A056283 -id:A056283 - cp's OEIS frontend

A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

1, 1, 1, 1, 2, 2, 1, 4, 9, 6, 1, 6, 30, 48, 24, 1, 12, 91, 260, 300, 120, 1, 18, 258, 1200, 2400, 2160, 720, 1, 34, 729, 5106, 15750, 23940, 17640, 5040, 1, 58, 2018, 20720, 92680, 211680, 258720, 161280, 40320, 1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880

Offset: 1

Philippe Deléham

Equivalently, T(n,k) is the number of sequences (words) of length n on an alphabet of k letters where each letter of the alphabet occurs at least once in the sequence. Two sequences are considered equivalent if one can be obtained from the other by a cyclic shift of the letters. Cf. A054631 where the surjective restriction is removed. - Geoffrey Critzer, Jun 18 2013

Robert A. Russell's g.f. for column k >= 1 (in the Formula section below) can be proved by integrating both sides of the formula Sum_{n>=1} S2(n, k)*x^(n-1) = x^(k-1)/((1 - x)* (1 - 2*x) * (1 - 3*x) * ... * (1 - k*x)) w.r.t. x. A variation of this identity (valid for |x| < 1/k) can be found in the Formula section of A008277. - Petros Hadjicostas, Aug 20 2019

			The triangle begins with T(1,1):
  1;
  1,   1;
  1,   2,    2;
  1,   4,    9,     6;
  1,   6,   30,    48,     24;
  1,  12,   91,   260,    300,     120;
  1,  18,  258,  1200,   2400,    2160,     720;
  1,  34,  729,  5106,  15750,   23940,   17640,    5040;
  1,  58, 2018, 20720,  92680,  211680,  258720,  161280,   40320;
  1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880;
  ...
For T(4,2) = 4, the necklaces are AAAB, AABB, ABAB, and ABBB.
For T(4,4) = 6, the necklaces are ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB.

Alois P. Heinz, Rows n = 1..141, flattened

Columns 1-6: A057427, A052823, A056283, A056284, A056285, A056286.
Diagonals: A000142 and A074143.
Row sums: A019536.
Cf. A000010 (Euler totient phi function), A008277 (Stirling2 numbers), A075195 (table of Jablonski).
Cf. A254040, A273891.

with(numtheory):
T:= (n, k)-> (k!/n) *add(phi(d) *Stirling2(n/d, k), d=divisors(n)):
seq(seq(T(n,k), k=1..n), n=1..12);  # Alois P. Heinz, Jun 19 2013

Table[Table[Sum[EulerPhi[d]*StirlingS2[n/d,k]k!,{d,Divisors[n]}]/n,{k,1,n}],{n,1,10}]//Grid (* Geoffrey Critzer, Jun 18 2013 *)

T(n, k) = (k!/n) * sumdiv(n, d, eulerphi(d) * stirling(n/d, k, 2)); \\ Joerg Arndt, Sep 25 2020

T(n,k) = Sum_{i=0..k-1} (-1)^i * C(k,i) * A075195(n,k-i); A075195 = Jablonski's table.
T(n,k) = (k!/n) * Sum_{d|n} phi(d) * S2(n/d, k), where S2(n,k) = Stirling numbers of 2nd kind A008277.
G.f. for column k: -Sum_{d>0} (phi(d)/d) * Sum_{j = 1..k} (-1)^(k-j) * C(k,j) * log(1 - j * x^d). - Robert A. Russell, Sep 26 2018
T(n,k) = Sum_{d|n} A254040(d, k) for n, k >= 1. - Petros Hadjicostas, Aug 19 2019

Formula section edited by Petros Hadjicostas, Aug 20 2019

A294685 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly three colors under translational symmetry, 1 <= k <= n.

Original entry on oeis.org

0, 0, 9, 2, 91, 2022, 9, 738, 43315, 2679246, 30, 5613, 950062, 174184755, 33887517990, 91, 43404, 21480921, 11765865678, 6862930841141, 4169289730628814, 258, 338259, 497812638, 816999710223, 1429469771994078, 2605213713043722909, 4883659745750360600262, 729, 2679228, 11765822365, 57906482267826, 303941554100145501

Offset: 1

Marko Riedel, Nov 06 2017

Colors are not being permuted, i.e., Power Group Enumeration does not apply here.

			Triangle begins:
   0;
   0,     9;
   2,    91,     2022;
   9,   738,    43315,     2679246;
  30,  5613,   950062,   174184755,   33887517990;
  91, 43404, 21480921, 11765865678, 6862930841141, 4169289730628814;
  ...

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..820 (first 40 rows)
Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Main diagonal is A376823.

