Entringer Number

Entringer number

The Entringer number (OEIS A008281) $E(n,k)$ is the number of permutations of the $n+1$ numbers from $0$ to $n$ satisfying the following conditions:

• The first element is $k$.
• The next element is smaller than the first, the following element is larger than the preceding one, the next is smaller than the preceding one, and so on; every subsequent adjacent pair follows this alternating pattern.

The initial values of the Entringer numbers include:

$$E(0,0)=1$$ $$E(n,0)=0$$

They satisfy the recurrence

$$E(n,k)=E(n,k-1)+E(n-1,n-k)$$

Seidel–Entringer–Arnold triangle

A suitably arranged number triangle of Entringer numbers is called the Seidel–Entringer–Arnold triangle (OEIS A008280). It arranges the Entringer numbers $E_(n,k)$ in ox-plowing order:

$$\begin{aligned} & E(0,0) \\ & E(1,0) \rightarrow E(1,1) \\ & E(2,2) \leftarrow E(2,1) \leftarrow E(2,0) \\ & E(3,0) \rightarrow E(3,1) \rightarrow E(3,2) \rightarrow E(3,3) \\ & E(4,4) \leftarrow E(4,3) \leftarrow E(4,2) \leftarrow E(4,1) \leftarrow E(4,0) \end{aligned}$$

That is:

$$\begin{aligned} & 1 \\ & 0 \rightarrow 1 \\ & 1 \leftarrow 1 \leftarrow 0 \\ & 0 \rightarrow 1 \rightarrow 2 \rightarrow 2 \\ & 5 \leftarrow 5 \leftarrow 4 \leftarrow 2 \leftarrow 0 \end{aligned}$$

The advantage of this arrangement is that it agrees with the recurrence $E(n,k)=E(n,k-1)+E(n-1,n-k)$, making the recurrence easier to remember and understand.

The Entringer numbers have an exponential generating function:

$$\sum_{m=0}^\infty\sum_{n=0}^\infty E\left(m+n,\frac{1}{2}\left(m+n+{(-1)}^{m+n}(n-m)\right)\right)\frac{x^m}{m!}\frac{x^n}{n!}=\frac{\cos x+\sin x}{\cos (x+y)}$$

The coefficient arrangement of this generating function is in fact a simple stretched version of the Seidel–Entringer–Arnold triangle above:

$$\begin{array}{ccccc} E(0,0) & E(1,1) & E(2,0) & E(3,3) & E(4,0) \\ E(1,0) & E(2,1) & E(3,2) & E(4,1) & \\ E(2,2) & E(3,1) & E(4,2) & & \\ E(3,0) & E(4,3) & & & \\ E(4,4) & & & & \end{array}$$

That is:

$$\begin{aligned} & 1\quad 1\quad 0\quad 2\quad 0\\ & 0\quad 1\quad 2\quad 2\\ & 1\quad 1\quad 4\\ & 0\quad 5\\ & 5 \end{aligned}$$

Zigzag permutations

A zigzag permutation is a permutation $c_1$ through $c_i$ of $1$ through $n$ such that no element $c_i$ lies between $c_{i-1}$ and $c_{i+1}$ in value.

The number of zigzag permutations $Z_n$ (OEIS A001250), starting from $n=0$, is:

$$1, 1, 2, 4, 10, 32, 122, 544, \cdots$$

For example, the alternating permutations for the first few values of $n$ are:

$$\begin{aligned} n=1: & \{1\}\\ n=2: & \{1,2\}, \{2,1\}\\ n=3: & \{1,3,2\}, \{2,1,3\}, \{2,3,1\}, \{3,1,2\}\\ n=4: & \{1,3,2,4\}, \{1,4,2,3\}, \{2,1,4,3\}, \{2,3,1,4\}, \{2,4,1,3\}, \\ & \{3,1,4,2\}, \{3,2,4,1\}, \{3,4,1,2\}, \{4,1,3,2\}, \{4,2,3,1\} \end{aligned}$$

Alternating permutations and zigzag numbers

(These should be distinguished conceptually from derangements.)

For $n$ greater than $1$, reversing every zigzag permutation produces another zigzag permutation, so the permutations can be paired and their number must be even.

