The tangent counts zigzags

The Taylor series of the sine and cosine have coefficients anyone can remember: $1/n!$ with a sign pattern. The tangent’s do not:

$$\tan x = x + \frac{2x^3}{3!} + \frac{16x^5}{5!} + \frac{272x^7}{7!} + \frac{7936x^9}{9!} + \cdots$$

and the secant’s are $1, 1, 5, 61, 1385, \ldots$ over the even factorials. Rebuilding the sine from its zeros found where the tangent’s partner, the cotangent, gets its coefficients — from the sums of reciprocal even powers — and that is one explanation of the numbers. This essay is about a second, which has nothing to do with analysis at all. The numbers $1, 1, 2, 5, 16, 61, 272, \ldots$ count arrangements.

Arrangements that zigzag #

Write the numbers 1 to $n$ in some order. Call the arrangement a zigzag — up-down, or alternating — if the first number is smaller than the second, the second larger than the third, the third smaller than the fourth, and so on, alternately rising and falling.

For one number there is one arrangement, trivially a zigzag. For two there is one, 12. For three, 132 and 231: two. For four, five: 1324, 1423, 2314, 2413, 3412. For five, the sixteen drawn. The counts go 1, 1, 2, 5, 16, and continue 61, 272, 1385, 7936. The odd-length counts are the tangent’s numerators, $1, 2, 16, 272, 7936$; the even-length ones are the secant’s, $1, 5, 61, 1385$. Désiré André proved in 1879 that this continues for ever: the number of zigzag arrangements of $n$ numbers is $n!$ times the coefficient of $x^n$ in $\tan x + \sec x$.

It is a statement that should not be true. The tangent is a ratio of two waves — the sine and the cosine, a circle seen from the side — and its Taylor coefficients come out of dividing one power series by another, a computation with alternating signs and cancellation. The zigzags are a property of orderings, with no signs anywhere. The bridge between them is short, and it is worth seeing before believing.

Splitting at the largest number #

Take any zigzag of $n + 1$ numbers, up-down or down-up, and find its largest entry. The largest entry is a peak — it is bigger than both neighbours, being bigger than everything — and it cuts the arrangement in two.

The left part is a zigzag of whatever length it has, ending as the arrangement approached the peak; the right part, read from the far end inwards, is a zigzag too. Conversely, choose which $k$ of the other $n$ numbers go on the left, put any zigzag of them there, put any zigzag of the remaining $n - k$ on the right reversed, and place the maximum between: the result alternates, and it is up-down or down-up according to the parity of $k$. Counting both kinds, every alternating arrangement of $n + 1$ numbers arises exactly once, so

$$2A_{n+1} = \sum_{k=0}^{n} \binom{n}{k} A_k A_{n-k}.$$

For seven numbers that is $2 \times 272 = 61 + 96 + 75 + 80 + 75 + 96 + 61 = 544$, and the figure’s arrangement is one of those 544.

Now the bridge. Put the counts into a series with factorials, $y(x) = \sum A_n x^n / n!$. The left side of the recurrence is twice the coefficient of the derivative $y'$. The right side is the coefficient of $y^2$, because multiplying two such series multiplies their coefficients with exactly those binomial weights. The equation holds for every $n \ge 1$, and the constant terms fix the rest: the counts are the coefficients of the solution of

$$y' = \frac{1 + y^2}{2}, \qquad y(0) = 1.$$

And that equation has a solution anyone can check: $y = \tan x + \sec x$. Its derivative is $\sec^2 x + \sec x \tan x = \sec x (\sec x + \tan x)$, and $(1 + y^2)/2$ simplifies to the same thing using $\sec^2 x = 1 + \tan^2 x$. A recurrence about splitting arrangements at their maximum is the derivative of the tangent, read coefficient by coefficient.

A triangle that only adds #

The recurrence computes the counts but needs multiplication. There is a faster way that needs nothing but addition, found by Ludwig Seidel in 1877 and rediscovered several times since, most memorably by Vladimir Arnold.

Each row is built from the one above by running sums taken in the opposite direction — the zigzag of the ploughing that gives the triangle its name — and the last entry of row $n$ is the number of zigzags of length $n$. The entries in between count something too: the number in row $n$, position $k$, counts the zigzags of $n$ numbers that start with the number $k$ (in the appropriate direction), a refinement due to Robert Entringer. Row four shows it concretely. Row three, read in its own direction, is $0, 1, 2, 2$; row four starts at nought and adds those numbers taken from the other end — $2$, then $2$, then $1$, then $0$ — giving the running totals $0, 2, 4, 5, 5$. The last entry, five, is the number of zigzags of four numbers, and the entries before it, $2, 4, 5$, split those five according to how the arrangement begins. Two arithmetic operations per entry, and no multiplication anywhere, produce numbers that the tangent’s series produces by long division.

That is why the triangle works. A zigzag starting at $k$ and going down continues with a zigzag of the remaining numbers going up from something smaller than $k$, and summing over the possible second entries is exactly the running sum along the row.

