|
|
A056323
|
|
Number of reversible string structures with n beads using a maximum of four different colors.
|
|
13
|
|
|
1, 1, 2, 4, 11, 31, 107, 379, 1451, 5611, 22187, 87979, 350891, 1400491, 5597867, 22379179, 89500331, 357952171, 1431743147, 5726775979, 22906841771, 91626580651, 366505274027, 1466017950379, 5864067607211
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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 four or fewer nonempty subsets. - Robert A. Russell, Oct 28 2018
There are nonrecursive formulas, generating functions, and computer programs for A124303 and A305750, which can be used in conjunction with the formula. - Robert A. Russell, Oct 28 2018
a(n) is the number of (unlabeled) 4-paths with n+6 vertices. (A 4-path with order n at least 6 can be constructed from a 5-clique by iteratively adding a new 4-leaf (vertex of degree 4) adjacent to an existing 4-clique containing an existing 4-leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)
|
|
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
|
|
|
FORMULA
|
Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
For n > 0, a(n) = (16 + (-2)^n + 15*2^n + 4^n)/48. - Colin Barker, Nov 24 2012
G.f.: (1 - 4x - 3x^2 + 14x^3 - 5x^4) / ((1-x)*(1-4x)*(1-4x^2)). - Colin Barker, Nov 24 2012 [Adapted to offset 0 by Robert A. Russell, Nov 09 2018]
a(n) = Sum_{j=0..k} (S2(n,j) + Ach(n,j)) / 2, where k=4 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)).
|
|
EXAMPLE
|
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.
|
|
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=4; Table[Sum[StirlingS2[n, j]+Ach[n, j], {j, 0, k}]/2, {n, 0, 40}] (* Robert A. Russell, Oct 28 2018 *)
LinearRecurrence[{5, 0, -20, 16}, {1, 1, 2, 4, 11}, 40] (* Robert A. Russell, Oct 28 2018 *)
|
|
CROSSREFS
|
The sequences above converge to A103293(n+1).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|