A213936 Number triangle with entry a(n,k), n>=1, m=1, 2, ..., n, giving the number of representative necklaces with n beads (C_n symmetry) corresponding to the color multinomial c[1]^k*c[2]*...*c[n+1-k].

1, 1, 1, 2, 1, 1, 6, 3, 1, 1, 24, 12, 4, 1, 1, 120, 60, 20, 5, 1, 1, 720, 360, 120, 30, 6, 1, 1, 5040, 2520, 840, 210, 42, 7, 1, 1, 40320, 20160, 6720, 1680, 336, 56, 8, 1, 1, 362880, 181440, 60480, 15120, 3024, 504, 72, 9, 1, 1

Offset: 1

Author

Wolfdieter Lang, Jul 10 2012

Keywords

• nonn
• easy
• tabl

Comments

This table coincides with A173333 but has an extra main diagonal with entries 1.

a(n,k) is the number of necklaces of n beads (C_N symmetry), with colors from the repertoire {c[1],c[2],...,c[n]}, corresponding to the representative color multinomials obtained from the partition [k,1^(n-k)] of n with m=n-k+1 parts by 'exponentiation' (taking the parts in the given order as exponents of the colors), hence only m from the available n colors are present. As representative necklaces one takes the ones where the color c[1] appears k times. In particular, for k=1 the partition is [1^n] and all n colors are used, and there are (n-1)! necklaces from permuting the n colors.

a(n,k) appears in the representative necklace partition array A212359 in row n at the position l(n,n+1-k,1), with l(n,m,1) the position of the first partition with m parts in the list of partitions of n in A-St order. E.g., n=5, k=4: l(5,5-3,1) =2 with the partition [4,1] (used in reverse order compared to A-St).

See the comments on A212359 for the Abramowitz-Stegun (A-St) reference, and the 'exponentiation' to obtain multisets, used to encode color multinomials, from partitions.

The row sums of this triangle are given by A213937.

Examples

			n\k      1       2      3      4     5    6   7  8  9 10 ...
1        1
2        1       1
3        2       1      1
4        6       3      1      1
5       24      12      4      1     1
6      120      60     20      5     1    1
7      720     360    120     30     6    1   1
8     5040    2520    840    210    42    7   1  1
9    40320   20160   6720   1680   336   56   8  1  1
10  362880  181440  60480  15120  3024  504  72  9  1  1 ...
a(4,3) = 1 because  the partition is [3,1], the color signature (exponentiation) c[.]^3 c[.]^1, and the one representative necklace (we use j for color c[j] here) is: cyclic(1112).
a(4,2) = 3  because  the partition is [2,1^2], the color signature c[.]^2 c[.] c[.], and the three representative necklaces are: cyclic(1123), cyclic(1132) and cyclic(1213).
a(5,3) = 4  because the color signature is  c[.]^3 c[.] c[.]  (from the partition [3,1^2]). and the four representative necklaces are 11123, 11132, 11213 and 11312, all taken cyclically.
		

Crossrefs

Cf. A212359, A213937 (row sums). For columns and diagonals see the links under A173333 (after an additional 1 has been supplied for each columns).

Formula

a(n,n)=1, a(n,k) = (n-1)!/k! if 1 <= k < n, else 0.

See also A212359 with a link for the formula for general partitions.

a(n,k) = A173333(n-1,k), 1 <= k < n.