A120061 Number of universal cycles for permutations of n objects.

1, 3, 384, 7044820107264000, 43717045185341789547924740349079734434493871700606561180430383632613376000000000000000000000000000000000

Offset: 2

Author

Hugo Pfoertner, Jun 06 2006

Keywords

• nonn

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.

Examples

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

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

• 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.

Crossrefs

Cf. A005563.