A320526 -id:A320526 - cp's OEIS frontend

A056327 Number of reversible string structures with n beads using exactly three different colors.

0, 0, 1, 4, 15, 50, 160, 502, 1545, 4730, 14356, 43474, 131145, 395150, 1188580, 3572902, 10732065, 32225810, 96733636, 290322394, 871200825, 2614097750, 7843255300, 23531775502, 70599259185, 211805902490

Offset: 1

Marks R. Nester

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure.

Number of set partitions for an unoriented row of n elements using exactly three different elements. An unoriented row is equivalent to its reverse. - Robert A. Russell, Oct 14 2018

			For a(4)=4, the color patterns are ABCA, ABBC, AABC, and ABAC. The first two are achiral. - _Robert A. Russell_, Oct 14 2018

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]

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-6,-24,49,6,-66,36).

Column 3 of A284949.
Cf. A056310.
Cf. A000392 (oriented), A320526 (chiral), A304973 (achiral).

I:=[0,0,1,4,15,50,160]; [n le 7 select I[n] else 6*Self(n-1) -6*Self(n-2) -24*Self(n-3) +49*Self(n-4) +6*Self(n-5) -66*Self(n-6) +36*Self(n-7): n in [1..40]]; // G. C. Greubel, Oct 16 2018

k=3; Table[(StirlingS2[n,k] + If[EvenQ[n], 2StirlingS2[n/2+1,3] - 2StirlingS2[n/2,3], StirlingS2[(n+3)/2,3] - StirlingS2[(n+1)/2,3]])/2, {n,30}] (* Robert A. Russell, Oct 15 2018 *)
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]]
k=3; Table[(StirlingS2[n, k] + Ach[n, k])/2, {n,30}] (* Robert A. Russell, Oct 15 2018 *)
LinearRecurrence[{6, -6, -24, 49, 6, -66, 36}, {0, 0, 1, 4, 15, 50, 160}, 30] (* Robert A. Russell, Oct 15 2018 *)

m=40; v=concat([0,0,1,4,15,50,160], vector(m-7)); for(n=8, m, v[n] = 6*v[n-1] -6*v[n-2] -24*v[n-3] +49*v[n-4] +6*v[n-5] -66*v[n-6] +36*v[n-7] ); v \\ G. C. Greubel, Oct 16 2018

a(n) = A001998(n-1) - A005418(n).
G.f.: x^3*(3*x^4 - 8*x^3 + 3*x^2 + 2*x - 1)/((x-1)*(2*x-1)*(3*x-1)*(2*x^2-1)*(3*x^2-1)). - Colin Barker, Sep 23 2012
From Robert A. Russell, Oct 14 2018: (Start)
a(n) = (S2(n,k) + A(n,k))/2, where k=3 is the number of colors (sets), S2 is the Stirling subset number A008277 and A(n,k) = [n>1] * (k*A(n-2,k) + A(n-2,k-1) + A(n-2,k-2)) + [n<2 & n==k & n>=0].
a(n) = (A000392(n) + A304973(n)) / 2 = A000392(n) - A320526(n) = A320526(n) + A304973(n). (End)

A320525 Triangle read by rows: T(n,k) = number of chiral pairs of color patterns (set partitions) in a row of length n using exactly k colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 6, 10, 4, 0, 0, 12, 40, 28, 6, 0, 0, 28, 141, 167, 64, 9, 0, 0, 56, 464, 824, 508, 124, 12, 0, 0, 120, 1480, 3840, 3428, 1300, 220, 16, 0, 0, 240, 4600, 16920, 21132, 11316, 2900, 360, 20, 0, 0, 496, 14145, 72655, 123050, 89513, 31846, 5890, 560, 25, 0, 0, 992, 43052, 305140, 688850, 660978, 313190, 79256, 11060, 830, 30, 0

Offset: 1

Robert A. Russell, Oct 14 2018

Two color patterns are equivalent if we permute the colors. Chiral color patterns must not be equivalent if we reverse the order of the pattern.

