A032122 -id:A032122 - cp's OEIS frontend

A277504 Array read by descending antidiagonals: T(n,k) is the number of unoriented strings with n beads of k or fewer colors.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 6, 1, 0, 1, 5, 10, 18, 10, 1, 0, 1, 6, 15, 40, 45, 20, 1, 0, 1, 7, 21, 75, 136, 135, 36, 1, 0, 1, 8, 28, 126, 325, 544, 378, 72, 1, 0, 1, 9, 36, 196, 666, 1625, 2080, 1134, 136, 1, 0, 1, 10, 45, 288, 1225, 3996, 7875, 8320, 3321, 272, 1, 0

Offset: 0

Jean-François Alcover, Oct 18 2016

From Petros Hadjicostas, Jul 07 2018: (Start)
Column k of this array is the "BIK" (reversible, indistinct, unlabeled) transform of k,0,0,0,....
Consider the input sequence (c_k(n): n >= 1) with g.f. C_k(x) = Sum_{n>=1} c_k(n)*x^n. Let a_k(n) = BIK(c_k(n): n >= 1) be the output sequence under Bower's BIK transform. It can proved that the g.f. of BIK(c_k(n): n >= 1) is A_k(x) = (1/2)*(C_k(x)/(1-C_k(x)) + (C_k(x^2) + C_k(x))/(1-C_k(x^2))). (See the comments for sequence A001224.)
For column k of this two-dimensional array, the input sequence is defined by c_k(1) = k and c_k(n) = 0 for n >= 1. Thus, C_k(x) = k*x, and hence the g.f. of column k is (1/2)*(C_k(x)/(1-C_k(x)) + (C_k(x^2) + C_k(x))/(1-C_k(x^2))) = (1/2)*(k*x/(1-k*x) + (k*x^2 + k*x)/(1-k*x^2)) = (2 + (1-k)*x - 2*k*x^2)*k*x/(2*(1-k*x^2)*(1-k*x)).
Using the first form the g.f. above and the expansion 1/(1-y) = 1 + y + y^2 + ..., we can easily prove J.-F. Alcover's formula T(n,k) = (k^n + k^((n + mod(n,2))/2))/2.
(End)

			Array begins with T(0,0):
1 1   1     1      1       1        1         1         1          1 ...
0 1   2     3      4       5        6         7         8          9 ...
0 1   3     6     10      15       21        28        36         45 ...
0 1   6    18     40      75      126       196       288        405 ...
0 1  10    45    136     325      666      1225      2080       3321 ...
0 1  20   135    544    1625     3996      8575     16640      29889 ...
0 1  36   378   2080    7875    23436     58996    131328     266085 ...
0 1  72  1134   8320   39375   140616    412972   1050624    2394765 ...
0 1 136  3321  32896  195625   840456   2883601   8390656   21526641 ...
0 1 272  9963 131584  978125  5042736  20185207  67125248  193739769 ...
0 1 528 29646 524800 4884375 30236976 141246028 536887296 1743421725 ...
...

See A005418.

Robert A. Russell, Antidiagonals n=0..52, flattened (antidiagonals 1..50 from Andrew Howroyd)
C. G. Bower, Transforms (2)

Columns 0-6 are A000007, A000012, A005418(n+1), A032120, A032121, A032122, A056308.
Rows 0-20 are A000012, A001477, A000217 (triangular numbers), A002411 (pentagonal pyramidal numbers), A037270, A168178, A071232, A168194, A071231, A168372, A071236, A168627, A071235, A168663, A168664, A170779, A170780, A170790, A170791, A170801, A170802.
Main diagonal is A275549.
Transpose is A284979.
Cf. A284871, A284949.
Cf. A003992 (oriented), A293500 (chiral), A321391 (achiral).

[[n le 0 select 1 else ((n-k)^k + (n-k)^Ceiling(k/2))/2: k in [0..n]]: n in [0..15]]; // G. C. Greubel, Nov 15 2018

Table[If[n>0, ((n-k)^k + (n-k)^Ceiling[k/2])/2, 1], {n, 0, 15}, {k, 0, n}] // Flatten (* updated Jul 10 2018 *) (* Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018 *)

for(n=0,15, for(k=0,n, print1(if(n==0,1, ((n-k)^k + (n-k)^ceil(k/2))/2), ", "))) \\ G. C. Greubel, Nov 15 2018

T(n,k) = {(k^n + k^ceil(n/2)) / 2} \\ Andrew Howroyd, Sep 13 2019

T(n,k) = [n==0] + [n>0] * (k^n + k^ceiling(n/2)) / 2. [Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018]
G.f. for column k: (1 - binomial(k+1,2)*x^2) / ((1-k*x)*(1-k*x^2)). - Petros Hadjicostas, Jul 07 2018 [Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018]
From Robert A. Russell, Nov 13 2018: (Start)
T(n,k) = (A003992(k,n) + A321391(n,k)) / 2.
T(n,k) = A003992(k,n) - A293500(n,k) = A293500(n,k) + A321391(n,k).
G.f. for row n: (Sum_{j=0..n} S2(n,j)*j!*x^j/(1-x)^(j+1) + Sum_{j=0..ceiling(n/2)} S2(ceiling(n/2),j)*j!*x^j/(1-x)^(j+1)) / 2, where S2 is the Stirling subset number A008277.
G.f. for row n>0: x*Sum_{k=0..n-1} A145882(n,k) * x^k / (1-x)^(n+1).
E.g.f. for row n: (Sum_{k=0..n} S2(n,k)*x^k + Sum_{k=0..ceiling(n/2)} S2(ceiling(n/2),k)*x^k) * exp(x) / 2, where S2 is the Stirling subset number A008277.
T(0,k) = 1; T(1,k) = k; T(2,k) = binomial(k+1,2); for n>2, T(n,k) = k*(T(n-3,k)+T(n-2,k)-k*T(n-1,k)).
For k>n, T(n,k) = Sum_{j=1..n+1} -binomial(j-n-2,j) * T(n,k-j). (End)

Array transposed for greater consistency by Andrew Howroyd, Apr 04 2017

Origin changed to T(0,0) by Robert A. Russell, Nov 13 2018

A056324 Number of reversible string structures with n beads using a maximum of five different colors.

Original entry on oeis.org

1, 1, 2, 4, 11, 32, 116, 455, 1993, 9134, 43580, 211659, 1041441, 5156642, 25640456, 127773475, 637624313, 3184387574, 15910947980, 79521737939, 397510726681, 1987259550002, 9935420646296, 49674470817195, 248364482308833, 1241798790172214

Offset: 0

Marks R. Nester

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 five or fewer nonempty subsets. - Robert A. Russell, Oct 28 2018
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
From Allan Bickle, Jun 02 2022: (Start)
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.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

			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.

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]

Muniru A Asiru, Table of n, a(n) for n = 0..1000
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.
Index entries for linear recurrences with constant coefficients, signature (11, -34, -16, 247, -317, -200, 610, -300).

Cf. A032122.
Column 5 of A320750.
Cf. A056272 (oriented), A320935 (chiral), A305751 (achiral).
The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
The sequences above converge to A103293(n+1).

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,0,k}]/2,{n,0,40}]  (* Robert A. Russell, Oct 28 2018 *)
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 *)

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
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]
From Robert A. Russell, Oct 28 2018: (Start)
a(n) = (A056272(n) + A305751(n)) / 2.
a(n) = A056272(n) - A320935(n) = A320935(n) + A305751(n).
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)).
a(n) = A000007(n) + A057427(n) + A056326(n) + A056327(n) + A056328(n) + A056329(n). (End)
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
From Allan Bickle, Jun 04 2022: (Start)
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;
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)

Terms added by Robert A. Russell, Oct 30 2018

a(0)=1 prepended by Robert A. Russell, Nov 07 2018

A056451 Number of palindromes using a maximum of five different symbols.

Original entry on oeis.org

1, 5, 5, 25, 25, 125, 125, 625, 625, 3125, 3125, 15625, 15625, 78125, 78125, 390625, 390625, 1953125, 1953125, 9765625, 9765625, 48828125, 48828125, 244140625, 244140625, 1220703125, 1220703125, 6103515625, 6103515625, 30517578125, 30517578125, 152587890625, 152587890625

Offset: 0

Marks R. Nester

Number of achiral rows of n colors using up to five colors. For a(3) = 25, the rows are AAA, ABA, ACA, ADA, AEA, BAB, BBB, BCB, BDB, BEB, CAC, CBC, CCC, CDC, CEC, DAD, DBD, DCD, DDD, DED, EAE, EBE, ECE, EDE, and EEE. - Robert A. Russell, Nov 09 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]

Vincenzo Librandi, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (0,5).

Column k=5 of A321391.
Cf. A000007, A016116, A056391, A056453, A056454, A056455, A056456, A057427,
Cf. A000351 (oriented), A032122 (unoriented), A032088(n>1) (chiral).

[5^Floor((n+1)/2): n in [0..40]]; // Vincenzo Librandi, Aug 16 2011

LinearRecurrence[{0,5},{1,5},30] (* or *) Riffle[5^Range[0, 20], 5^Range[20]] (* Harvey P. Dale, Jul 28 2018 *)
Table[5^Ceiling[n/2], {n,0,40}] (* Robert A. Russell, Nov 07 2018 *)

vector(40, n, n--; 5^floor((n+1)/2)) \\ G. C. Greubel, Nov 07 2018

a(n) = 5^floor((n+1)/2).
a(n) = 5*a(n-2). - Colin Barker, May 06 2012
G.f.: (1+5*x) / (1-5*x^2). - Colin Barker, May 06 2012 [Adapted to offset 0 by Robert A. Russell, Nov 07 2018]
a(n) = C(5,0)*A000007(n) + C(5,1)*A057427(n) + C(5,2)*A056453(n) + C(5,3)*A056454(n) + C(5,4)*A056455(n) + C(5,5)*A056456(n). - Robert A. Russell, Nov 08 2018
E.g.f.: cosh(sqrt(5)*x) + sqrt(5)*sinh(sqrt(5)*x). - Stefano Spezia, Jun 06 2023

a(0)=1 prepended by Robert A. Russell, Nov 07 2018

A032088 Number of reversible strings with n beads of 5 colors. If more than 1 bead, not palindromic.

Original entry on oeis.org

5, 10, 50, 300, 1500, 7750, 38750, 195000, 975000, 4881250, 24406250, 122062500, 610312500, 3051718750, 15258593750, 76293750000, 381468750000, 1907347656250, 9536738281250, 47683710937500

Offset: 1

Christian G. Bower

Andrew Howroyd, Table of n, a(n) for n = 1..200
C. G. Bower, Transforms (2)
Index entries for linear recurrences with constant coefficients, signature (5, 5, -25).

Column 5 of A293500 for n>1.
Cf. A032122.
Equals (A000351 - A056451) / 2 for n>1.

Join[{5}, LinearRecurrence[{5, 5, -25}, {10, 50, 300}, 19]] (* Jean-François Alcover, Oct 11 2017 *)

a(n) = if(n<2, [5][n], (5^n - 5^(ceil(n/2)))/2); \\ Andrew Howroyd, Oct 10 2017

"BHK" (reversible, identity, unlabeled) transform of 5, 0, 0, 0, ...
Conjectures from Colin Barker, Jul 07 2012: (Start)
a(n) = 5*a(n-1) + 5*a(n-2) - 25*a(n-3) for n > 4.
G.f.: 5*x*(1 - 3*x - 5*x^2 + 25*x^3)/((1 - 5*x)*(1 - 5*x^2)).
(End)
Conjectures from Colin Barker, Mar 09 2017: (Start)
a(n) = 5^(n/2)*(5^(n/2) - 1) / 2 for n > 1 and even.
a(n) = -5*(5^(n/2-1/2) - 5^(n-1)) / 2 for n > 1 and odd.
(End)
The above conjectures are true: The second set follows from the definition and the first set can be derived from that. - Andrew Howroyd, Oct 10 2017
a(n) = (5^n - 5^(ceiling(n/2))) / 2 = (A000351(n) - A056451(n)) / 2 for n>1. - Robert A. Russell and Danny Rorabaugh, Jun 22 2018

A056312 Number of reversible strings with n beads using exactly five different colors.

Original entry on oeis.org

0, 0, 0, 0, 60, 900, 8400, 63000, 417120, 2551560, 14804700, 82764900, 450518460, 2404510500, 12646078200, 65771496000, 339165516120, 1737486149760, 8855359634100, 44952367981500, 227475768907860, 1148269329527100, 5785013373810000, 29100047092479000

Offset: 1

Marks R. Nester

A string and its reverse are considered to be equivalent.

			For n=5, the 60 rows are 60 permutations of ABCDE that do not include any mutual reversals.  Each of the 60 chiral pairs, such as ABCDE-EDCBA, is then counted just once.

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]

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (13,-45,-75,695,-575,-3195,5595,4706,-14918,2160,12840,-7200).

Cf. A005418, A032120, A032121, A032122.
Column 5 of A305621.
Equals (A001118 + A056456) / 2 = A001118 - A305625 = A305625 + A056456.

[60*(StirlingSecond(n, 5)+StirlingSecond(Ceiling(n/2), 5)): n in [1..30]]; // Vincenzo Librandi, Sep 30 2018

k=5; Table[(StirlingS2[i,k]+StirlingS2[Ceiling[i/2],k])k!/2,{i,30}] (* Robert A. Russell, Nov 25 2017 *) adapted
CoefficientList[Series[-60*x^4*(120*x^7 - 17*x^6 - 50*x^5 - 32*x^4 + 20*x^3 + 10*x^2 - 2*x - 1)/((x - 1)*(2*x - 1)*(2*x + 1)*(3*x - 1)*(4*x - 1)*(5*x - 1)*(2*x^2 - 1)*(3*x^2 - 1)*(5*x^2 - 1)), {x, 0, 30}], x] (* Stefano Spezia, Sep 29 2018 *)

a(n) = 60*(stirling(n, 5, 2) + stirling(ceil(n/2), 5, 2)); \\ Altug Alkan, Sep 27 2018

a(n) = A032122(n) - 5*A032121(n) + 10*A032120(n) - 10*A005418(n+1) + 5.
G.f.: -60*x^5*(120*x^7 - 17*x^6 - 50*x^5 - 32*x^4 + 20*x^3 + 10*x^2 - 2*x - 1)/((x - 1)*(2*x - 1)*(2*x + 1)*(3*x - 1)*(4*x - 1)*(5*x - 1)*(2*x^2 - 1)*(3*x^2 - 1)*(5*x^2 - 1)). [Colin Barker, Sep 03 2012]
a(n) = k! (S2(n,k) + S2(ceiling(n/2),k)) / 2, where k=5 is the number of colors and S2 is the Stirling subset number. - Robert A. Russell, Sep 25 2018

A056313 Number of reversible strings with n beads using exactly six different colors.

Original entry on oeis.org

0, 0, 0, 0, 0, 360, 7560, 95760, 952560, 8217720, 64615680, 476515080, 3355679880, 22837101840, 151449674040, 984573656640, 6302070915840, 39847411326600, 249509384858160, 1550188410555960, 9570844671224760

Offset: 1

Marks R. Nester

A string and its reverse are considered to be equivalent.

			For n=6, the 360 rows are 360 permutations of ABCDEF that do not include any mutual reversals.  Each of the 360 chiral pairs, such as ABCDEF-FEDCBA, is then counted just once. - _Robert A. Russell_, Sep 25 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]

Index entries for linear recurrences with constant coefficients, signature (19, -117, 81, 1883, -5915, -6615, 53235, -30394, -191744, 264852, 258804, -634248, 43920, 505440, -259200).

Cf. A056308, A056322.
Column 6 of A305621.
Equals (A000920 + A056457) / 2 = A000920 - A305626 = A305626 + A056457.

k=6; Table[(StirlingS2[i,k]+StirlingS2[Ceiling[i/2],k])k!/2,{i,k,30}] (* Robert A. Russell, Nov 25 2017 *)

a(n) = my(k=6); k!/2*(stirling(n, k, 2) + stirling(ceil(n/2), k, 2)); \\ Altug Alkan, Sep 27 2018

a(n) = A056308(n) - 6*A032122(n) + 15*A032121(n) - 20*A032120(n) + 15*A005418(n+1) - 6.
G.f.: 360*x^6*(8*x^2 - x - 1)*(90*x^7 - 9*x^6 - 29*x^5 - 34*x^4 + 15*x^3 + 9*x^2 - x - 1)/((x - 1)*(2*x - 1)*(2*x + 1)*(3*x - 1)*(4*x - 1)*(5*x - 1)*(6*x - 1)*(2*x^2 - 1)*(3*x^2 - 1)*(5*x^2 - 1)*(6*x^2 - 1)). - Colin Barker, Sep 03 2012
a(n) = k! (S2(n,k) + S2(ceiling(n/2),k)) / 2, where k=6 is the number of colors and S2 is the Stirling subset number. - Robert A. Russell, Sep 25 2018

cp's OEIS Frontend

A277504 Array read by descending antidiagonals: T(n,k) is the number of unoriented strings with n beads of k or fewer colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A056324 Number of reversible string structures with n beads using a maximum of five different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A056451 Number of palindromes using a maximum of five different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A032088 Number of reversible strings with n beads of 5 colors. If more than 1 bead, not palindromic.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056312 Number of reversible strings with n beads using exactly five different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A056313 Number of reversible strings with n beads using exactly six different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI