|
%I #42 Feb 21 2024 08:26:45
%S 1,1,2,4,11,32,117,467,2135,10480,55091,301633,1704115,9819216,
%T 57365191,338134521,2005134639,11937364184,71254895955,426063226937,
%U 2550552314219,15280103807200,91588104196415,549159428968825
%N Number of reversible string structures with n beads using a maximum of six 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 six or fewer nonempty subsets. - _Robert A. Russell_, Oct 28 2018
%C There are nonrecursive formulas, generating functions, and computer programs for A056273 and A305752, which can be used in conjunction with the first formula. - _Robert A. Russell_, Oct 28 2018
%C From _Allan Bickle_, Jun 23 2022: (Start)
%C a(n) is the number of (unlabeled) 6-paths with n+8 vertices. (A 6-path with order n at least 8 can be constructed from a 6-clique by iteratively adding a new 6-leaf (vertex of degree 6) adjacent to an existing 6-clique containing an existing 6-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 Colin Barker, <a href="/A056325/b056325.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_11">Index entries for linear recurrences with constant coefficients</a>, signature (16,-84,84,685,-2140,180,7200,-8244,-4176,11664,-5184).
%F Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
%F From _Robert A. Russell_, Oct 28 2018: (Start)
%F a(n) = (A056273(n) + A305752(n)) / 2.
%F a(n) = A056273(n) - A320936(n) = A320936(n) + A305752(n).
%F a(n) = Sum_{j=0..k} (S2(n,j) + Ach(n,j)) / 2, where k=6 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) + A056330(n).
%F (End)
%F From _Colin Barker_, Mar 24 2020: (Start)
%F G.f.: (1 - 15*x + 70*x^2 - 28*x^3 - 654*x^4 + 1479*x^5 + 783*x^6 - 5481*x^7 + 3512*x^8 + 4640*x^9 - 5922*x^10 + 1530*x^11) / ((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 4*x)*(1 - 6*x)*(1 - 2*x^2)*(1 - 3*x^2)*(1 - 6*x^2)).
%F a(n) = 16*a(n-1) - 84*a(n-2) + 84*a(n-3) + 685*a(n-4) - 2140*a(n-5) + 180*a(n-6) + 7200*a(n-7) - 8244*a(n-8) - 4176*a(n-9) + 11664*a(n-10) - 5184*a(n-11) for n>11.
%F (End)
%F From _Allan Bickle_, Jun 23 2022: (Start)
%F a(n) = (1/1440)*6^n + (1/96)*4^n + (1/36)*3^n + (3/32)*2^n + (19/360)*6^(n/2) + (1/9)*3^(n/2) + (1/8)*2^(n/2) + 17/60 for n > 0 even;
%F a(n) = (1/1440)*6^n + (1/96)*4^n + (1/36)*3^n + (3/32)*2^n + (13/720)*6^((n+1)/2) + (1/18)*3^((n+1)/2) + (1/16)*2^((n+1)/2) + 17/60 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=6; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,0,k}]/2,{n,0,40}] (* _Robert A. Russell_, Oct 28 2018 *)
%t LinearRecurrence[{16, -84, 84, 685, -2140, 180, 7200, -8244, -4176, 11664, -5184}, {1, 1, 2, 4, 11, 32, 117, 467, 2135, 10480, 55091, 301633}, 40] (* _Robert A. Russell_, Oct 28 2018 *)
%o (PARI) Vec((1 - 15*x + 70*x^2 - 28*x^3 - 654*x^4 + 1479*x^5 + 783*x^6 - 5481*x^7 + 3512*x^8 + 4640*x^9 - 5922*x^10 + 1530*x^11) / ((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 4*x)*(1 - 6*x)*(1 - 2*x^2)*(1 - 3*x^2)*(1 - 6*x^2)) + O(x^30)) \\ _Colin Barker_, Apr 15 2020
%Y Cf. A056308.
%Y Column 6 of A320750.
%Y Cf. A056273 (oriented), A320936 (chiral), A305752 (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 Another term from _Robert A. Russell_, Oct 29 2018
%E a(0)=1 prepended by _Robert A. Russell_, Nov 09 2018
|
