A137651 -id:A137651 - cp's OEIS frontend

A276543 Triangle read by rows: T(n,k) = number of primitive (period n) n-bead bracelet structures using exactly k different colored beads.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 13, 11, 3, 1, 0, 8, 31, 33, 16, 3, 1, 0, 14, 80, 136, 85, 27, 4, 1, 0, 21, 201, 478, 434, 171, 37, 4, 1, 0, 39, 533, 1849, 2270, 1249, 338, 54, 5, 1, 0, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1

Offset: 1

Andrew Howroyd, Apr 09 2017

Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure.

			Triangle starts:
  1
  0  1
  0  1   1
  0  2   2    1
  0  3   5    2    1
  0  5  13   11    3    1
  0  8  31   33   16    3   1
  0 14  80  136   85   27   4  1
  0 21 201  478  434  171  37  4 1
  0 39 533 1849 2270 1249 338 54 5 1
  ...

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]

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

Columns 1-6 are A063524, A056366, A056367, A056368, A056369, A056370.
Partial row sums include A000046, A056362, A056363, A056364, A056365.
Row sums are A276548.
Cf. A276550, A152175, A152176, A107424, A137651, A276544, A304972.

\\ Ach is A304972 and R is A152175 as square matrices.
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={my(M=(R(n)+Ach(n))/2); Mat(vectorv(n,n,sumdiv(n, d, moebius(d)*M[n/d,])))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n, k) = Sum_{d|n} mu(n/d) * A152176(d, k).

A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 17, 13, 3, 1, 0, 9, 43, 50, 20, 3, 1, 0, 16, 124, 220, 136, 36, 4, 1, 0, 28, 338, 866, 773, 296, 52, 4, 1, 0, 51, 941, 3435, 4280, 2303, 596, 78, 5, 1, 0, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 0, 170, 7234, 51061

Offset: 1

David Wasserman, May 26 2005

This classification is concerned with which beads are the same color, not with the colors themselves, so bbabcd is the same structure as aabacd. Cyclic permutations are also the same structure, e.g. abacda is also the same structure. However, order matters: the reverse of aabacd is equivalent to aabcad, which is also on the list.

			T(6, 4) = 13: {aaabcd, aabacd, aabcad, abacad, aabbcd, aabcbd, aabcdb, aacbbd, aacbdb, ababcd, abacbd, acabdb, abcabd}.
From _Andrew Howroyd_, Apr 09 2017 (Start)
Triangle starts:
1
0  1
0  1   1
0  2   2    1
0  3   5    2    1
0  5  17   13    3    1
0  9  43   50   20    3   1
0 16 124  220  136   36   4  1
0 28 338  866  773  296  52  4 1
0 51 941 3435 4280 2303 596 78 5 1
(End)

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

Columns 2-6 are A056303, A056304, A056305, A056306, A056307.
Partial row sums include A000048, A002075, A056300, A056301, A056302.
Row sums are A276547.
Cf. A074650, A152175, A276543, A137651, A276544.