If the top entry of the triangle is changed from 0 to 1, this is the number of non-equivalent distinguishing partitions of the path on n vertices (n >= 1) with exactly k parts (1 <= k <= n). - Bahman Ahmadi, Aug 21 2019

			Triangle begins with T(1,1):
  0;
  0,   0;
  0,   1,     0;
  0,   2,     2,      0;
  0,   6,    10,      4,      0;
  0,  12,    40,     28,      6,      0;
  0,  28,   141,    167,     64,      9,      0;
  0,  56,   464,    824,    508,    124,     12,     0;
  0, 120,  1480,   3840,   3428,   1300,    220,    16,     0;
  0, 240,  4600,  16920,  21132,  11316,   2900,   360,    20,   0;
  0, 496, 14145,  72655, 123050,  89513,  31846,  5890,   560,  25, 0;
  0, 992, 43052, 305140, 688850, 660978, 313190, 79256, 11060, 830, 30, 0;
  ...
For T(3,2)=1, the chiral pair is AAB-ABB.  For T(4,2)=2, the chiral pairs are AAAB-ABBB and AABA-ABAA.  For T(5,2)=6, the chiral pairs are AAAAB-ABBBB, AAABA-ABAAA, AAABB-AABBB, AABAB-ABABB, AABBA-ABBAA, and ABAAB-ABBAB.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Columns 1-6 are A000004, A122746(n-2), A320526, A320527, A320528, A320529.
Row sums are A320937.
Cf. A008277 (oriented), A284949 (unoriented), A304972 (achiral).

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 *)
Table[(StirlingS2[n, k] - Ach[n, k])/2, {n, 1, 12}, {k, 1, n}] // Flatten

\\ here Ach is A304972 as square matrix.
Ach(n)={my(M=matrix(n,n,i,k,i>=k)); for(i=3, n, for(k=2, n, M[i,k]=k*M[i-2,k] + M[i-2,k-1] + if(k>2, M[i-2,k-2]))); M}
T(n)={(matrix(n,n,i,k,stirling(i,k,2)) - Ach(n))/2}
{ my(A=T(10)); for(n=1, #A, print(A[n,1..n])) } \\ Andrew Howroyd, Sep 18 2019

T(n,k) = (S2(n,k) - A(n,k))/2, where S2 is the Stirling subset number A008277 and A(n,k) = [n>1] * (k*A(n-2,k) + A(n-2,k-1) + A(n-2,k-2)) + [n<2 & n==k & n>=0].

T(n,k) = (A008277(n,k) - A304972(n,k)) / 2 = A008277(n,k) - A284949(n,k) = A284949(n,k) - A304972(n,k).

A107767 a(n) = (1 + 3^n - 23^(n/2))/4 if n is even, (1 + 3^n - 43^((n-1)/2))/4 if n odd.

Original entry on oeis.org

0, 1, 4, 16, 52, 169, 520, 1600, 4840, 14641, 44044, 132496, 397852, 1194649, 3585040, 10758400, 32278480, 96845281, 290545684, 871666576, 2615029252, 7845176329, 23535617560, 70607118400, 211821620920, 635465659921

Offset: 1

Emeric Deutsch, Jun 12 2005

a(n-1) is the number of chiral pairs of color patterns (set partitions) for a row of length n using up to 3 colors (subsets). For n=4, a(n-1)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - Robert A. Russell, Oct 28 2018

Balaban, A. T., Brunvoll, J., Cyvin, B. N., & Cyvin, S. J. (1988). Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures. Tetrahedron, 44(1), 221-228. See Eq. 5.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).
Index entries for linear recurrences with constant coefficients, signature (4,0,-12,9).

Cf. A167993 (first differences).
Column 3 of A320751, offset by 1.
Cf. A124302 (oriented), A001998 (unoriented), A182522 (achiral), varying offsets.

a:=[];; for n in [1..30] do if n mod 2 <> 0 then Add(a,(1+3^n-4*3^((n-1)/2))/4); else Add(a,(1+3^n-2*3^(n/2))/4); fi; od; a; # Muniru A Asiru, Oct 30 2018

I:=[0, 1, 4, 16]; [n le 4 select I[n] else 4*Self(n-1)-12*Self(n-3)+9*Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 26 2012

a:=proc(n) if n mod 2 = 0 then (1+3^n-2*3^(n/2))/4 else (1+3^n-4*3^((n-1)/2))/4 fi end: seq(a(n),n=1..32);

CoefficientList[Series[-x/((x-1)*(3*x-1)*(3*x^2-1)),{x,0,40}],x] (* or *) LinearRecurrence[{4,0,-12,9},{0,1,4,16},50] (* Vincenzo Librandi, Jun 26 2012 *)
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=3; Table[Sum[StirlingS2[n,j]-Ach[n,j],{j,k}]/2,{n,2,40}] (* Robert A. Russell, Oct 28 2018 *)
CoefficientList[Series[(1/12 E^(-Sqrt[3] x) (-3 + 2 Sqrt[3] - (3 + 2 Sqrt[3]) E^(2 Sqrt[3] x) + 3 E^((3 + Sqrt[3]) x) + 3 E^(x + Sqrt[3] x)))/x, {x, 0, 20}], x]*Table[(k+1)!, {k, 0, 20}] (* Stefano Spezia, Oct 29 2018 *)

x='x+O('x^50); concat(0, Vec(x^2/((1-x)*(3*x-1)*(3*x^2-1)))) \\ Altug Alkan, Sep 23 2018

G.f.: -x^2 / ( (x-1)*(3*x-1)*(3*x^2-1) ). - R. J. Mathar, Dec 16 2010
a(n) = 4*a(n-1) - 12*a(n-3) + 9*a(n-4). - Vincenzo Librandi, Jun 26 2012
From Robert A. Russell, Oct 28 2018: (Start)
a(n-1) = Sum_{j=0..k} (S2(n,j) - Ach(n,j)) / 2, where k=3 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-1) = (A124302(n) - A182522(n))/2.
a(n-1) = A124302(n) - A001998(n-1).
a(n-1) = A001998(n-1) - A182522(n).
a(n-1) = A122746(n-2) + A320526(n). (End)
E.g.f.: (1/12)*exp(-sqrt(3)*x)*(-3 + 2*sqrt(3) - (3 + 2*sqrt(3))*exp(2*sqrt(3)*x) + 3*exp((3 + sqrt(3))*x) + 3*exp(x + sqrt(3)*x)). - Stefano Spezia, Oct 29 2018
From Bruno Berselli, Oct 31 2018: (Start)
a(n) = (1 + 3^n - 3^((n-1)/2)*(4 + (-2 + sqrt(3))*(1 + (-1)^n)))/4. Therefore:
a(2*k)   = (3^k - 1)^2/4;
a(2*k+1) = (3^k - 1)*(3^(k+1) - 1)/4. (End)

Entry revised by N. J. A. Sloane, Jul 29 2011

A320936 Number of chiral pairs of color patterns (set partitions) for a row of length n using 6 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 1, 4, 20, 86, 409, 1976, 10168, 54208, 299859, 1699012, 9808848, 57335124, 338073107, 2004955824, 11936998016, 71253827696, 426061036747, 2550545918300, 15280090686256, 91588065861292, 549159350303235, 3293482358956552, 19755007003402944

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
A chiral row is not equivalent to its reverse.
There are nonrecursive formulas, generating functions, and computer programs for A056273 and A305752, which can be used in conjunction with the first formula.

			For a(4)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (16,-84,84,685,-2140,180,7200,-8244, -4176,11664,-5184).

Column 6 of A320751.

Cf. A056273 (oriented), A056325 (unoriented), A305752 (achiral).

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=6; Table[Sum[StirlingS2[n,j]-Ach[n,j],{j,k}]/2,{n,40}]
LinearRecurrence[{16, -84, 84, 685, -2140, 180, 7200, -8244, -4176, 11664, -5184}, {0, 0, 1, 4, 20, 86, 409, 1976, 10168, 54208, 299859}, 40]

concat([0,0], Vec(x^3*(1 - 12*x + 40*x^2 + 18*x^3 - 308*x^4 + 376*x^5 + 364*x^6 - 882*x^7 + 378*x^8) / ((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^40))) \\ Colin Barker, Nov 22 2018

a(n) = (A056273(n) - A305752(n))/2.
a(n) = A056273(n) - A056325(n).
a(n) = A056325(n) - A305752(n).
a(n) = A122746(n-2) + A320526(n) + A320527(n) + A320528(n) + A320529(n).
a(n) = Sum_{j=1..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)).
From Colin Barker, Nov 22 2018: (Start)
G.f.: x^3*(1 - 12*x + 40*x^2 + 18*x^3 - 308*x^4 + 376*x^5 + 364*x^6 - 882*x^7 + 378*x^8) / ((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)).
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.
(End)

