# Number of alternating variations

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.

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

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