A[d_, n_] := A[d, n] = Which[n == 0, 1, n == 1, DivisorSum[d, x^# &], d == 1, Sum[StirlingS2[n, k] x^k, {k, 0, n}], True, Expand[A[d, 1] A[d, n-1] + D[A[d, n-1], x] x]];
B[n_, k_] := Coefficient[DivisorSum[n, EulerPhi[#] A[#, n/#]&]/n/x, x, k];
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] B[#, k]&];
Table[T[n, k], {n, 1, 12}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jun 06 2018, after Andrew Howroyd and Robert A. Russell *)

\\ here R(n) is A152175 as square matrix.
R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n) = {my(M=R(n)); matrix(n, n, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020

T(n, k) = Sum_{d|n} mu(n/d) * A152175(d, k). - Andrew Howroyd, Apr 09 2017

A276544 Triangle read by rows: T(n,k) = number of primitive (aperiodic) reversible string structures with n beads using exactly k different colors.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 4, 4, 1, 0, 9, 15, 6, 1, 0, 16, 49, 37, 9, 1, 0, 35, 160, 183, 76, 12, 1, 0, 66, 498, 876, 542, 142, 16, 1, 0, 133, 1544, 3930, 3523, 1346, 242, 20, 1, 0, 261, 4715, 17179, 21392, 11511, 2980, 390, 25, 1

Offset: 1

Andrew Howroyd, Apr 09 2017

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure.

			Triangle starts
1
0   1
0   2    1
0   4    4     1
0   9   15     6     1
0  16   49    37     9     1
0  35  160   183    76    12    1
0  66  498   876   542   142   16   1
0 133 1544  3930  3523  1346  242  20  1
0 261 4715 17179 21392 11511 2980 390 25 1
...
Primitive reversible word structures are:
n=1: a => 1
n=2: ab => 1
n=3: aab, aba; abc => 2 + 1
n=4: aaab, aaba, aabb, abba => 4 (k=2)
     aabc, abac, abbc, abca => 4 (k=3)

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]

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

Columns 2-6 are A056336, A056337, A056338, A056339, A056340.
Partial row sums include A056331, A056332, A056333, A056334, A056335.
Row sums are A276549.
Cf. A284871, A284949, A277504, A137651, A107424, A276543.

Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[n == 0, 1, 0], 1, If[n > 0, 1, 0], _, If[OddQ[n], Sum[Binomial[(n - 1)/2, i] Ach[n - 1 - 2 i, k - 1], {i, 0, (n - 1)/2}], Sum[Binomial[n/2 - 1, i] (Ach[n - 2 - 2 i, k - 1] + 2^i Ach[n - 2 - 2 i, k - 2]), {i, 0, n/2 - 1}]]]
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] (StirlingS2[#, k] + Ach[#, k])/2& ];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 29 2018, after Robert A. Russell and Andrew Howroyd *)

\\ here Ach is A304972 as matrix.
Ach(n,m=n)={my(M=matrix(n, m, i, k, i>=k)); for(i=3, n, for(k=2, m, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
T(n,m=n)={my(M=matrix(n, m, i, k, stirling(i, k, 2)) + Ach(n,m)); matrix(n, m, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))/2}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020

T(n, k) = Sum_{d|n} mu(n/d) * A284949(d, k).

A056278 Number of primitive (aperiodic) word structures of length n which contain exactly two different symbols.

Original entry on oeis.org

0, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880, 4294966269, 8589869055, 17179869105

Offset: 1

Marks R. Nester

nonn

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure. This is identical to A000740 for n>1.

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]

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

Apart from initial term, this is a duplicate of A000740.
Column 2 of A137651.
Cf. A056267.

a(n) = Sum_{d|n} mu(d)*A000225(n/d-1) where n>0.

G.f.: Sum_{k>=1} mu(k) * x^(2*k) / ((1 - x^k) * (1 - 2*x^k)). - Ilya Gutkovskiy, Apr 15 2021

Terms a(30) and beyond from Andrew Howroyd, Apr 15 2021

A082951 Number of primitive (aperiodic) word structures of length n using an infinite alphabet.

Original entry on oeis.org

1, 1, 1, 4, 13, 51, 197, 876, 4125, 21142, 115922, 678569, 4213381, 27644436, 190898444, 1382958489, 10480138007, 82864869803, 682076784814, 5832742205056, 51724158119384, 474869816155870, 4506715737768752, 44152005855084345, 445958869290587567

Offset: 0

Vadim Ponomarenko (vadim123(AT)gmail.com), May 26 2003

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.

Row sums of triangle A137651. - Gary W. Adamson, Feb 01 2008

			There are A000110(3)=5 word structures of length 3: aaa, aab, aba, abb, abc. The first consists of 3 copies of a word of length 1; the other 4 are primitive. So a(3)=4.

Alois P. Heinz, Table of n, a(n) for n = 0..500

Cf. A000110, A056277, A056272, A056275, A056274, A056278.

Cf. A137651.

with(combinat,bell): with(numtheory): newb := proc(n) local s,i; s := 0; for i in divisors(n) do s := s+bell(i)*mobius(n/i): end do: end proc;
# second Maple program:
with(combinat): with(numtheory):
a:= proc(n) option remember;
      bell(n)-add(a(d), d=divisors(n) minus {n})
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 23 2015

a[n_] := DivisorSum[n, BellB[#] MoebiusMu[n/#]&]; a[0]=1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 23 2017 *)

a(n) = sum mu(c)*A000110(d) over all cd=n; equivalently, A000110(n) = sum a(k), where the sum is over all k|n.

1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) is the g.f. of A000110. - Ilya Gutkovskiy, Mar 05 2018

More terms from Alois P. Heinz, Jan 23 2015

A056279 Number of primitive (aperiodic) word structures of length n which contain exactly three different symbols.

Original entry on oeis.org

0, 0, 1, 6, 25, 89, 301, 960, 3024, 9305, 28501, 86430, 261625, 788669, 2375075, 7140720, 21457825, 64435896, 193448101, 580597110, 1742343323, 5228050949, 15686335501, 47063113320, 141197991000, 423610488665, 1270865802276, 3812663735790, 11438127792025, 34314649427035

Offset: 1

Marks R. Nester

nonn

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same 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]

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

Column 3 of A137651.

Cf. A056268.

a(n) = Sum_{d|n} mu(d)*A000392(n/d) where n>0.

G.f.: Sum_{k>=1} mu(k) * x^(3*k) / Product_{j=1..3} (1 - j*x^k). - Ilya Gutkovskiy, Apr 15 2021

Terms a(26) and beyond from Andrew Howroyd, Apr 15 2021

A056280 Number of primitive (aperiodic) word structures of length n which contain exactly four different symbols.

Original entry on oeis.org

0, 0, 0, 1, 10, 65, 350, 1700, 7770, 34095, 145750, 611435, 2532530, 10391395, 42355940, 171797200, 694337290, 2798799150, 11259666950, 45232081795, 181509069700, 727778478075, 2916342574750, 11681056021300, 46771289738800, 187226354413735, 749329038527580

Offset: 1

Marks R. Nester

nonn

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same 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]

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

Column 4 of A137651.

Cf. A056269.

a(n) = Sum_{n > 0, d|n} mu(d)*A000453(n/d).

G.f.: Sum_{k>=1} mu(k) * x^(4*k) / Product_{j=1..4} (1 - j*x^k). - Ilya Gutkovskiy, Apr 15 2021

Terms a(25) and beyond from Andrew Howroyd, Apr 15 2021

A056281 Number of primitive (aperiodic) word structures of length n which contain exactly five different symbols.

Original entry on oeis.org

0, 0, 0, 0, 1, 15, 140, 1050, 6951, 42524, 246730, 1379385, 7508501, 40074895, 210766919, 1096189500, 5652751651, 28958088579, 147589284710, 749206047975, 3791262568261, 19137821665325, 96416888184100

Offset: 1

Marks R. Nester

nonn

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same 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]

Column 5 of A137651.

Cf. A056270.

a(n) = Sum_{n > 0, d|n} mu(d)*A000481(n/d).

G.f.: Sum_{k>=1} mu(k) * x^(5*k) / Product_{j=1..5} (1 - j*x^k). - Ilya Gutkovskiy, Apr 15 2021

A056282 Number of primitive (aperiodic) word structures of length n which contain exactly six different symbols.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 21, 266, 2646, 22827, 179487, 1323651, 9321312, 63436352, 420693273, 2734926292, 17505749898, 110687248392, 693081601779, 4306078872557, 26585679462783, 163305339165738, 998969857983405

Offset: 1

Marks R. Nester

nonn

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same 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]

Column 6 of A137651.

Cf. A056271.

a(n) = Sum_{n > 0, d|n} mu(d)*A000770(n/d).

G.f.: Sum_{k>=1} mu(k) * x^(6*k) / Product_{j=1..6} (1 - j*x^k). - Ilya Gutkovskiy, Apr 15 2021

cp's OEIS Frontend

A276543 Triangle read by rows: T(n,k) = number of primitive (period n) n-bead bracelet structures using exactly k different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A276544 Triangle read by rows: T(n,k) = number of primitive (aperiodic) reversible string structures with n beads using exactly k different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056278 Number of primitive (aperiodic) word structures of length n which contain exactly two different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A082951 Number of primitive (aperiodic) word structures of length n using an infinite alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A056279 Number of primitive (aperiodic) word structures of length n which contain exactly three different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A056280 Number of primitive (aperiodic) word structures of length n which contain exactly four different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula