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, 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

0,5

Comments

See A318810 for a definition of necklace permutation.

References

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

Links

Andrew Howroyd, Table of n, a(n) for n = 0..2713 (rows 0..20)

Math StackExchange, Marko Riedel et. al, Free circular permutations

Marko Riedel, Maple code for sequence by PET and closed form.

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

Example

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,1
  2,1,1
  6,3,2,1,1
  24,12,6,4,2,1,1

Prog

(PARI)
C(sig)={my(n=vecsum(sig)); if(n==0, 1, 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

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

Sequence in context: A284308 A369435 A172400 * A226691 A158389 A186287

Adjacent sequences: A380398 A380399 A380400 * A380402 A380403 A380404

Keyword

nonn,tabf

Author

Marko Riedel, Jan 23 2025

Extensions

a(0)=1 prepended by Andrew Howroyd, Nov 18 2025

Status

approved