[seqfan] suggest comment for A000085 (Involutions)

Joerg Arndt arndt at jjj.de
Wed Jun 24 09:42:04 CEST 2009

Number of ballot sequences (or lattice permutations) of length n.
A ballot sequence B is a string such that, for all prefixes P of B,
h(i)>=h(j) for i<j, where h(x) is the number of times x appears in P.
For example, the ballot sequences of length 4 are
1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1231, and 1234.
The string 1221 does not appear in the list because in the
3-prefix 122 there are two 2s but only one 1.

Cf. p.176 of Bruce E. Sagan: "The Symmetric Group"

P.S.: I never heard the term "lattice permutation" before.

More information about the SeqFan mailing list