Skip to content

Entringer Number

Entringer Numbers

Entringer numbers (Entringer number, OEIS A008281) \(E(n,k)\) count the number of permutations of \(0\) to \(n\) (i.e., \(n+1\) numbers) satisfying the following conditions:

  • The first element is \(k\);
  • The next element is smaller than the first element, the following element is larger than the previous one, the next is smaller than the previous one, and so on. The size relationship between adjacent elements follows this alternating pattern.

The initial values of Entringer numbers are:

\[ E(0,0)=1 \]
\[ E(n,0)=0 \]

They satisfy the recurrence relation:

\[ E(n,k)=E(n,k-1)+E(n-1,n-k) \]

Seidel–Entringer–Arnold Triangle

A triangular arrangement of Entringer numbers in a specific order is called the Seidel–Entringer–Arnold triangle (Seidel–Entringer–Arnold triangle, OEIS A008280). This triangle arranges the Entringer numbers \(E(n,k)\) in an "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 arranging Entringer numbers in this way is that it aligns with their recurrence relation \(E(n,k)=E(n,k-1)+E(n-1,n-k)\), making it easier to remember and understand.

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 distribution of this generating function is essentially a simple stretched deformation 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\) to \(c_i\) of \(1\) to \(n\) such that no element \(c_i\) lies between \(c_{i-1}\) and \(c_{i+1}\) in value.

For the number of zigzag permutations \(Z_n\) (OEIS A001250), starting from \(n=0\):

\[ 1, 1, 2, 4, 10, 32, 122, 544, \cdots \]

For example, the first few alternating permutations for small \(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

(Note the conceptual distinction from "derangements".)

For \(n > 1\), each zigzag permutation remains a zigzag permutation when reversed, so they can be paired up, implying the total number must be even.

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

An alternating permutation has its first element greater than the second, with the pattern:

\[ c_1>c_2<c_3>\cdots \]

A reverse alternating permutation has its first element smaller than the second, with the pattern:

\[ c_1<c_2>c_3<\cdots \]

If we swap positions \(1\) and \(n\), \(2\) and \(n-1\), and so on, we can interchange the sets of alternating and reverse alternating permutations. Therefore, the number of alternating permutations equals the number of reverse alternating permutations, exactly half of the zigzag permutations.

For \(n > 1\), let:

\[ A_n=\frac{Z_n}{2} \]

Define initial values:

\[ A_0=A_1=1 \]

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

\[ 1, 1, 1, 2, 5, 16, 61, 272, \cdots \]

Next, we try to solve for \(A_n\).

From \(1\) to \(n\), choose a subset of \(k\) numbers; there are \(\dbinom{n}{k}\) ways.

From this \(k\)-element subset, choose a reverse alternating permutation \(u\); there are \(A_k\) ways. From the complement set (the remaining \(n-k\) elements), choose a reverse alternating permutation \(v\); there are \(A_{n-k}\) ways.

Consider an \((n+1)\)-element permutation \(w\), formed by reversing \(u\) as the prefix, followed by \(n+1\), and then \(v\). Then \(w\) must be a zigzag permutation. Moreover, any \((n+1)\)-element zigzag permutation can be split at \(n+1\) to obtain corresponding reverse alternating permutations \(u\) and \(v\), and different \((n+1)\)-element zigzag permutations correspond to different \(u\) and \(v\).

Thus, we have the recurrence relation:

\[ 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)!} \]

This recurrence does not hold for \(n=0\); the initial values \(A_0\) and \(A_1\) are both \(1\).

This is a convolution of exponential generating functions. Assuming the exponential generating function of \(A_n\) is \(y\), we obtain the differential equation:

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

The \(+1\) on the right-hand side handles the special case when \(n=0\). The general solution is:

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

Substituting the condition that the \(0\)-th term is \(1\) yields the particular solution:

\[ y=\tan x+\sec x \]

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

Relationship Between Entringer Numbers and Zigzag Numbers

According to the definition of Entringer numbers, \(E(n,k)\) counts the number of alternating permutations of \(0\) to \(n\) starting with \(k\). Therefore, Entringer numbers are related to zigzag numbers:

\[ A_n=E(n,n) \]

There is a reason for calling \(A_n\) "zigzag numbers": let \(E_n\) denote Euler numbers and \(B_n\) denote Bernoulli numbers.

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 terms are (OEIS A000364):

\[ 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 terms are (OEIS A000182):

\[ 1, 2, 16, 272, 7936, \cdots \]

Thus, the Taylor expansion at \(x=0\) gives 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 \]

This forms the generating function for zigzag numbers.

  1. Alternating permutation - Wikipedia
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用