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

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.

Links

Table of n, a(n) for n=1..55.

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.

Example

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

Sequence in context: A201922 A181644 A144351 * A142589 A284308 A369435

Adjacent sequences: A213933 A213934 A213935 * A213937 A213938 A213939

Keyword

nonn,easy,tabl

Author

Wolfdieter Lang, Jul 10 2012

Status

approved