Here is another pairing method: divide zigzag permutations into alternating permutations and reverse alternating permutations.

An alternating permutation starts with a larger element and satisfies

$$c_1>c_2<c_3>\cdots$$

A reverse alternating permutation starts with a smaller element and satisfies

$$c_1<c_2>c_3<\cdots$$

Swapping positions $1$ and $n$, positions $2$ and $n-1$, and so on exchanges the two sets. Therefore, the numbers of alternating and reverse alternating permutations are equal, exactly half the number of zigzag permutations.

For $n$ greater than $1$, let:

$$A_n=\frac{Z_n}{2}$$

with initial values

$$A_0=A_1=1$$

Here $A_n$ is called the Euler zigzag number (OEIS A000111), with values starting from $n=0$:

$$1, 1, 1, 2, 5, 16, 61, 272, \cdots$$

Let us derive $A_n$.

Choose a $k$-element subset from $1$ through $n$; there are $\dbinom{n}{k}$ choices.

Within this $k$-element subset, choose a reverse alternating permutation $u$; there are $A_k$ choices. From the remaining $k$-element subset of $n-k$ elements, choose a reverse alternating permutation $v$; there are $A_{n-k}$ choices.

Consider a permutation $w$ of $n+1$ elements. Reverse $u$ to form its beginning, append $n+1$, and then append $v$. Thus, $w$ is certainly a zigzag permutation. Conversely, every zigzag permutation of $n+1$ elements can be cut at $n+1$ to obtain the corresponding reverse alternating permutations $u$ and $v$, and distinct $n+1$-element zigzag permutations give distinct $u$ and $v$.

Therefore,

$$2A_{n+1}=\sum_{k=0}^n \dbinom{n}{k} A_k A_{n-k}$$ $$2(n+1)\frac{A_{n+1}}{(n+1)!}=\sum_{k=0}^n \frac{A_k}{k!}\frac{A_{n-k}}{(n-k)!}$$

When $n$ is $0$, this recurrence does not hold; the initial values $A_0$ and $A_1$ are both $1$.

This is a convolution of exponential generating functions. If the exponential generating function of $A_n$ is $y$, then:

$$2\frac{\mathrm{d}y}{\mathrm{d}x}=y^2+1$$

The $1$ on the right handles the special case when $n$ is $0$. The general solution is:

$$y=\tan\left(\frac{1}{2}x+C\right)$$

Substituting the term for $0$, which is $1$, gives the particular solution:

$$y=\tan x+\sec x$$

The tangent function is odd and the secant function is even, so their sum is the generating function of the zigzag numbers.

Relationship between Entringer numbers and zigzag numbers

By definition, the Entringer number $E(n,k)$ counts alternating permutations of $0$ through $n$ whose first element is $k$. Thus, Entringer numbers and zigzag numbers are related by:

$$A_n=E(n,n)$$

There is also a reason for calling $A_n$ the zigzag number. Let $E_n$ be the Euler number and $B_n$ the Bernoulli number.

When $n$ is even, the zigzag numbers with even indices are also called secant numbers $S_n$, or zig numbers. They satisfy:

$$A_n=(-1)^{n/2}E_n$$

The first few values (OEIS A000364) are:

$$1, 1, 5, 61, 1385, \cdots$$

When $n$ is odd, the zigzag numbers with odd indices are also called tangent numbers $T_n$, or zag numbers. They satisfy:

$$A_n=\frac{(-1)^{(n-1)/2}2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}$$

The first few values (OEIS A000182) are:

$$1, 2, 16, 272, 7936, \cdots$$

Thus, the Taylor expansions at $x=0$ give the secant and tangent numbers:

$$\sec x=A_0+A_2\frac{x^2}{2!}+A_4\frac{x^4}{4!}+\cdots$$ $$\tan x=A_1x+A_3\frac{x^3}{3!}+A_5\frac{x^5}{5!}+\cdots$$

Or, combined:

$$\sec x+\tan x=A_0+A_1x+A_2\frac{x^2}{2!}+A_3\frac{x^3}{3!}+A_4\frac{x^4}{4!}+A_5\frac{x^5}{5!}+\cdots$$

which is the generating function of the zigzag numbers.

References and links

1. Alternating permutation - Wikipedia