1, 1, 5, 61, 1385, 50521...

1, 2, 16, 272, 7936, 353792...

See Secant number (Wolfram MathWorld), Tangent number (Wolfram MathWorld) and Secant number (Journal of Integer Sequences), Tangent number (Journal of Integer Sequences). The secant numbers are also known as Euler numbers, and the tangent numbers are closely related to the Bernoulli numbers.

We shall refer to the secant numbers as E₀, E₂, E₄... and to the tangent numbers as T₁, T₃, T₅...

Knowing these numbers is equivalent to knowing the Taylor series for the secant and tangent functions respectively. In fact, E_2n is just the (2n)^th derivative of sec z at z = 0. T_2n−1 is just the (2n−1)^th derivative of tan z at z = 0.

To see what this means, take the case m=4. Of the 24 permutations of 4 elements, which we can write as 1234, 1243, 1324... 4321, just five have the property of running up-down-up in an alternating fashion. These are the permutations 1423, 1324, 2413, 2314, 3412. This tally agrees with E₄=5.

A new classification of permutations

Consider the two permutations of 8 elements given by 13284657 and 38142756. Both are alternating (up-down-up-down-up-down-up), but they differ in where the 'ups' and 'downs' occur. In 13284657, the 4 is at a 'low' point between two greater numbers, whilst in 38142756 the 4 is at a 'high' point between two smaller numbers.

We label 'low' points by R, and 'high' points by L. The first and last numbers in the sequence can be brought into the scheme as shown in the diagrams. Then the fact that the zigzag begins with an 'up' and ends with a 'up' is coded into the fact that the first number is an R and the last number an L.

The classification is specified more formally in our first paper, but these zigzag pictures convey the idea in a natural way.

We shall say that 13284657 has secant zigzag type RRLRRLLL, meaning that 1 is a low, 2 is a low, 3 is a high, 4 is a low, 5 is a low, and 6, 7, and 8 are highs. Similarly, 38142756 has secant zigzag type RRRLRLLL.

To illustrate the kind of structure that emerges, we consider the classification for alternating permutations on 8 elements. The norm sign indicates the size of the classes.

• |RRRRLLLL| = 576
• |RRRLRLLL| = 324
• |RRRLLRLL| = |RRLRRLLL| = 144
• |RRLRLRLL| = 64
• |RRRLLLRL| = |RLRRRLLL| = 36
• |RRLRLLRL| = |RLRRLRLL| = 16
• |RRLLRRLL| = 16
• |RRLLRLRL| = |RLRLRRLL| = 4
• |RLRRLLRL| = 4
• |RLRLRLRL| = 1

The reason for the choice of R and L is that the non-empty classes correspond exactly to the paths on the non-negative integers starting and ending at 0 and moving Right or Left by one step. Thus the class RRLRRLLL corresponds to the path (0,1,2,1,2,3,2,1,0) and RRRLRLLL to the path (0,1,2,3,2,3,2,1,0). The number of such paths is well known to be the Catalan Number which in this case is 8!/(4! × 5!) = 14.

This classification has been chosen in just such a way that the every alternating permutation is characterised by a sequence of R's and L's. But it can be extended to all permutations by writing an S when a position is neither R nor L. For instance, the permutation 58372461 is of type SRRSRLLL. These classes can also be mapped into paths on the non-negative integers, by allowing S steps which are stationary, e.g. SRRSRLLL corresponds to the path (0,0,1,2,2,3,2,1,0).

We could apply this classification to permutations of an odd number of elements, but it would not pick out the alternating permutations correctly. To do this, we need to define a different classification, the tangent zigzag classes. Considering permutations on 7 elements, the alternating permutations run up-down-up-down-up-down, and this is naturally accounted for by writing R' for low points, L' for high points, S' for points which are neither high nor low, and dealing with the end points as in the illustrated example. Since 1 is always a low point in this classification, in any permutation, its R' is omitted as redundant. Thus the alternating permutation 4713265 is of type R'L'R'R'L'L' (as 2, 4, and 5 are low points; 3, 6, and 7 are high points).

