Entringer number (source code)

= Entringer number
{c}
{title2=$E(n,k)$}

With the convention used here, $E(n,k)$ counts the <alternating permutations> $a_1\cdots a_{n+1}$ of $\{1,\ldots,n+1\}$ satisfying
$$
a_1>a_2<a_3>a_4<\cdots,\qquad a_1=k+1,\qquad 0\leq k\leq n.
$$
The direction of the first comparison and the shift in the first-entry index are essential when comparing tables. The <recurrence relation> is
$$
E(0,0)=1,\qquad E(n,0)=0\ (n>0),\qquad E(n,k)=E(n,k-1)+E(n-1,n-k)\ (1\leq k\leq n).
$$
Hence the first rows in increasing $k$ are $(1)$, $(0,1)$, $(0,1,1)$ and $(0,1,2,2)$. For $n=2$, the two <alternating permutations> are $213$ and $312$, explaining the two nonzero entries. The row sum counts all <alternating permutations> on $n+1$ labels; the last entry counts those on $n$ labels. Reversed-row <prefix sums> compute the <Entringer triangle> without enumerating the <permutations> individually.<A Survey of Alternating Permutations by Richard P. Stanley>[§2, printed pages4–5]{ref}