A095988 Number of Gray codes for partitions of n.

1, 1, 1, 1, 3, 1, 52, 652, 298896, 2291100484

Offset

1,5

Comments

List the partitions of n and form a graph where two partitions are connected if one can be transformed into the other by adding 1 from one element, subtracting 1 from another element and rearranging (if necessary). A Gray code corresponds to a Hamiltonian path through all of the partitions.

Terms a(6) through a(10) are given in the Knuth reference.

References

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.4.

Links

Table of n, a(n) for n=1..10.

Example

The partitions of the integer 6 are 111111, 21111, 3111, 2211, 222, 321, 33, 42, 411, 51, 6. Each term is obtained from the previous term by adding 1 to one element, subtracting 1 from another element and rearranging. This is the only way to do it for 6, so a(6)=1.

Crossrefs

Sequence in context: A133104 A322730 A292425 * A189898 A082525 A162221

Adjacent sequences: A095985 A095986 A095987 * A095989 A095990 A095991

Keyword

hard,nonn

Author

Jud McCranie, Jul 18 2004

Status

approved