[Information Index] [Generation Index] [COS homepage]

Information on Genocchi Numbers and Dumont Permutations

The Genocchi numbers, g1,g2,... can be defined in a number of different ways. There is a recurrence relation (with g1 = 1)

gn   =  
__
\
/   
i > 0
(-1)i ( n
2i
) gn-i.

The absolute value of the coefficient of the x2n/(2n)! term in the exponential generating function shown below is gn.

2x

ex+1
  =     x   -   1
x2

2!
  +   1
x4

4!
  -   3
x6

6!
  +   17
x8

8!
  -   155
x10

10!
  +   · · ·

The first 15 Genocchi numbers are: 1, 1, 3, 17, 155, 2073, 38227, 929569, 28820619, 1109652905, 51943281731, 2905151042481, 191329672483963, 14655626154768697, 1291885088448017715. This is sequence A001469(M3041) in Neil J. Sloane's database of integer sequences.

Dominique Dumont showed that certain classes of permuations are counted by the Genocchi numbers. Dumont showed that the (n + 1)st Genocchi number is the number of permutations of [2n] with the following properties:

  1. each even integer must be followed by a smaller integer. (This rule disallows the sequence from ending with an even integer)
  2. each odd integer is either followed by a larger integer or is final in the sequence.
We call these Dumont permutations of the first kind. Dumont defined another type of permutation of [2n] and showed that they are also counted by the Genocchi numbers. These permutations p[1..2n] have the following properties and are called the Dumont permutations of the second kind.
  1. For an even position i, the value of p[i] is less than i.
  2. For an odd position i, the value of p[i] is at least i.
The table below shows all 17 permutations of both types for n=3. It is these permutations that are output by COS.

    First Kind         Second Kind    
2 1 4 3 6 5 4 1 5 2 6 3
2 1 5 6 4 3 3 1 5 2 6 4
2 1 6 4 3 5 5 1 4 2 6 3
3 4 2 1 6 5 3 1 4 2 6 5
3 5 6 4 2 1 5 1 3 2 6 4
3 6 4 2 1 5 4 1 3 2 6 5
4 2 1 3 6 5 4 1 5 3 6 2
4 2 1 5 6 3 2 1 5 3 6 4
4 2 1 6 3 5 5 1 4 3 6 2
4 3 5 6 2 1 2 1 4 3 6 5
4 3 6 2 1 5 4 1 6 2 5 3
5 6 2 1 4 3 3 1 6 2 5 4
5 6 3 4 2 1 6 1 4 2 5 3
5 6 4 2 1 3 6 1 3 2 5 4
6 2 1 4 3 5 4 1 6 3 5 2
6 3 4 2 1 5 2 1 6 3 5 4
6 4 2 1 3 5 6 1 4 3 5 2

References


Programs available:
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
[Error Opening Counter File -- Click for more info]
©Frank Ruskey, 1995-2003.