## Abstract

The combinatorial properties of the Bernoulli and Euler numbers are interpreted using a new classification of permutations. The classification is naturally described by an operator algebra of a type familiar from quantum theory. It has a duality structure described by an operator satisfying anticommutation relations.

## 1. Introduction

The Bernoulli and Euler numbers have been studied for some 300 years and have properties in both the theory of numbers and combinatorial theory which are very well known. The Bernoulli numbers *B*_{n} can be defined by the Taylor series(1.1)They are closely related to the Riemann *zeta function*, defined for by(1.2)Standard complex analysis shows that(1.3)so that knowledge of the non-trivial Bernoulli numbers is equivalent to knowing the sums of the elementary series:and so on, for all negative even powers.

The values and properties of the Bernoulli numbers are summarized in standard texts, for instance Abramowitz & Stegun (1970, pp. 803–819) and Gradshteyn & Ryzhik (2000, pp. 1030–1035). It is straightforward to show that *B*_{0}=1, *B*_{1}=−1/2 and *B*_{2n+1}=0 for all *n*≥1. Furthermore, all the Bernoulli numbers can be found by multiplying both sides by e^{z}−1, identifying coefficients of powers of *z* and solving linear equations. This recursive process has a special role in the history of mathematics, as the calculation of Bernoulli numbers by this means (in numerical approximation, as decimals) was a problem chosen by Charles Babbage *ca* 1840 to illustrate the potential of his projected Analytical Engine.

Far more efficient recursive methods have since been found. A starting point is the observation that the Bernoulli numbers can be reformulated as the coefficients of the Taylor series for the cotangent function. Thus, properties of the Bernoulli numbers can then be related to identities and integrals in higher trigonometry. This development naturally brings in the closely related *Euler numbers*. A less obvious but striking feature of these properties is a connection with *alternating* or ‘zigzag'permutations in combinatorial theory.

The purpose of this paper is to show that this elementary and well-known material leads in an unexpected direction when the concept of alternating permutations is extended to a further classification of permutations which is still entirely elementary, but appears to be new. The emergent algebra is naturally described in terms of the algebra of *creation and annihilation operators* as used in quantum theory. It also involves a duality between permutations on an even/odd number of elements, which can be described by an operator satisfying *anticommutation relations*.

The algebraic structure to be developed here is not intended to surpass existing computational methods, but to shed a quite new light on the underlying structure.

The plan is as follows. Section 2 sets out further classical material. We base our work on the *tangent numbers*, which are closely related to the Bernoulli numbers, and the *secant numbers*, which are the same as the Euler numbers. The duality between the tangent and the secant series is then pivotal in the ensuing discussion. In §3, we show by a Fourier transform method how the tangent and secant numbers are related to the alternating or zigzag permutations. In §4, we count such permutations in the secant case, by defining the new classification of permutations and showing that it is naturally described by linear operators. Section 5 recasts the operators as matrices, thus giving a natural efficient algorithm for the secant numbers. In §6, we present a parallel discussion for the tangent numbers. In §7, we show that the two cases can be unified by an operator satisfying anticommutation relations.

## 2. Tangent and secant

Riemann's theory exploits the fact that the infinite sum for the zeta function can be rewritten as an infinite product over the primes. Cutting this decomposition short at the *first* prime, i.e. 2, we obtain structures with an even/odd duality. These lead to relations between the Bernoulli numbers and trigonometrical functions as follows:(2.1)(2.2)and(2.3)It is convenient to work with the *tangent numbers T*_{2m−1}, which we shall show are always positive integers, as defined by(2.4)(2.5)In what follows, we shall generally refer to the tangent numbers as the objects of our interest, but it should be remembered that they have this simple relationship with the Bernoulli numbers.

Note that the tangent numbers are also naturally related with the secant by(2.6)However, the secant function itself requires an essentially different sequence of integers. We define the *secant numbers E*_{2m}, which we shall also show are always positive integers, by(2.7)Then(2.8)so that the secant numbers are related to the summation of *alternating* series of negative *odd* powers of the natural numbers.

We prefer to use the term ‘secant numbers’ for the *E*_{n} rather than ‘Euler numbers’ owing to the natural tangent/secant duality. There are various slightly differing conventions for their definition. We follow Knuth & Buckholtz (1967). The advantage of their convention is that there is a natural series of positive integers *E*_{0}, *T*_{1}, *E*_{2}, *T*_{3}, *E*_{4}, … with the subscript *n* always associated with a series with inverse power (*n*+1) and, as we shall see, also naturally associated with the permutation group of order *n*.

