login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A213940 Triangle with entry a(n,m) giving the number of bracelets of n beads (dihedral D_n symmetry) with n colors available for each bead, but only m distinct fixed colors, say c[1],...,c[m], are present, with m from {1,...,n} and n>=1. 9
1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 3, 6, 6, 12, 1, 7, 20, 26, 30, 60, 1, 8, 40, 93, 150, 180, 360, 1, 18, 106, 424, 633, 1050, 1260, 2520, 1, 22, 304, 1180, 3260, 5040, 8400, 10080, 20160, 1, 46, 731, 4844, 16212, 29244, 45360, 75600, 90720, 181440 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

This triangle is obtained from the partition array A213939 by summing in row n, for n>=1, all entries related to partitions of n with the same number of parts m.

a(n,m) is the number of bracelets of n beads (dihedral D_n symmetry) corresponding to the representative color multinomials obtained from all partitions of n with m parts by 'exponentiation', hence only m from the available n colors are present. As a representative multinomial of each of the p(n,m)=A008284(n,m) such m-color classes we take the one where the considered m part partition of n, [p[1],...,p[m]], written in nonincreasing order, is distributed as exponents on the color indices like c[1]^p[1]*...*c[m]^p[m]. That is only the first m colors from the n available ones are involved.

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 A213939, and they are given by A213943.

Number of n-length bracelets w over a k-ary alphabet {a1,a2,...,ak} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 1, where #(w,x) counts the letters x in word w (bracelet analog of A226874). - Andrew Howroyd, Sep 26 2017

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

FORMULA

a(n,m) = Sum_{j=1..p(n,m)}A213939(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) is 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.

EXAMPLE

n\m  1  2   3    4     5     6     7     8     9     10 ...

1    1

2    1  1

3    1  1   1

4    1  3   2    3

5    1  3   6    6    12

6    1  7  20   26    30    60

7    1  8  40   93   150   180   360

8    1 18 106  424   633  1050  1260  2520

9    1 22 304 1180  3260  5040  8400 10080 20160

10   1 46 731 4844 16212 29244 45360 75600 90720 181440

...

a(5,3) = 2 + 4 = 6, from A213939(5,4) + A213939(5,5), because k(5,3,1) = 4 and p(5,3) = 2.

a(2,1) = 1 because the partition [2] of n=2 with part number m=1 corresponds to the representative color multinomial (here monomial) c[1]^2 = c[1]*c[1], and there is one such representative bracelet. There is another bracelet color monomial in this class of n=2 colors where only m=1 color is active: c[2]*c[2]. See the triangle entry A213941(2,1)=2. The same holds for the necklace case.

a(3,1) = 1 from the color monomial representative c[1]^3. This class has 2 other members: c[2]^3 and c[3]^3. See A213941(3,1)=3. The same holds for the necklace case.

Like in the necklace case one has in general a(n,1)=1 and A213941(n,1) = n from the partition [n] providing the color signature and a representative c[1]^n.

a(3,2) = 1 from the representative color multinomial c[1]^2*c[2] (from the m=2 partition [2,1] of n=3) leading to just one representative bracelet (and necklace) cyclic(112) (when one uses j for color c[j]). The whole class consists of A213941(3,2)=6 bracelets (or necklaces): cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).

a(3,3) = 1. The representative color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). There is only one bracelet cyclic(1,2,3) which constitutes already the whole class (A213941(3,3)=1). The necklace cyclic(1,3,2) becomes equivalent under D_3.

a(4,2) = 3 from two representative color multinomials c[1]^3*c[2] and c[1]^2*c[2]^2 (from the two m=2 partitions of n=4: [3,1] and [2,2]). The first one has one representative bracelet, namely cyclic(1112), the second one leads to the two representative bracelets: cyclic(1122) and cyclic(1212). Together these are the 3 bracelets counted by a(4,2). The first color class c[.]^3*c[.] consists of 4*3=12 bracelets, when all 4 colors are used. The second one consists of 2*6=12 bracelets. Together they sum up to the 24 bracelets counted by A213941(4,2). In this example the necklace case does not differ from the bracelet one.

PROG

(PARI)

Cyc(v)={my(s=vecsum(v)); sumdiv(gcd(v), d, eulerphi(d)*(s/d)!/prod(i=1, #v, (v[i]/d)!))/s}

CPal(v)={my(odds=#select(t->t%2, v), s=vecsum(v));  if(odds>2, 0, ((s-odds)/2)!/prod(i=1, #v, (v[i]\2)!))}

T(n, k)={my(t=0); forpart(p=n, t+=Cyc(Vec(p))+CPal(Vec(p)), [1, n], [k, k]); t/2}

for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Sep 26 2017

(PARI) \\ faster version; here U is A226874 as vector of polynomials.

U(n)={Vec(serlaplace(prod(k=1, n, 1/(1-y*x^k/k!) + O(x*x^n))))}

T(n)={my(t=U(n)); vector(n, n, vector(n, k, ((1/n)*sumdiv(n, d, eulerphi(n/d) * polcoeff(t[d+1], k)) + if(n%2, sum(d=0, (n-1)/2, binomial((n-1)/2, d)*polcoeff(t[d+1], (k-1))), polcoeff(t[n/2+1], k) + sum(d=0, n/2-1, binomial(n/2-1, d)*(2^d + if(d%2, 0, binomial(d, d/2)))*polcoeff(t[n/2-d], k-2))/2))/2))}

{ my(t=T(10)); for(n=1, #t, print(t[n])) } \\ Andrew Howroyd, Dec 22 2017

CROSSREFS

Columns k=2..5 are A213942, A214307, A214309, A214311.

Cf. A008284, A213939, A213941, A213943 (row sums), A226874, A152176.

Cf. A213934 (cyclic symmetry).

Sequence in context: A046818 A177462 A106584 * A236027 A220128 A131498

Adjacent sequences:  A213937 A213938 A213939 * A213941 A213942 A213943

KEYWORD

nonn,tabl

AUTHOR

Wolfdieter Lang, Jul 20 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 15 21:16 EST 2018. Contains 318154 sequences. (Running on oeis4.)