A212359 -id:A212359 - cp's OEIS frontend

A213935 Triangle with entry a(n,m) giving the total number of necklaces of n beads (C_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

1, 2, 1, 3, 6, 2, 4, 24, 36, 6, 5, 60, 300, 240, 24, 6, 180, 1820, 3900, 1800, 120, 7, 378, 9030, 42000, 50400, 15120, 720, 8, 952, 40824, 357420, 882000, 670320, 141120, 5040, 9, 2088, 169512, 2610720, 11677680, 17781120, 9313920, 1451520, 40320, 10, 4770, 673560, 17193960, 128598624, 345144240, 355622400, 136080000, 16329600, 362880

Offset: 1

Wolfdieter Lang, Jun 27 2012

This triangle is obtained from the array A212360 by summing in the row number n, for n>=1, all entries related to partitions of n with the same number of parts m.
a(n,m) is the total number of necklaces of n beads (C_n symmetry) corresponding to all the color multinomials obtained from all p(n,m)=A008284(n,m) partitions of n with m parts, written in nonincreasing form, by 'exponentiation'. Therefore only m from the available n colors are present, and a(n,m) gives the number of necklaces with n beads with only m of the n available colors present, for m from 1,2,...,n, and n>=1. All of the possible color assignments are counted.
See the comments on A212359 for the Abramowitz-Stegun (A-St) order of partitions, and the 'exponentiation' to obtain multisets, used to encode color multinomials, from partitions.
The row sums of this triangle coincide with the ones of array A212360, and they are given by A056665.

			n\m 1    2      3       4       5       8      7     8 ...
1   1
2   2    1
3   3    6      2
4   4   24     36       6
5   5   60    300     240      24
6   6  180   1820    3900    1800     120
7   7  378   9030   42000   50400   15120     72
8   8  952  40824  357420  882000  670320 141120  5040
...
Row n=9:   9 2088 169512 2610720 11677680 17781120 9313920 1451520 40320.
Row n=10: 10 4770 673560 17193960 128598624 345144240 355622400 136080000 16329600 362880.
a(2,2)=1 from the color monomial c[1]^1*c[2]^1= c[1]*c[2] (from the m=2 partition [1,1] of n=2). The necklace in question is cyclic(12) (we use j for color c[j] in these examples).
a(5,3) = 120 + 180 = 300, from A212360(5,4) + A212360(5,5), because k(5,3,1)=4 and p(5,3)=2.
a(3,1) = 3 from the color monomials c[1]^3, c[2]^3 and c[3]^1. The three necklaces are cyclic(111), cyclic(222) and cyclic(333).
In general a(n,1)=n from the partition [n] providing the color signature (exponent), and the n color choices.
a(3,2) = 6 from the color signature c[.]^2 c[.]^1, (from the m=2 partition [2,1] of n=3), and there are 6 choices for the color indices. The 6 necklaces are cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).
a(3,3) = 2. The color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). All three available colors are used. There are two non-equivalent necklaces: cyclic(1,2,3) and cyclic(1,3,2).
a(4,2) = 24 from two color signatures c[.]^3 c[.] and c[.]^2 c[.]^2 (from the two m=2 partitions of n=4: [3,1] and [2,2]). The first one produces 4*3=12 necklaces, namely 1112, 1113, 1114, 2221, 2223, 2224, 3331, 3332, 3334, 4441, 4442 and 4443 all taken cyclically. The second color signature leads to another 2*6=12 necklaces: 1122, 1133, 1144, 2233, 2244, 3344, 1212, 1313, 1414, 2323, 2424 and 3434, all taken cyclically. Together they provide the 24 necklaces counted by a(4,2).

Cf. A212360, A056665 (row sums). A075195 (another necklace table).

a(n,m) = Sum_{j=1..p(n,m)}A212360(n,k(n,m,1)+j-1), with k(n,m,1) the position where in the list of partitions of n in A-St order the first with m parts appears, and p(n,m) the number of partitions of n with m parts shown in the array A008284. E.g., n=5, m=3: k(5,3,1)=4, p(5,3)=2.

A339677 Partition array: T(n, k) is the number of aperiodic necklaces (Lyndon words) on a multiset of colored beads (of size n) whose color multiplicities form the k-th partition of n in Abramowitz-Stegun order.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 1, 3, 6, 0, 1, 2, 4, 6, 12, 24, 0, 1, 2, 3, 5, 10, 14, 20, 30, 60, 120, 0, 1, 3, 5, 6, 15, 20, 30, 30, 60, 90, 120, 180, 360, 720, 0, 1, 3, 7, 8, 7, 21, 35, 51, 70, 42, 105, 140, 210, 312, 210, 420, 630, 840, 1260, 2520, 5040, 0, 1, 4, 9, 14, 8, 28, 56, 70, 84, 140

