|
%I #60 Mar 03 2024 11:19:07
%S 1,1,2,4,11,32,116,455,1993,9134,43580,211659,1041441,5156642,
%T 25640456,127773475,637624313,3184387574,15910947980,79521737939,
%U 397510726681,1987259550002,9935420646296,49674470817195,248364482308833,1241798790172214
%N Number of reversible string structures with n beads using a maximum of five different colors.
%C 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.
%C Number of set partitions of an unoriented row of n elements with five or fewer nonempty subsets. - _Robert A. Russell_, Oct 28 2018
%C 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
%C From _Allan Bickle_, Jun 02 2022: (Start)
%C 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.)
%C Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)
%D 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]
%H Muniru A Asiru, <a href="/A056324/b056324.txt">Table of n, a(n) for n = 0..1000</a>
%H Allan Bickle, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Bickle/bickle5.html">How to Count k-Paths</a>, J. Integer Sequences, 25 (2022) Article 22.5.6.
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H J. Eckhoff, <a href="https://doi.org/10.1002/jgt.3190170112">Extremal interval graphs</a>, J. Graph Theory 17 1 (1993), 117-127.
%H L. Markenzon, O. Vernet, and P. R. da Costa Pereira, <a href="https://doi.org/10.1016/j.dam.2008.05.015">A clique-difference encoding scheme for labelled k-path graphs</a>, Discrete Appl. Math. 156 (2008), 3216-3222.
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (11, -34, -16, 247, -317, -200, 610, -300).
%F Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
%F 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]
%F From _Robert A. Russell_, Oct 28 2018: (Start)
%F a(n) = (A056272(n) + A305751(n)) / 2.
%F a(n) = A056272(n) - A320935(n) = A320935(n) + A305751(n).
%F 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)).
%F a(n) = A000007(n) + A057427(n) + A056326(n) + A056327(n) + A056328(n) + A056329(n). (End)
%F 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
%F From _Allan Bickle_, Jun 04 2022: (Start)
%F 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;
%F 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)
%e 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.
%t 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 *)
%t k=5; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,0,k}]/2,{n,0,40}] (* _Robert A. Russell_, Oct 28 2018 *)
%t 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 *)
%Y Cf. A032122.
%Y Column 5 of A320750.
%Y Cf. A056272 (oriented), A320935 (chiral), A305751 (achiral).
%Y The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
%Y The sequences above converge to A103293(n+1).
%K nonn,easy
%O 0,3
%A _Marks R. Nester_
%E Terms added by _Robert A. Russell_, Oct 30 2018
%E a(0)=1 prepended by _Robert A. Russell_, Nov 07 2018
|
