login
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].
6

%I #10 Jan 28 2013 04:25:36

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

%T 5040,2520,840,210,42,7,1,1,40320,20160,6720,1680,336,56,8,1,1,362880,

%U 181440,60480,15120,3024,504,72,9,1,1

%N 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].

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

%C 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.

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

%C 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.

%C The row sums of this triangle are given by A213937.

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

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

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

%e n\k 1 2 3 4 5 6 7 8 9 10 ...

%e 1 1

%e 2 1 1

%e 3 2 1 1

%e 4 6 3 1 1

%e 5 24 12 4 1 1

%e 6 120 60 20 5 1 1

%e 7 720 360 120 30 6 1 1

%e 8 5040 2520 840 210 42 7 1 1

%e 9 40320 20160 6720 1680 336 56 8 1 1

%e 10 362880 181440 60480 15120 3024 504 72 9 1 1 ...

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

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

%e 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.

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

%K nonn,easy,tabl

%O 1,4

%A _Wolfdieter Lang_, Jul 10 2012