Three counts, one table #

Since the claim is that three unrelated computations give the same numbers, the honest check is to do all three.

The first column is brute force: 362,880 arrangements of nine numbers, filtered. The second is the triangle. The third is pure series arithmetic: the coefficients of $\tan x$ satisfy $\tan x \cdot \cos x = \sin x$, which, multiplied by factorials, is a triangular system of whole numbers solved one coefficient at a time; the secant’s satisfy $\sec x \cdot \cos x = 1$ in the same way. No step of the third computation mentions an arrangement, and no step of the first mentions a cosine. They agree: 1, 1, 1, 2, 5, 16, 61, 272, 1,385, 7,936, 50,521, 353,792, 2,702,765, 22,368,256, 199,360,981.

The division is short enough to do by hand for the first terms, and doing it shows where the cancellation lives. Write $\tan x = t_1 x + t_3 x^3/3! + t_5 x^5/5! + \cdots$ and multiply by $\cos x = 1 - x^2/2! + x^4/4! - \cdots$; the product must be $\sin x = x - x^3/3! + x^5/5! - \cdots$. Matching the coefficient of $x$ gives $t_1 = 1$. Matching $x^3/3!$ gives $t_3 - 3t_1 = -1$, so $t_3 = 2$. Matching $x^5/5!$ gives $t_5 - 10 t_3 + 5 t_1 = 1$, so $t_5 = 16$. Every step is a subtraction of binomially weighted earlier terms, with signs alternating — the opposite of the zigzag count, which never subtracts anything. That the two produce the same positive integers is the content of the theorem, and no single step of the division hints at it.

The secant’s numbers, $1, 1, 5, 61, 1385, \ldots$, are older than André’s interpretation: Euler computed them in the 1750s, and they are still called the Euler numbers. They count the zigzags of even length, which begin by rising and end by rising. A zigzag of odd length ends on a fall from a peak, and that asymmetry — even lengths end where they started going, odd lengths end where they turned — is why the counts split between two functions, one even and one odd, rather than coming from a single one.

The tangent numbers have a further life. Each is a multiple of a Bernoulli number, the numbers that sums of powers are built from: $T_{2n-1} = 2^{2n}(2^{2n}-1)|B_{2n}|/(2n)$. So the zigzags of odd length are counted by the same numbers that give $1^k + 2^k + \cdots + m^k$ and the even values of the zeta function, and the reason, ultimately, is that all of them are coefficients of one family of functions — the tangent, the cotangent and their relatives — computed in different ways.

Zigzags as a volume #

There is a third reading of the share $A_n/n!$, and it makes the π less mysterious. Choose $n$ numbers independently and uniformly between nought and one. With probability one they are distinct, and their relative order is a uniformly random arrangement, so the chance that they zigzag — $x_1 < x_2 > x_3 < \cdots$ — is exactly $A_n/n!$. That chance is a volume: the volume of the region of the $n$-dimensional unit cube where the coordinates alternate.

The cube splits into $n!$ congruent slices, one for each ordering of the coordinates, each a simplex of volume $1/n!$ — the slicing that counting the orderings consistent with a partial order turns into a volume computation. A zigzag is a partial order on the coordinates, a fence of alternating comparisons, and the region it carves out is the union of $A_n$ of the slices. So the coefficients of the tangent and secant are the volumes of these “zigzag polytopes”: $1/3$ for three coordinates, $5/24$ for four, $2/15$ for five.

Seen this way, the recurrence is a statement about integrals. The volume for $n + 1$ coordinates can be computed by integrating over the position of the largest coordinate and multiplying the volumes of the two smaller zigzag regions on either side, with the right scaling — and that is the convolution that the binomial coefficients express. The differential equation $y' = (1 + y^2)/2$ is the same convolution, made continuous.

A zigzag is not a mountain range #

Alternating patterns appear elsewhere too, and the comparison is instructive. A path of up-steps and down-steps that never dips below its start is counted by the Catalan numbers, and the reflection trick counts them in a closed form; their generating function satisfies an equation with a square in it, an algebraic equation, and the counts grow like $4^n$. The zigzag arrangements are a different object — they record the relative order of all the values, not just the sequence of directions — and their generating function satisfies a differential equation, not an algebraic one. Its solution is transcendental, and the counts grow like $n!$ times $(2/\pi)^n$.

The difference is the general rule. Sequences counted by an algebraic equation have growth rates that are algebraic numbers and generating functions with branch points; sequences whose exponential generating function solves a non-linear differential equation can have π, and the trigonometric functions, in their growth. The derangements — arrangements in which no number keeps its place — are the gentlest case of the second kind: their exponential generating function is $e^{-x}/(1 - x)$, with a single pole at one, so a random arrangement is a derangement with probability tending to $1/e$. The zigzags’ function has its first pole at $\pi/2$ instead, and so the share falls geometrically rather than settling.

How rare a zigzag is #