Both the secant and the tangent classes can now be written down for permutations of both even and odd degree, but the secant classes serve to pick out the alternating permutations of even degree, and the tangent classes pick out alternating permutations of odd degree.

How can the sizes of these classes be calculated efficiently? It is now very helpful to extend the definitions. If X and Y are zigzag classes, with sizes |X| and |Y|, define |X + Y| to be |X| + |Y| and more generally |αX + βY| = α|X| + β|Y|. To see the value of this extension, consider the case of E₄ = 5. Using the classification we have developed, we have

E₄ = |RRLL| + |RLRL| = 4 + 1 = 5

E₄ = |RRRR| + |RRRL| + |RRLR| + |RRLL| + ... + |LLLL|

= |(R + L)⁴|.

E_2n = |(R + L)²ⁿ|

T_2n+1 = |(R' + L')²ⁿ|.

|(R + L + S)²ⁿ| = (2n)!

|(R' + L' + S')²ⁿ| = (2n+1)!

The next observation is that with this extension, our R, L, S etc. can be treated as operators on a vector space. They are non-commuting operators, because RL is not the same as LR. In fact we can define the commutator [R, L] = RL − LR. This allows us to express our extraordinarily simple main result as follows:

Main Theorem:

[R, L] = S,   [R, S] = 2R,   [S, L] = 2L

Also

[R', L'] = S',   [R', S'] = 2R',   [S', L'] = 2L'

The proofs of these statements require only simple counting arguments and are given in our first paper. These, together with some other simple facts, imply that for any X (a sequence of R, L and S operators):

For p ≥ 0, |R^pSX| = (2p + 1) |R^pX|

For p ≥ 0, |R^pLX| = (p + 1)² |R^p−1X|

and similarly

For p ≥ 0, |R'^pS'X'| = 2(p + 1) |R'^pX'|

For p ≥ 0, |R'^pL'X'| = (p + 1)(p + 2) |R'^p−1X'|

from which the size of any given class can be evaluated recursively.

For evaluation of the secant and tangent numbers it is not necessary to work out the sizes of the individual classes but instead to evaluate |(R + L)²ⁿ|, |(R' + L')²ⁿ| directly. The results can be presented in a form which slightly generalises the idea of the Pascal triangle:

r = a²,   l = a*²   and   s = 1/2(aa* + a*a)

satisfy the same commutation relations as do the R, L and S. Does this mean there are analogous annihilation and creation operators for the permutations, which behave like square roots of the R and L operators? Almost, but not quite.

We show in the papers that it is possible and useful to define A and A* operators which are more primitive than the R, L, S, R', L', S', and which bring them all into a single scheme. However, these A and A* do not satisfy the standard commutation relations for annnihilation and creation operators, but a generalisation of them with a parity-dependent term. In our second paper we analyse these commutation relations in greater generality.

It seems to us that there may be further surprising results about permutations and operator structures to be found from this starting-point. A particularly interesting feature is that the duality between secant and tangent numbers can be expressed in terms of an anti-commuting operator.

One question we have explored is that of the parallel structure for transpositions, i.e. those permutations which simply swap elements in pairs. As an example, the permutation 53271846 is a transposition, swapping the pairs (15)(23)(47)(68). First we define a new classification for transpositions, in which a number is marked C if its partner is greater, and D if its partner is smaller. Thus this transposition is of type CCDCDCDD. In this case it turns out that C and D behave as annihilation and creation operators which satisfy the standard commutation relation [C, D] = 1.

The analogues of the alternating permutations are then those transpositions which are generated entirely by C² and D². (For instance (15)(27)(38)(46) is of type CCCCCDDDD.) Computing the sizes of these classes is equivalent to calculating certain amplitudes which arise in quantum optics.

In our second paper we compute the total number of 'alternating transpositions', as so defined, by a purely combinatorial argument, finding agreement with the standard answer from quantum mechanics. The series runs 1, 2, 28, 1112, 87568, 11447072... and has generating function √(sec 2z).