login
Number of reversible string structures with n beads using a maximum of four different colors.
13

%I #48 Feb 21 2024 08:26:37

%S 1,1,2,4,11,31,107,379,1451,5611,22187,87979,350891,1400491,5597867,

%T 22379179,89500331,357952171,1431743147,5726775979,22906841771,

%U 91626580651,366505274027,1466017950379,5864067607211

%N Number of reversible string structures with n beads using a maximum of four 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 four or fewer nonempty subsets. - _Robert A. Russell_, Oct 28 2018

%C 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

%C From _Allan Bickle_, Jun 02 2022: (Start)

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

%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 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_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,0,-20,16).

%F Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.

%F For n > 0, a(n) = (16 + (-2)^n + 15*2^n + 4^n)/48. - _Colin Barker_, Nov 24 2012

%F 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]

%F From _Robert A. Russell_, Oct 28 2018: (Start)

%F a(n) = (A124303(n) + A305750(n)) / 2.

%F a(n) = A124303(n) - A320934(n) = A320934(n) + A305750(n).

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

%F a(n) = A000007(n) + A057427(n) + A056326(n) + A056327(n) + A056328(n). (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=4; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,0,k}]/2,{n,0,40}] (* _Robert A. Russell_, Oct 28 2018 *)

%t LinearRecurrence[{5, 0, -20, 16}, {1, 1, 2, 4, 11}, 40] (* _Robert A. Russell_, Oct 28 2018 *)

%Y Cf. A032121.

%Y Column 4 of A320750.

%Y Cf. A124303 (oriented), A320934 (chiral), A305750 (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 a(0)=1 prepended by _Robert A. Russell_, Nov 09 2018