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

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

Author

Marks R. Nester

Keywords

• nonn
• easy

Comments

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)

Examples

			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.
		

References

• 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]

Links

• 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).

Crossrefs

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

Programs

Mathematica

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 *)

Formula

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)

Extensions

Terms added by Robert A. Russell, Oct 30 2018

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