A320935 Number of chiral pairs of color patterns (set partitions) for a row of length n using 5 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 1, 4, 20, 86, 400, 1852, 8868, 42892, 210346, 1038034, 5150110, 25623486, 127740880, 637539592, 3184224728, 15910524632, 79520923966, 397508610454, 1987255480650, 9935410066186, 49674450471460, 248364429410332, 1241798688445588, 6208922948527572, 31044403310614786

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
A chiral row is not equivalent to its reverse.
There are nonrecursive formulas, generating functions, and computer programs for A056272 and A305751, which can be used in conjunction with the first formula.

			For a(4)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

Index entries for linear recurrences with constant coefficients, signature (11,-34,-16,247,-317,-200,610,-300).

Column 5 of A320751.

Cf. A056272 (oriented), A056324 (unoriented), A305751 (achiral).

LinearRecurrence[{11, -34, -16, 247, -317, -200, 610, -300}, {0, 0, 1, 4, 20, 86, 400, 1852}, 40] (* or *)
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,k}]/2,{n,40}]

a(n) = (A056272(n) - A305751(n))/2.
a(n) = A056272(n) - A056324(n).
a(n) = A056324(n) - A305751(n).
a(n) = A122746(n-2) + A320526(n) + A320527(n) + A320528(n).
a(n) = Sum_{j=1..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)).
G.f.: x^3*(1 - 7*x + 10*x^2 + 18*x^3 - 49*x^4 + 25*x^5)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 5*x)*(1 - 5*x^2)*(1 - 2*x^2)). - Bruno Berselli, Oct 31 2018

A320934 Number of chiral pairs of color patterns (set partitions) for a row of length n using 4 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 1, 4, 20, 80, 336, 1344, 5440, 21760, 87296, 349184, 1397760, 5591040, 22368256, 89473024, 357908480, 1431633920, 5726601216, 22906404864, 91625881600, 366503526400, 1466015154176, 5864060616704, 23456246661120, 93824986644480, 375299963355136, 1501199853420544, 6004799480791040

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
A chiral row is not equivalent to its reverse.
There are nonrecursive formulas, generating functions, and computer programs for A124303 and A305750, which can be used in conjunction with the first formula.

			For a(4)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

Index entries for linear recurrences with constant coefficients, signature (4,4,-16).

Column 4 of A320751.

Cf. A124303 (oriented), A056323 (unoriented), A305750 (achiral).

Table[(4^n - 4^Floor[n/2+1])/48, {n, 40}] (* or *)
LinearRecurrence[{4, 4, -16}, {0, 0, 1}, 40] (* or *)
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,k}]/2,{n,40}]
CoefficientList[Series[x^2/((-1 + 4 x) (-1 + 4 x^2)), {x, 0, 50}], x] (* Stefano Spezia, Oct 29 2018 *)

a(n) = (A124303(n) - A305750(n))/2.
a(n) = A124303(n) - A056323(n).
a(n) = A056323(n) - A305750(n).
a(n) = A122746(n-2) + A320526(n) + A320527(n).
a(n) = Sum_{j=1..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)).
a(2*m) = (16^m - 4*4^m)/48.
a(2*m-1) = (16^m - 4*4^m)/192.
a(n) = (4^n - 4^floor(n/2+1))/48.
G.f.: x^2/((-1 + 4*x)*(-1 + 4*x^2)). - Stefano Spezia, Oct 29 2018
a(n) = 2^n*(2^n - (-1)^n - 3)/48. - Bruno Berselli, Oct 31 2018

cp's OEIS Frontend

A056327 Number of reversible string structures with n beads using exactly three different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A320525 Triangle read by rows: T(n,k) = number of chiral pairs of color patterns (set partitions) in a row of length n using exactly k colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A107767 a(n) = (1 + 3^n - 2*3^(n/2))/4 if n is even, (1 + 3^n - 4*3^((n-1)/2))/4 if n odd.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

Extensions

A320936 Number of chiral pairs of color patterns (set partitions) for a row of length n using 6 or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A320935 Number of chiral pairs of color patterns (set partitions) for a row of length n using 5 or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A320934 Number of chiral pairs of color patterns (set partitions) for a row of length n using 4 or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A107767 a(n) = (1 + 3^n - 23^(n/2))/4 if n is even, (1 + 3^n - 43^((n-1)/2))/4 if n odd.