Offset: 1

Álvar Ibeas, Dec 12 2020

As in A212359, A072605, and A261600, for each partition, the base set of beads is fixed.

Abuse of notation: we write T(n, L) for T(n, k), where L is the k-th partition of n in A-St order. We do accordingly for A036038 and A212359.

			Array begins:
  k:  1 2 3 4 5  6  7  8  9 10  11  12  13  14  15
      --------------------------------------------
n=1:  1
n=2:  0 1
n=3:  0 1 2
n=4:  0 1 1 3 6
n=5:  0 1 2 4 6 12 24
n=6:  0 1 2 3 5 10 14 20 30 60 120
n=7:  0 1 3 5 6 15 20 30 30 60  90 120 180 360 720
Consider partition L = (4, 2). There are 3 = A212359(6, L) necklaces on the bead set {a^4, b^2}: (aaaabb), (aaabab), and (aabaab). The latter has a period smaller than its size (3 < 6), whereas the other two are aperiodic. Hence, T(6, L) = 2.
T(n, (1,...,1)) = A212359(n, (1,...,1)) = (n-1)!, counting necklaces with n beads, each in a different color.

Álvar Ibeas, First 25 rows, flattened

Cf. A036035, A036038, A072605, A185974, A212359, A261600 (row sums), A298941, A318808.

C(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
Row(n)=[C(Vec(p)) | p<-partitions(n)]
for(n=1, 7, print(Row(n))) \\ Andrew Howroyd, Dec 14 2020

Let L be a partition of n and d be the gcd of its parts. Then,
T(n, L) = n^(-1) * Sum_{v|d} mu(v) * A036038(n/v, L/v), where L/v is the partition obtained from L after dividing each part by v.
T(n, L) = Sum_{v|d} mu(v) * A212359(n/v, L/v).
T(n, L) = n^(-1) * A036038(n, L) - Sum_{1T(n,k) = A298941(A036035(n,k)) = A318808(A185974(n,k)). - Andrew Howroyd, Dec 14 2020

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.

Original entry on oeis.org

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

Marko Riedel, Jan 23 2025

See A318810 for a definition of necklace permutation.

			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

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

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

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

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

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

A213937 Row sums a(n) of triangle A213936: number of representative necklaces with n beads (C_N symmetry) corresponding to all color signatures given by the partitions [1^n], [2,1^(n-2)], ..., [n-1,1], [n].

Original entry on oeis.org

1, 2, 4, 11, 42, 207, 1238, 8661, 69282, 623531, 6235302, 68588313, 823059746, 10699776687, 149796873606, 2246953104077, 35951249665218, 611171244308691, 11001082397556422, 209020565553572001

Offset: 1

Wolfdieter Lang, Jul 10 2012

See A213936 and A212359 for more details, references and links.

			n=4: the representative necklaces (of a color class) correspond to the color signatures c[.] c[.] c[.] c[.], c[.]^2 c[.] c[.], c[.]^3 c[.]^1 and c[.]^4 (the reverse partition order compared to Abramowitz-Stegun without 2^2). The corresponding necklaces are (we use j for color c[j]): cyclic(1234), coming in all-together 6  permutations of the present colors, cyclic(1123) coming in 3 permutions, cyclic(1112) and cyclic(1111), adding up to the 11 = a(4) necklaces. Not all 4 colors are present, except for the first signature (partition).

Cf. A002627, A231936, A248669.

a(n) = A002627(n-1) + 1, n>=1.
a(n) = Sum_{k=1..n} A213936(n,k), n>=1.
a(n) = 1 + Sum_{k=1..n-1} (n-1)!/k! = 1 + A002627(n-1), n>=1.
a(n) = 1 + Sum_{k=1..n} A248669(n-1,k), n>=1. - Greg Dresden, Mar 31 2022

Previous Showing 11-14 of 14 results.

cp's OEIS Frontend

A213935 Triangle with entry a(n,m) giving the total number of necklaces of n beads (C_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A339677 Partition array: T(n, k) is the number of aperiodic necklaces (Lyndon words) on a multiset of colored beads (of size n) whose color multiplicities form the k-th partition of n in Abramowitz-Stegun order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A213937 Row sums a(n) of triangle A213936: number of representative necklaces with n beads (C_N symmetry) corresponding to all color signatures given by the partitions [1^n], [2,1^(n-2)], ..., [n-1,1], [n].

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula