A305751 -id:A305751 - cp's OEIS frontend

A056272 Word structures of length n using a 5-ary alphabet.

1, 1, 2, 5, 15, 52, 202, 855, 3845, 18002, 86472, 422005, 2079475, 10306752, 51263942, 255514355, 1275163905, 6368612302, 31821472612, 159042661905, 795019337135, 3974515030652, 19870830712482, 99348921288655

Offset: 0

Marks R. Nester

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.
Density of regular language L over {1,2,3,4}^* (i.e., number of strings of length n in L) described by regular expression 11* + 11*2(1+2)* + 11*2(1+2)*3(1+2+3)* + 11*2(1+2)*3(1+2+3)*4(1+2+3+4)* + 11*2(1+2)*3(1+2+3)*4(1+2+3+4)*5(1+2+3+4+5)* - Nelma Moreira, Oct 10 2004
Number of set partitions of [n] into at most 5 parts. - Joerg Arndt, Apr 18 2014

			For a(4)=15, the 7 achiral patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD; the 8 chiral patterns are the 4 pairs AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

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]

Muniru A Asiru, Table of n, a(n) for n = 0..1400 (first 200 terms from Vincenzo Librandi)
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Nelma Moreira and Rogerio Reis, On the density of languages representing finite set partitions, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto
Nelma Moreira and Rogerio Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
Index entries for linear recurrences with constant coefficients, signature (11,-41,61,-30).

Cf. A000351, A007581, A056273, A008290, A007051.
A row of the array in A278984.
Cf. A056324 (unoriented), A320935 (chiral), A305751 (achiral).

List([0..25],n->Sum([0..5],k->Stirling2(n,k))); # Muniru A Asiru, Oct 30 2018

I:=[1,1,2,5,15]; [n le 5 select I[n] else 11*Self(n-1)-41*Self(n-2)+61*Self(n-3)-30*Self(n-4): n in [1..30]]; // Vincenzo Librandi, Apr 19 2014

seq(add(combinat:-stirling2(n, j), j=0..5), n=0..23); # Zerinvary Lajos, Dec 04 2007
# Alternative:
(x*(x*(x*(11*x-37)+32)-10)+1)/(x*(x*(x*(30*x-61)+41)-11)+1):
series(%, x, 32): seq(coeff(%, x, n), n=0..23); # Peter Luschny, Nov 05 2018

CoefficientList[Series[(1 - 10 x + 32 x^2 - 37 x^3 + 11 x^4)/((x - 1) (3 x - 1) (2 x - 1) (5 x - 1)), {x, 0, 30}], x] (* Vincenzo Librandi, Apr 19 2014 *)
LinearRecurrence[{11,-41,61,-30},{1,1,2,5,15},30] (* Harvey P. Dale, Feb 25 2018 *)
Table[Sum[StirlingS2[n, k], {k, 0, 5}], {n, 0, 30}] (* Robert A. Russell, Apr 25 2018 *)
CoefficientList[Series[1/120 (44 + 45 E^x + 20 E^(2 x) + 10 E^(3 x) + E^(5 x)), {x, 0, 30}], x]*Table[k!, {k, 0, 30}] (* Stefano Spezia, Nov 06 2018 *)

a(n) = sum(k=0,5, stirling(n, k, 2) ); \\ Joerg Arndt, Apr 18 2014

a(n) = Sum_{k=0..5} Stirling2(n, k).
a(n) = (5^n + 10*3^n + 20*2^n + 45)/5! for n >= 1. - Vladeta Jovovic, Aug 17 2003
From Nelma Moreira, Oct 10 2004: (Start)
For c=5, a(n) = c^n/c! + Sum_{k=0..c-2} (k^n/k!*(Sum_{j=2..c-k} (-1)^j/j!)).
a(n) = Sum_{k=1..c} g(k, c)*k^n where g(1, 1) = 1, g(1, c) = g(1, c-1) + (-1)^(c-1)/(c-1)! if c > 1; g(k, c) = g(k-1, c-1)/k if c > 1, 2 <= k <= c and n >= 1. (End)
a(n+1) is the top entry of the vector M^n*[1,1,1,1,1,0,0,0,...], where M is an infinite bidiagonal matrix with M(r,r+1)=1 in the superdiagonal and M(r,r)=r, r>=1 as the main diagonal, and the rest zeros. The n-th power of the matrix is multiplied from the right with a column vector starting with 5 1's. - Gary W. Adamson, Jun 24 2011
G.f.: (1 - 10x + 32x^2 - 37x^3 + 11x^4)/((1 - x)*(1 - 2x)*(1 - 3x)*(1 - 5x)). - R. J. Mathar, Jul 06 2011 [Adapted to offset 0 by Robert A. Russell, Oct 30 2018]
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=5. - Robert A. Russell, Apr 25 2018
E.g.f.: (1/120)*(44 + 45*exp(x) + 20*exp(2*x) + 10*exp(3*x) + exp(5*x)). - Stefano Spezia, Nov 06 2018

a(0)=1 prepended by Robert A. Russell, Nov 06 2018

A056324 Number of reversible string structures with n beads using a maximum of five different colors.

Original entry on oeis.org

1, 1, 2, 4, 11, 32, 116, 455, 1993, 9134, 43580, 211659, 1041441, 5156642, 25640456, 127773475, 637624313, 3184387574, 15910947980, 79521737939, 397510726681, 1987259550002, 9935420646296, 49674470817195, 248364482308833, 1241798790172214

Offset: 0

Marks R. Nester

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure. Thus aabc, cbaa and bbac are all considered to be identical.
Number of set partitions of an unoriented row of n elements with five or fewer nonempty subsets. - Robert A. Russell, Oct 28 2018
There are nonrecursive formulas, generating functions, and computer programs for A056272 and A305751, which can be used in conjunction with the formula. - Robert A. Russell, Oct 28 2018
From Allan Bickle, Jun 02 2022: (Start)
a(n) is the number of (unlabeled) 5-paths with n+7 vertices. (A 5-path with order n at least 7 can be constructed from a 5-clique by iteratively adding a new 5-leaf (vertex of degree 5) adjacent to an existing 5-clique containing an existing 5-leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

			For a(4)=11, the 7 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, ABBC, and ABCD.  The 4 chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

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]

Muniru A Asiru, Table of n, a(n) for n = 0..1000
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.
Index entries for linear recurrences with constant coefficients, signature (11, -34, -16, 247, -317, -200, 610, -300).

Cf. A032122.
Column 5 of A320750.
Cf. A056272 (oriented), A320935 (chiral), A305751 (achiral).
The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
The sequences above converge to A103293(n+1).

Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
k=5; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,0,k}]/2,{n,0,40}]  (* Robert A. Russell, Oct 28 2018 *)
LinearRecurrence[{11, -34, -16, 247, -317, -200, 610, -300}, {1, 1, 2, 4, 11, 32, 116, 455, 1993}, 40] (* Robert A. Russell, Oct 28 2018 *)

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
G.f.: (1-10x+25x^2+32x^3-196x^4+149x^5+225x^6-321x^7+85x^8)/((1-x)*(1-2x)*(1-3x)*(1-5x)*(1-2x^2)*(1-5x^2)). - Colin Barker, Nov 24 2012 [Adapted to offset 0 by Robert A. Russell, Nov 07 2018]
From Robert A. Russell, Oct 28 2018: (Start)
a(n) = (A056272(n) + A305751(n)) / 2.
a(n) = A056272(n) - A320935(n) = A320935(n) + A305751(n).
a(n) = Sum_{j=0..k} (S2(n,j) + Ach(n,j)) / 2, where k=5 is the maximum number of colors, S2 is the Stirling subset number A008277, and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
a(n) = A000007(n) + A057427(n) + A056326(n) + A056327(n) + A056328(n) + A056329(n). (End)
For n>8, a(n) = 11*a(n-1) - 34*a(n-2) - 16*a(n-3) + 247*a(n-4) - 317*a(n-5) - 200*a(n-6) + 610*a(n-7) - 300*a(n-8). - Muniru A Asiru, Oct 30 2018
From Allan Bickle, Jun 04 2022: (Start)
a(n) = 5^n/240 + 3^n/24 + 2^n/12 + 13*5^(n/2)/120 + 2^(n/2)/6 + 5/16 for n>0 even;
a(n) = 5^n/240 + 3^n/24 + 2^n/12 + 5^((n+1)/2)/24 + 2^((n+1)/2)/12 + 5/16 for n>0 odd. (End)

Terms added by Robert A. Russell, Oct 30 2018

a(0)=1 prepended by Robert A. Russell, Nov 07 2018

A305749 T(n,k) is the number of achiral color patterns (set partitions) in a row or loop of length n with k or fewer colors (sets).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 18, 8, 1, 1, 2, 3, 7, 12, 27, 27, 16, 1, 1, 2, 3, 7, 12, 30, 43, 54, 16, 1, 1, 2, 3, 7, 12, 31, 55, 107, 81, 32, 1, 1, 2, 3, 7, 12, 31, 58, 141, 171, 162, 32, 1, 1, 2, 3, 7, 12, 31, 59, 159, 266, 427, 243, 64, 1, 1, 2, 3, 7, 12, 31, 59, 163, 312, 688, 683, 486, 64, 1

Offset: 1

Robert A. Russell, Jun 09 2018

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABC are equivalent, as are AAABB and BBBAA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a loop are equivalent, so for loops AAABCB = BAAABC = CBAAAB.

			The array begins at T(1,1):