It should be clear that these trigonometrical series together with such relations asallow elementary evaluations of the Bernoulli, tangent and secant numbers in many different ways. But these methods have a complexity equivalent to inverting an upper diagonal matrix with entries taken from an exponential series involving *O*(*n*^{3}) multiplications.

Joffe (1917–1920) used a much more efficient type of recursion relation. This was then further developed and refined by Knuth & Buckholtz (1967). We note further advances in computation as detailed by Fee & Plouffe (2007). The approach to be shown here will not go beyond the recursion relations used by Joffe in efficiency. However, the algebraic approach is completely different.

## 3. Zigzag permutations via Fourier transforms

The connection between the tangent numbers and alternating or zigzag permutations is well known. We give a direct argument for it using a Fourier-analytic method.

Let *f*_{0}(*x*) be the square wave with period 4: *f*_{0}(*x*)=1 on (−1, 1), *f*_{0}(1)=0, *f*_{0}(−1)=0, *f*_{0}(*x*)=−1 on (1, 3). Then by standard Fourier theory,(3.1)We now define a sequence *f*_{n} of periodic functions with the properties(3.2)Then(3.3)and(3.4)Restricting to the interval (0, 1), where *f*_{0}(*x*)≡1, the *f*_{n} can be written as(3.5)and so on. But(3.6)Hence, *T*_{n} and *E*_{n} are given by(3.7)The *n*th integral here is in the *n*-dimensional hypercube. Consider the hypercube as decomposed into the *n*! regions associated with the *n*! different orderings of . These regions are of equal volume and so each has volume (*n*!)^{−1}. The contribution to the *n*th integral will be non-zero only from points in those regions where etc. Hence, we need to count only the number of such regions to evaluate the integral. In fact *E*_{n} and *T*_{n} are just these numbers (and so must always be positive integers).

The problem of counting the regions is equivalent to counting the number of permutations *π* of (12345 … *n*) which have the alternating or zigzag property,(3.8)Thus *T*_{n} and *E*_{n} are precisely the number of permutations on *n* elements with the zigzag property.

This integration scheme can be represented in a slightly different form, using the idea of a Green function. First, change variables by putting , . Then the integral becomes(3.9)and our formulae can be recast as(3.10)and(3.11)where the integral is taken over the whole unit hypercube and *G*(*x*, *y*) is the characteristic function of the set in [0,1]^{2}. Now, the Fourier representation of *G*(*x*, *y*) extended to a function periodic in both *x* and *y* with period 4 is(3.12)and this is readily seen to be consistent.

A more symmetrical formulation creating a loop rather than a chain of Green functions is(3.13)and(3.14)The *f*_{n}(*x*) are related to the classical *Bernoulli polynomials*. The relation is most readily found by considering the generating functions. The generating function for the *f*_{n}(*x*) is ; the generating function for the Bernoulli polynomials is and hence(3.15)More simply, the *f*_{n}(*x*) are equivalent to the *Euler polynomials*, with generating function ,(3.16)

## 4. Counting zigzag permutations: the secant case

We now count the number of zigzag permutations by a new method. The method is slightly simpler in the case of the secant numbers, so we take this case first.

We have shown that the calculation of *E*_{4} amounts to noting that of the 24 permutations of (1234), just 5 of them have the zigzag property, namely those given by We need a systematic method of calculating this number for general (even) *n*.

To obtain such a method, it is useful to classify permutations not just according to whether or not they satisfy the zigzag property, but by a more refined criterion. Although it is an elementary idea, and simple to execute, we are not aware of this classification having been used before in the literature of combinatorial theory.

Given a permutation *π*(123 … *n*), we can define its *secant zigzag class* as follows:(4.1)The sequence (*Z*(1), *Z*(2), …, *Z*(*n*)) is then called the secant zigzag class of *π*. For even *n*, the zigzag permutations are precisely those without an *S* in their class. Thus, in the case *n*=4, (3412) is of class *RLRL*, and the other four zigzag permutations are of class *RRLL*.

We are interested in the size of these classes, which we will write as norms. The idea is again best illustrated by simple examplesWe define these classes for all *n* even though we shall wish only to evaluate the results for even *n*. Thus for *n*=3,For *n*=4 we have that and , and there are no other classes without an *S*. Hence we can writeMore generally, we wish to evaluate . To do this, we first note some obvious features of the algebraic structure.(4.2)(4.3)(4.4)This is a natural adjoint structure. (Indeed, we have only used the distinct letters *R*, *L* for the sake of greater legibility.) As this structure suggests, will turn out to have a natural interpretation as linear *operators*. First, we need to extend the notation, by defining to be and more generally to be

Then, rather less obviously, there are *commutator* rules. In what follows, we write [*A*,*B*] for the commutator *AB*−*BA*. Then(4.5)To establish the first of these relations, we shall show that for any *X*, *Y*, the class *XRLY* is in one-to-one correspondence with the union of the classes *XLRY* and *XSY*. We will suppose that *X* is of length *m* and that the total length of *XLRY* is *n*.

As a lemma, let us note that the condition *Z*(*m*+1)=*L* implies that *π*^{−1}(*m*+1), *π*^{−1}(*m*+2) cannot be adjacent. For if they were *q*, *q*±1, then we should have contradicting *Z*(*m*+1)=*L*.

Now consider the class *XLRY*. From the lemma, *π*^{−1}(*m*+1), *π*^{−1}(*m*+2) are not adjacent. Define the permutation *π*′ byFor *k* other than *m*+1, *m*+2, we have and . Thus, for these values, all the inequalities and so *Z*(*k*) are unchanged. For the same reason (and using the non-adjacency), *R* and *L* are interchanged for *m*+1, *m*+2. Thus *π*′ is in *XRLY*.

Now consider the class *XRLY*. If *π*^{−1}(*m*+1), *π*^{−1}(*m*+2) are not adjacent, then in similar manner, it corresponds to an element of *XLRY*. Thus the class *XLRY* is in one-to-one correspondence with a subset of *XRLY*. The remaining elements of *XRLY* are those in which *π*^{−1}(*m*+1), *π*^{−1}(*m*+2) *are* adjacent. But these have a one-to-one correspondence with the elements of *XSY*. Explicitly, we can map the pair (*m*+1, *m*+2) to *m*+1 and renumber the elements of *Y* to run from *m*+2 to *n*−1. This establishes that *XRLY* is in one-to-one correspondence with the union of the classes *XLRY* and *XSY*, and henceThis holds for all *X*, *Y* and so gives the commutation relation.

As illustration, take *m*=1, *X*=*R*, *Y*=*L*. The four elements of *RRLL* are (2413), (2314), (1423), (1324). Of these, only the first has non-adjacent *π*^{−1}(2)=1, *π*^{−1}(3)=4. Transposing 2 and 3 yields the permutation (3412), which is indeed the only element of *RLRL*. The remaining three correspond via (23)→2, 4→3 to the three elements (213), (132), (123) of *RSL*.

The proofs for the other commutation relations are analogous. These relations are the vital features of this new classification of permutations, on which the ensuing discussion rests.

First we derive some useful corollaries.(4.6)and(4.7)These rules make the evaluation of any particular class size into a simple algorithm. For example, with *n*=6, we may computeand so *E*_{6}, the total number of permutations with the zigzag property, is 61. But the total number of classes to be considered is given by the *Catalan number*This is the number of paths of length *n* on the non-negative integers, beginning and ending at 0. This grows similar to 2^{n} and so does not give an efficient method when we do not need the sizes of individual classes, but only the sum . To find such an efficient method, we need only to take further the idea of *R*, *L* and *S* as operators by finding matrix representations for them.

## 5. A matrix calculus for the secant numbers

We shall realize these operators as (unbounded) linear operators on an infinite-dimensional Hilbert space. For reasons that will appear later, we take orthonormal basis states labelled as . For even *n*, define(5.1)It may easily be verified that *R* and *L* are adjoint operators, and *S* a self-adjoint operator, satisfying the desired commutation relations. Moreover, the orthonormality ensures that what we have previously called the norm |*X*| is identical with the Hermitian product , and, in particular, that for even *n* the total number of permutations with the zigzag property is given by(5.2)The matrix (*R*+*L*) is bidiagonal, i.e. it has non-vanishing elements only on the two diagonals just above and just below the principal diagonal. Thus, the calculation of its *n*th power does not require the complexity of general matrix multiplication, and in fact can readily be represented by a recursive scheme like that of a Pascal triangle.

The secant numbers now appear in the left-hand column. This method of generating them can be written as a very simple algorithm needing only *O*(*n*^{2}) multiplications or *O*(*n*^{3}) additions for *E*_{n}.

There are also nonlinear relationships which are readily described in this formalism, for example(5.4)gives, for *k*=8 and *p*=2, 3, 4, respectively,The last of these relationships, giving the secant number as a sum of squares, is of particular interest because it comes from the symmetry of the number triangle under vertical reflection.

At this point, those familiar with operators in quantum mechanics will expect to see *R* and *L* reduced to more primitive creation and annihilation operators, but we postpone doing this until the parallel algebra for the tangent numbers has been set out.

## 6. Counting zigzag permutations: the tangent case

We now give a different zigzag classification *Z*′ of the permutations on *n* elements.(6.1)Note that *Z*′(1) is always *R*′ and so is redundant. The *tangent zigzag class* consists of the sequence . For odd *n*, the zigzag permutations are those without an *S*′ in the class.

We shall again apply this classification to all permutations even though we shall only evaluate the tangent zigzag class sizes for odd *n*.

For *n*=3, (132), (231) are of class *R*′*L*′ and the rest are in *S*′*S*′.

For *n*=4, (1342), (1423), (1432), (2341), (2413), (2431), (3142), (3241) are in *R*′*S*′*L*′; (1243), (2143), (3412), (3421) are in *S*′*R*′*L*′; (1324), (2314), (4132), (4231) are in *R*′*L*′*S*′; and the remaining eight are in *S*′*S*′*S*′.

The algebra is similar to the secant case, except that while we had |*S*|=1, we find |*S*′|=2 as both (12) and (21) are of type *S*′. The analogues of properties (4.2)–(4.5) hold, and in particular we have the vital commutator relation(6.2)We now have the corollaries,(6.3)and(6.4)This algebra can be realized on a Hilbert space by taking orthonormal states labelled by and then identifying *R*′, *L*′, *S*′ with operations *R*, *L*, *S* on these odd-numbered states by(6.5)Again the matrix (*R*+*L*)^{n} is bidiagonal, and hence the calculation of can be simplified into a recursive scheme as follows:

The tangent numbers appear in the left-hand column. This is essentially the same scheme as that given and refined by Knuth & Buckholtz (1967).

In this case, the entries in the table are not the values of , but are modified by a factor . Thus, the identity(6.7)yields, for *k*=8 and *p*=4, 3, 2, respectively,

## 7. The duality of tangent and secant numbers

It is a remarkable fact that the operators (*R*, *L*, *S*), (*R*′, *L*′, *S*′) can naturally be factorized into simpler operators, although these new operators do not have any obvious meaning in terms of the permutations on which (*R*, *L*, *S*), (*R*′, *L*′, *S*′) were originally defined.

To do this, we define adjoint operators *A*, *A*^{†} such that(7.1)Then for odd *n*, but for even *n*. The definitions(7.2)then give all the correct properties for (*R*, *L*, *S*) on even states. When applied to odd states, they correctly correspond to (*R*′, *L*′, *S*′).

Note that on even states (and (*R*′+*L*′+*S*′) on odd states) so(7.3)The proportion of permutations with the zigzag property may be written as(7.4)in the secant and tangent cases, respectively.

This factorization is not a purely formal device, because it gives rise to non-obvious and non-trivial relationships between permutation classes of the different types. For instance, we may show purely by this operator calculus that there are eight times as many permutations of eight elements of type *S*′*R*′*R*′*S*′*L*′*L*′*S*′ as there are permutations on six elements of type *RRRLLL*. (The numbers are in fact 288 and 36, respectively.) The demonstration runs as follows:The existence of this factorization structure clearly suggests that the tangent and secant series should be unified into a single scheme, rather than being seen as two independent structures. We have anticipated this idea in the use of even-numbered states for the secant series and odd-numbered states for the tangent series. This unification can naturally be expressed by another feature borrowed from quantum mechanics, namely the specification of an operator satisfying anticommutation relations to map odd to even states and vice versa.

We define *U* by(7.5)Then *U* and *U*^{†} have anticommutation relations(7.6)The commutator [*U*^{†},*U*] is Hermitian and satisfies(7.7)We also have the anticommutation relations(7.8)Now the commutation relations for *A* and *A*^{†} can be given as follows:(7.9)The underlying symmetry between the secant and tangent numbers revealed by the operator methods is a surprising result which deserves further study.

In a further paper (Sukumar & Hodges 2007), we study these non-standard commutation relations from a physical point of view. We find that the classification of permutations by their zigzag classes has an analogue in the classification of *transpositions*. Combined with some simple graph-theoretic ideas, this has a direct relationship to states arising in quantum optics. The reader is referred to this complementary paper for a discussion of this connection.

## Acknowledgments

The authors would like to thank referees for their helpful remarks on how best to present the foregoing observations.

## Footnotes

- Received May 24, 2007.
- Accepted June 14, 2007.

- © 2007 The Royal Society