A380401 Triangle read by rows: T(n,k) is the number of necklace permutations of a multiset whose multiplicities are given by the k-th partition of n in graded reflected lexicographic order.

1, 1, 1, 2, 1, 1, 6, 3, 2, 1, 1, 24, 12, 6, 4, 2, 1, 1, 120, 60, 30, 16, 20, 10, 4, 5, 3, 1, 1, 720, 360, 180, 90, 120, 60, 30, 20, 30, 15, 5, 6, 3, 1, 1, 5040, 2520, 1260, 630, 318, 840, 420, 210, 140, 70, 210, 105, 54, 35, 10, 42, 21, 7, 7, 4, 1, 1, 40320, 20160, 10080, 5040, 2520, 6720, 3360, 1680, 840, 1120, 560, 188, 1680, 840, 420, 280, 140, 70, 336, 168, 84, 56, 14, 56, 28, 10, 8, 4, 1, 1

Offset: 1

Author

Marko Riedel, Jan 23 2025

Keywords

• nonn
• tabf

Comments

See A318810 for a definition of necklace permutation.

Examples

			The ordering of the partitions used here is graded reflected lexicographic illustrated below with n=5:
  1,1,1,1,1 => 24
  1,1,1,2 => 12
  1,2,2 => 6
  1,1,3 => 4
  2,3 => 2
  1,4 => 1
  5 => 1
Table begins:
  1
  1,1
  2,1,1
  6,3,2,1,1
  24,12,6,4,2,1,1
		

References

• F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, pages 36-37, 42-43.

Links

• Math StackExchange, Marko Riedel et. al, Free circular permutations
• Marko Riedel, Maple code for sequence by PET and closed form.

Crossrefs

Cf. A000041 (row lengths), A072605 (row sums), A080576 (graded reflected lexicographic order), A212359 (similar triangle for Abramowitz-Stegun order), A318810, A334434, A214609 (up to rotations and reflections).

Programs

PARI

C(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, eulerphi(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
Row(n)={apply(C, vecsort([Vecrev(p) | p<-partitions(n)]))} \\ Andrew Howroyd, Jan 23 2025

Formula

For a distribution of colors n1+n2+...+nm = n the number of necklaces is (1/n)*Sum_{d|gcd(n1,n2,...,nm)} phi(d) (n/d)!/Prod_{q=1..m} (nq/d)!

T(n,k) = A318810(A334434(n,k)).