1  1   1    1    1     1     1     1     1     1     1     1     1 ...
1  2   2    2    2     2     2     2     2     2     2     2     2 ...
1  2   3    3    3     3     3     3     3     3     3     3     3 ...
1  4   6    7    7     7     7     7     7     7     7     7     7 ...
1  4   9   11   12    12    12    12    12    12    12    12    12 ...
1  8  18   27   30    31    31    31    31    31    31    31    31 ...
1  8  27   43   55    58    59    59    59    59    59    59    59 ...
1 16  54  107  141   159   163   164   164   164   164   164   164 ...
1 16  81  171  266   312   334   338   339   339   339   339   339 ...
1 32 162  427  688   883   963   993   998   999   999   999   999 ...
1 32 243  683 1313  1774  2069  2169  2204  2209  2210  2210  2210 ...
1 64 486 1707 3407  5103  6119  6634  6789  6834  6840  6841  6841 ...
1 64 729 2731 6532 10368 13524 15080 15790 15975 16026 16032 16033 ...
a(n) are the terms of this array read by antidiagonals.
For T(4,3)=6, the achiral pattern rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA. The achiral pattern loops are AAAA, AAAB, AABB, ABAB, AABC, and ABAC.

Columns 1-6 are A057427, A016116, A182522, A305750, A305751, and A305752.

Columns converge to the right to A080107.

Ach[n_, k_] := Ach[n,k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] +
  Ach[n-2,k-1] + Ach[n-2,k-2]]; (* A304972 *)
Table[Sum[Ach[n, j], {j, 1, k - n + 1}], {k, 1, 15}, {n, 1, k}] // Flatten

T(n,k) = Sum_{j=0..k} Ach(n,j), where Ach(n,k) = [n>1] * (k*T(n-2,k) + T(n-2,k-1) + T(n-2,k-2)) + [0 <= n <= 1 & n==k].

T(n,k) = Sum_{j=1..k} A304972(n,j).

A320935 Number of chiral pairs of color patterns (set partitions) for a row of length n using 5 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 1, 4, 20, 86, 400, 1852, 8868, 42892, 210346, 1038034, 5150110, 25623486, 127740880, 637539592, 3184224728, 15910524632, 79520923966, 397508610454, 1987255480650, 9935410066186, 49674450471460, 248364429410332, 1241798688445588, 6208922948527572, 31044403310614786

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
A chiral row is not equivalent to its reverse.
There are nonrecursive formulas, generating functions, and computer programs for A056272 and A305751, which can be used in conjunction with the first formula.

			For a(4)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

Index entries for linear recurrences with constant coefficients, signature (11,-34,-16,247,-317,-200,610,-300).

Column 5 of A320751.

Cf. A056272 (oriented), A056324 (unoriented), A305751 (achiral).

LinearRecurrence[{11, -34, -16, 247, -317, -200, 610, -300}, {0, 0, 1, 4, 20, 86, 400, 1852}, 40] (* or *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
k=5; Table[Sum[StirlingS2[n,j]-Ach[n,j],{j,k}]/2,{n,40}]

a(n) = (A056272(n) - A305751(n))/2.
a(n) = A056272(n) - A056324(n).
a(n) = A056324(n) - A305751(n).
a(n) = A122746(n-2) + A320526(n) + A320527(n) + A320528(n).
a(n) = Sum_{j=1..k} (S2(n,j) - Ach(n,j)) / 2, where k=5 is the maximum number of colors, S2 is the Stirling subset number A008277, and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
G.f.: x^3*(1 - 7*x + 10*x^2 + 18*x^3 - 49*x^4 + 25*x^5)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 5*x)*(1 - 5*x^2)*(1 - 2*x^2)). - Bruno Berselli, Oct 31 2018

A320745 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using 5 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 6, 34, 181, 871, 4016, 18526, 85101, 393148, 1822977, 8500893, 39809180, 187230704, 883730048, 4184926222, 19874478310, 94629276256, 451604739323, 2159748985582, 10348493650194, 49671898709098, 238804606717950, 1149792470325340, 5543620159707666, 26762240285558924, 129350640352555296, 625889650880647630, 3031651402693863747, 14698911258326292182, 71332938143655936584, 346474231506471943759

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
There are nonrecursive formulas, generating functions, and computer programs for A056293 and A305751, which can be used in conjunction with the first formula.

			For a(6)=6, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, AABACC-AABBAC, AABACD-AABCAD, and AABCBD-AABCDC.

Andrew Howroyd, Table of n, a(n) for n = 1..200
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 5 of A320742.

Cf. A056293 (oriented), A056355 (unoriented), A305751 (achiral).

Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d, Adnk[d,n-1,k-#]&], Boole[n == 0 && k == 0]]
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
k=5; Table[Sum[(DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j]&]/n - Ach[n,j])/2, {j, k}], {n,40}]

a(n) = (A056293(n) - A305751(n)) / 2 = A056293(n) - A056355(n) = A056355(n) - A305751(n).
a(n) = Sum_{j=1..k} -Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where k=5 is the maximum number of colors, Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)), and A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).
a(n) = A059053(n) + A320643(n) + A320644(n) + A320645(n).

cp's OEIS Frontend

A056272 Word structures of length n using a 5-ary alphabet.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

Extensions

A056324 Number of reversible string structures with n beads using a maximum of five different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A305749 T(n,k) is the number of achiral color patterns (set partitions) in a row or loop of length n with k or fewer colors (sets).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A320935 Number of chiral pairs of color patterns (set partitions) for a row of length n using 5 or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A320745 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using 5 or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula