A120061 Number of universal cycles for permutations of n objects.

1, 3, 384, 7044820107264000, 43717045185341789547924740349079734434493871700606561180430383632613376000000000000000000000000000000000

Offset

2,2

Comments

A universal cycle of permutations is a cycle of n! digits such that each permutation of {1,...,n} occurs exactly once as a block of n-1 consecutive digits (with its redundant final element suppressed). a(4)=2^7*3, a(5)=2^33*3^8*5^3, a(6)=2^190*3^49*5^33, a(7)=2^1217*3^123*5^119*7^5*11^28*43^35*73^20*79^21*109^35 ~=1.582284037*10^747.

References

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2, Generating All Tuples and Permutations. Ch. 7.2.1.2, Exercises 111 and 112, Page 75 and Answer to Exercise 112, pages 120-121.

Links

Table of n, a(n) for n=2..6.

Dawn Curtis, Taylor Hines, Glenn Hurlbert, Tatiana Moyer, Near universal cycles for subsets exist, arXiv:0809.3725 [math.CO], 22 Sep 2008, arXiv:0809.3725v1 [math.co] 3 November 2018.

Brad W. Jackson, Universal cycles of k-subsets and k-permutations, Discrete Math. 117 (1993), no. 1-3, 141-150.

Example

(121323) is a universal cycle of permutations for n=3,
(123124132134214324314234) is one for n=4.

Crossrefs

Cf. A005563.

Sequence in context: A317730 A193131 A193154 * A187942 A244670 A199146

Adjacent sequences: A120058 A120059 A120060 * A120062 A120063 A120064

Keyword

nonn

Author

Hugo Pfoertner, Jun 06 2006

Status

approved