There are $n!$ arrangements of $n$ numbers, and $A_n$ of them zigzag. The share $A_n/n!$ is exactly the Taylor coefficient of $\tan x + \sec x$, and so the question “how rare are zigzags?” is a question about how fast a Taylor series’ coefficients shrink. That has a sharp answer, and it comes from places the series never visits on the real line between nought and its first blow-up.

The function $\tan x + \sec x$ blows up at $x = \pi/2$ — a simple pole — and its radius of convergence is therefore $\pi/2$: the coefficients must shrink, eventually, by a factor of $\pi/2$ per term. More than that, near the pole the function behaves like $2/(\pi/2 - x)$, and the coefficients of that simple fraction are exactly $2 (2/\pi)^{n+1}$. Subtracting it leaves a function whose nearest singularity is at $-\pi/2$ — where $\tan x + \sec x$ happens to be finite, the two blow-ups cancelling — and then at $-3\pi/2$, three times further away. So the next correction to the coefficients is smaller by a factor of three per term, and

$$\frac{A_n}{n!} = 2\left(\frac{2}{\pi}\right)^{n+1}\left(1 + O(3^{-n})\right).$$

The figure measures it: the relative error tracks $3^{-(n+1)}$ down to about $10^{-11}$ at twenty-four numbers. A random arrangement of twenty numbers zigzags with chance about $2 (2/\pi)^{21}$, roughly one in 6,569 — and the formula gets that chance right to ten digits.

There is a surprise in it. A count of arrangements — a purely combinatorial question about finite orderings — has π in its answer, and to eleven significant figures. The π is the location of the tangent’s pole, which is where the cosine has its first zero. The zigzags know where the cosine crosses the axis.

What the figures leave to the theorem #

The counts agree in three columns for every length drawn, and the boustrophedon and the series agree to twenty-four terms; André’s theorem says they agree for every $n$, and the proof is the splitting argument, not the table. The splitting argument itself is drawn for one arrangement; its correctness rests on the claim that every alternating arrangement arises exactly once from a choice of left set and two smaller zigzags, which is a bijection that has to be checked in general, as above, rather than observed.

The asymptotic formula’s error term is a statement about every $n$, derived from the location of the poles; the figure shows the error following $3^{-(n+1)}$ to twenty-four terms, where floating-point arithmetic is still comfortably adequate, and says nothing beyond. The identification of the poles is exact: the tangent and secant are meromorphic, with poles only at odd multiples of $\pi/2$, which is what makes the error decrease by exactly a factor of three rather than some other ratio.

Still open: which alternations have such formulas #

André’s theorem is the first of a family. Count arrangements by more refined patterns — the positions of their peaks, the lengths of their runs, the arrangements avoiding a given smaller pattern — and some of the counts have generating functions as clean as $\tan x + \sec x$, while others do not. Arrangements whose runs all have length at most two or three, or that alternate with a fixed period, have exponential generating functions that are ratios of sums of exponentials; their growth rates are set by the zeros of those denominators, as here. But for arrangements avoiding a pattern of length four, such as 1324, no formula is known, and even the growth rate of the count is known only to lie between about 10.27 and 13.5.

A second question is the one the boustrophedon raises. Seidel’s triangle, Arnold’s “snakes” and the Entringer numbers all describe the same refinement of the zigzags; a similar addition-only triangle exists for many sequences defined by a differential equation of this kind, and which differential equations admit one — which coefficient sequences can be produced by alternating running sums — has no general answer, though Arnold found the phenomenon in the geometry of singularities, where the snakes count the ways a polynomial’s critical values can be arranged.

Arnold’s own generalisation shows how far the pattern reaches. Allow the numbers in an arrangement to carry signs, as the symmetries of a cube or a hypercube do, and count the signed zigzags he called snakes: their counts are the Springer numbers, $1, 1, 3, 11, 57, 361, \ldots$, and their exponential generating function is $1/(\cos x - \sin x)$. The same reasoning applies to it. Its first pole is where $\cos x = \sin x$, at $\pi/4$, so the snakes outnumber the zigzags by a factor approaching two per added number; and the next pole, at $-3\pi/4$, is three times as far away, so the same factor-of-three accuracy holds. Every family of reflection groups has its own version, and in each the growth is read off the first zero of a trigonometric denominator.

Where the cosine crosses the axis #

The tangent’s Taylor coefficients count the arrangements of $n$ numbers that alternately rise and fall. Splitting such an arrangement at its maximum gives a recurrence, and the recurrence is the differential equation $y' = (1 + y^2)/2$ that $\tan x + \sec x$ satisfies. A triangle of additions computes the same numbers, and series division computes them again; all three agree.

And because the counts are Taylor coefficients, their size is set by the nearest singularity. The cosine vanishes at $\pi/2$, the tangent blows up there, and the share of arrangements that zigzag falls by a factor of $\pi/2$ with every number added — a fact about orderings of finite sets, controlled by where a wave first crosses the axis.