Cf. A184271, A184284, A294684, A294686, A294687, A294791, A294792, A294793, A294794. T(n,1) is A056283.

T(n,m)=6*sumdiv(n, d, sumdiv(m, e, eulerphi(d) * eulerphi(e) * stirling(n*m/lcm(d,e), 3, 2) ))/(n*m) \\ Andrew Howroyd, Oct 05 2024

T(n,k) = (Q!/(n*k))*(Sum_{d|n} Sum_{f|k} phi(d) phi(f) S(gcd(d,f)*(n/d)*(k/f), Q)) with Q=3 and S(n,k) Stirling numbers of the second kind.

T(n,k) = A184284(n,k) - 3*A184271(n,k) + 3. - Andrew Howroyd, Oct 05 2024

A056296 Number of n-bead necklace structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 18, 43, 126, 339, 946, 2591, 7254, 20125, 56450, 158355, 446618, 1262225, 3580686, 10181479, 29032254, 82968843, 237645250, 682014587, 1960981598, 5647919645, 16292761730, 47069104613, 136166703562, 394418199725, 1143822046786, 3320790074371

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 3 of A152175.

Cf. A000013, A002076, A056283.

Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &], Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
Table[Coefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/n , x, 3], {n, 1, 40}] (* Robert A. Russell, Feb 23 2018 *)
Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#,6], StirlingS2[n/#+2,3] - StirlingS2[n/#+1,3], Divisible[#,3], StirlingS2[n/#+2,3] - 3 StirlingS2[n/#+1,3] + 3 StirlingS2[n/#,3], Divisible[#,2], 2 StirlingS2[n/#+1,3] - 2 StirlingS2[n/#,3], True, StirlingS2[n/#,3]] &],{n, 1, 40}] (* Robert A. Russell, May 29 2018*)
mx = 40; Drop[CoefficientList[Series[-Sum[(EulerPhi[d] / d) Which[ Divisible[d, 6], Log[1 - 3x^d] - Log[1 - 2x^d], Divisible[d, 3] , (Log[1 - 3x^d] - Log[1 - 2x^d] + Log[1 - x^d]) / 2, Divisible[d, 2], (2 Log[1 - 3x^d] - 3 Log[1 - 2x^d]) / 3, True, (Log[1 - 3x^d] - 3Log[1 - 2x^d] + 3 Log[1 - x^d]) / 6], {d, 1, mx}], {x, 0, mx}], x], 1] (* Robert A. Russell, May 29 2018 *)

a(n) = A002076(n) - A000013(n).
From Robert A. Russell, May 29 2018: (Start)
a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 6] * (S2(n/d + 2, 3) - S2(n/d + 1, 3)) + [d==3 mod 6] * (S2(n/d + 2, 3) - 3*S2(n/d + 1, 3) + 3*S2(n/d, 3)) + [d==2 mod 6 | d==4 mod 6] * (2*S2(n/d + 1, 3) - 2*S2(n/d, 3)) + [d==1 mod 6 | d=5 mod 6] * S2(n/d, 3)), where S2(n,k) is the Stirling subset number, A008277.
G.f.: -Sum_{d>0} (phi(d) / d) * ([d==0 mod 6] * (log(1-3x^d) - log(1-x^d)) + [d==3 mod 6] * (log(1-3x^d) - log(1-2x^d) + log(1-x^d)) / 2 + [d==2 mod 6 | d==4 mod 6] * (2*log(1-3x^d) - 3*log(1-2x^d)) / 3 + [d==1 mod 6 | d=5 mod 6] * (log(1-3x^d) - 3*log(1-2x^d) + 3*log(1-x^d)) / 6).
(End)

A056343 Number of bracelets of length n using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 6, 18, 56, 147, 411, 1084, 2979, 8043, 22244, 61278, 171030, 477929, 1345236, 3795750, 10758902, 30572427, 87149124, 248991822, 713096352, 2046303339, 5883433409, 16944543810, 48879769575

Offset: 1

Marks R. Nester

nonn

Turning over will not create a new bracelet.

			For a(4)=6, the arrangements are ABAC, ABCB, ACBC, AABC, ABBC, and ABCC. Only the last three are chiral, their reverses being AACB, ACBB, and ACCB respectively. - _Robert A. Russell_, Sep 26 2018

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Column 3 of A273891.

Equals (A056283 + A056489) / 2 = A056283 - A305542 = A305542 + A056489.

