1
$\begingroup$

Let $M=\{1,2,...,k\}$ and $\sigma=\left( \sigma_{1},...,\sigma_{n}\right) $ be a variation of elements of $M$, $\sigma_{i}\in M$, such that any element of $M$ takes part in $\sigma$ (so $n\geq k$). We shall call $\sigma$ an alternating variation if

$(\sigma_{i}-\sigma_{i-1})(\sigma_{i+1}-\sigma_{i})<0$, for $i=2,...,n-1$.

For example, $\sigma_{0}=(1,4,3,4,3,7,5,6,4,5,2,6)$ is such a variation with $k=7$, $n=12$.

Let $G(n,k)$ be the number of all alternating variations of length $n$ of $k$ elements. Broadly speaking, I am interested in this number. Highly likely, there is no any exact formula for $G(n,k)$, although there might be some nice generating function, similarly to Andre's result about $G(n,n)$, that is, the number of alternating permutations of $n$ elements, see https://en.wikipedia.org/wiki/Alternating_permutation. In 1881 D. Andre* shows that $\tan x+\sec x$ is a generating function for $G(n,n)$.

Note that the alternating variations are coding the similarity classes of "good" smooth functions defined on some segment $f:[a,b]\rightarrow\mathbb{R}$ with coinciding critical values allowed ($f(a)$ and $f(b)$ are treated also as critical values here). For example, the above variation $\sigma_{0}% =(1,4,3,4,3,7,5,6,4,5,2,6)$ is coding the function depicted on the figure below.

A "good" function

*D. Andre. Sur les permutations alternees. Journal de mathematiques pures et appliquees, 3e serie, tome 7 (1881), 167--184. gallica link

$\endgroup$

1 Answer 1

1
$\begingroup$

http://oeis.org/A079502 $$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.