t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1 + k)*k^(n/2))/(2*n), (t1 + n*k^((n + 1)/2))/(2*n)]);
T[n_, k_] := Sum[(-1)^i*Binomial[k, i]*t[n, k - i], {i, 0, k - 1}];
a[n_] := T[n, 3];
Array[a, 26] (* Jean-François Alcover, Nov 05 2017, after Andrew Howroyd *)
k=3; Table[k! DivisorSum[n, EulerPhi[#] StirlingS2[n/#,k]&]/(2n) + k!(StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k])/4, {n,1,30}] (* Robert A. Russell, Sep 26 2018 *)

a(n) = A027671(n) - 3*A000029(n) + 3.
From Robert A. Russell, Sep 26 2018: (Start)
a(n) = (k!/4) * (S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/2n) * Sum_{d|n} phi(d) * S2(n/d,k), where k=3 is the number of colors and S2 is the Stirling subset number A008277.
G.f.: (k!/4) * x^(2k-2) * (1+x)^2 / Product_{i=1..k} (1-i x^2) - Sum_{d>0} (phi(d)/2d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j x^d), where k=3 is the number of colors. (End)

A056489 Number of periodic palindromes using exactly three different symbols.

Original entry on oeis.org

0, 0, 0, 3, 6, 21, 36, 93, 150, 345, 540, 1173, 1806, 3801, 5796, 11973, 18150, 37065, 55980, 113493, 171006, 345081, 519156, 1044453, 1569750, 3151785, 4733820, 9492213, 14250606, 28550361, 42850116, 85798533, 128746950, 257690505, 386634060, 773661333

Offset: 1

Marks R. Nester

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome.

			For n=4, the three arrangements are ABAC, ABCB, and ACBC.
For n=5, the six arrangements are AABCB, AACBC, ABACC, ABBAC, ABCCB, and ACBBC.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,5,-5,-6,6).

Cf. A056454.

Column 3 of A305540.

a:=[0,0,0,3,6];; for n in [6..40] do a[n]:=a[n-1]+5*a[n-2]-5*a[n-3]-6*a[n-4]+6*a[n-5]; od; a; # Muniru A Asiru, Sep 28 2018

seq(coeff(series(3*x^4*(1+x)/((1-x)*(1-2*x^2)*(1-3*x^2)),x,n+1), x, n), n = 1..40); # Muniru A Asiru, Sep 28 2018

k = 3; Table[(k!/2) (StirlingS2[Floor[(n + 1)/2], k] +
StirlingS2[Ceiling[(n + 1)/2], k]), {n, 1, 40}] (* Robert A. Russell, Jun 05 2018 *)
LinearRecurrence[{1, 5, -5, -6, 6}, {0, 0, 0, 3, 6}, 80] (* Vincenzo Librandi, Sep 27 2018 *)

a(n) = my(k=3); (k!/2)*(stirling(floor((n+1)/2), k, 2) + stirling(ceil((n+1)/2), k, 2)); \\ Michel Marcus, Jun 05 2018

a(n) = 2 * A056343(n) - A056283(n).
G.f.: 3*x^4*(1+x)/((1-x)*(1-2*x^2)*(1-3*x^2)). - Colin Barker, May 06 2012
a(n) = (k!/2)*(S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)), with k=3 different colors used and where S2(n,k) is the Stirling subset number A008277. - Robert A. Russell, Jun 05 2018

A056288 Number of primitive (period n) n-bead necklaces with exactly three different colored beads.

Original entry on oeis.org

0, 0, 2, 9, 30, 89, 258, 720, 2016, 5583, 15546, 43215, 120750, 338001, 950030, 2677770, 7573350, 21478632, 61088874, 174179133, 497812378, 1425832077, 4092087522, 11765778330, 33887517840, 97756266615, 282414622728, 816999371955, 2366509198350, 6862929885407

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A027376.

Column k=3 of A254040.

with(numtheory):
b:= proc(n, k) option remember; `if`(n=0, 1,
      add(mobius(n/d)*k^d, d=divisors(n))/n)
    end:
a:= n-> add(b(n, 3-j)*binomial(3, j)*(-1)^j, j=0..3):
seq(a(n), n=1..30);  # Alois P. Heinz, Jan 25 2015

b[n_, k_] := b[n, k] = If[n==0, 1, DivisorSum[n, MoebiusMu[n/#]*k^#&]/n];
a[n_] := Sum[b[n, 3 - j]*Binomial[3, j]*(-1)^j, {j, 0, 3}];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jun 06 2018, after Alois P. Heinz *)

Sum mu(d)*A056283(n/d) where d|n.

cp's OEIS Frontend

A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A294685 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly three colors under translational symmetry, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A056296 Number of n-bead necklace structures using exactly three different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A056343 Number of bracelets of length n using exactly three different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A056489 Number of periodic palindromes using exactly three different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

A056288 Number of primitive (period n) n-bead necklaces with exactly three different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula