A032088 -id:A032088 - cp's OEIS frontend

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

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

A293500 Number of orientable strings of length n using a maximum of k colors, array read by descending antidiagonals, T(n,k) for n >= 1 and k >= 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 3, 2, 0, 0, 6, 9, 6, 0, 0, 10, 24, 36, 12, 0, 0, 15, 50, 120, 108, 28, 0, 0, 21, 90, 300, 480, 351, 56, 0, 0, 28, 147, 630, 1500, 2016, 1053, 120, 0, 0, 36, 224, 1176, 3780, 7750, 8064, 3240, 240, 0, 0, 45, 324, 2016, 8232, 23220, 38750, 32640, 9720, 496, 0

Offset: 1

Andrew Howroyd, Oct 10 2017

Reversing the string does not leave it unchanged. Only one string from each pair is counted.
Equivalently, the number of nonequivalent strings up to reversal that are not palindromes.
Except for the first term, column k is the "BHK" (reversible, identity, unlabeled) transform of k,0,0,0,... [Corrected by Petros Hadjicostas, Jul 01 2018]
From Petros Hadjicostas, Jul 01 2018: (Start)
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) = BHK(c_k(n): n >= 1) be the output sequence under Bower's BHK transform. It can be proved that the g.f. of BHK(c_k(n): n >= 1) is A_k(x) = (C_k(x)^2 - C_k(x^2))/(2*(1-C_k(x))*(1-C_k(x^2))) + C_k(x). (See the comments for sequences A032096, A032097, and A032098.)
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 (with the term C_k(x) = k*x excluded) is (C_k(x)^2 - C_k(x^2))/(2*(1-C_k(x))*(1-C_k(x^2))) = (1/2)*(k - 1)*k*x^2/((k*x^2 - 1)*(k*x - 1)), from which we can easily prove Howroyd's formula.
(End)
Comment from Bahman Ahmadi, Aug 05 2019: (Start)
We give an alternative definition for the square array A(n,k) = T(n,k) with n >= 2 and k >= 0. A(n,k) is the number of inequivalent "distinguishing colorings" of the path on n vertices using at most k colors.  The rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of permissible colors.
A vertex-coloring of a graph G is called "distinguishing" if it is only preserved by the identity automorphism of G. This notion is considered in the context of "symmetry breaking" of simple (finite or infinite) graphs. Two vertex-colorings of a graph are called "equivalent" if there is an automorphism of the graph which preserves the colors of the vertices.  Given a graph G, we use the notation Phi_k(G) to denote the number of inequivalent distinguishing colorings of G with at most k colors. This sequence gives A(n,k) = Phi_k(P_n), i.e., the number of inequivalent distinguishing colorings of the path P_n on n vertices with at most k colors.
For n=3, we can color the vertices of P_3 with at most 2 colors in 3 ways such that all the colorings distinguish the graph (i.e., no non-identity automorphism of the path P_3 preserves the coloring) and that all the three colorings are inequivalent.
We have Phi_k(P_n) = binomial(k,2)*k^(n-2) + k*Phi_k(P_(n-2)) for n >= 4; Phi_k(P_2) = binomial(k,2); Phi_k(P_3) = k*binomial(k,2).
(End)

			Array begins:
======================================================
n\k| 1   2    3     4      5      6       7       8
---|--------------------------------------------------
1  | 0   0    0     0      0      0       0       0...
2  | 0   1    3     6     10     15      21      28...
3  | 0   2    9    24     50     90     147     224...
4  | 0   6   36   120    300    630    1176    2016...
5  | 0  12  108   480   1500   3780    8232   16128...
6  | 0  28  351  2016   7750  23220   58653  130816...
7  | 0  56 1053  8064  38750 139320  410571 1046528...
8  | 0 120 3240 32640 195000 839160 2881200 8386560...
...
For T(4,2)=6, the chiral pairs are AAAB-BAAA, AABA-ABAA, AABB-BBAA, ABAB-BABA, ABBB-BBBA, and BABB-BBAB.

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.
C. G. Bower, Transforms (2).

Columns 2-5 for n > 1 are A032085, A032086, A032087, A032088.
Column 6 is A320524.
Rows 2-6 are A161680, A006002(n-1), A083374, A321672, A085744.
Cf. A277504, A293496.
Cf. A003992 (oriented), A277504 (unoriented), A321391 (achiral).

Table[Function[n, (k^n - k^(Ceiling[n/2]))/2][m - k + 1], {m, 11}, {k, m, 1, -1}] // Flatten (* Michael De Vlieger, Oct 11 2017 *)

PARI
```
T(n,k) = (k^n - k^(ceil(n/2)))/2;
```

T(n,k) = (k^n - k^(ceiling(n/2)))/2.
G.f. for column k: (1/2)*(k - 1)*k*x^2/((k*x^2 - 1)*(k*x - 1)). - Petros Hadjicostas, Jul 07 2018
From Robert A. Russell, Nov 16 2018: (Start)
T(n,k) = (A003992(k,n) - A321391(n,k)) / 2.
T(n,k) = = A003992(k,n) - A277504(n,k) = A277504(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>1: x * Sum_{k=1..n-1} A145883(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) = T(1,k) = 0; T(2,k) = binomial(k,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)

A032122 Number of reversible strings with n beads of 5 colors.

Original entry on oeis.org

1, 5, 15, 75, 325, 1625, 7875, 39375, 195625, 978125, 4884375, 24421875, 122078125, 610390625, 3051796875, 15258984375, 76294140625, 381470703125, 1907349609375, 9536748046875, 47683720703125

Offset: 0

Christian G. Bower

			For a(2)=15, the five achiral strings are AA, BB, CC, DD, and EE; the 10 (equivalent) chiral pairs are AB-BA, AC-CA, AD-DA, AE-EA, BC-CB, BD-DB, BE-EB, CD-DC, CE-EC, and DE-ED.

Vincenzo Librandi, Table of n, a(n) for n = 0..500
C. G. Bower, Transforms (2)
Index entries for linear recurrences with constant coefficients, signature (5,5,-25).

Column 5 of A277504.

Cf. A000351 (oriented), A032088(n>1) (chiral), A056451 (achiral).

I:=[1, 5, 15]; [n le 3 select I[n] else 5*Self(n-1)+ 5*Self(n-2)-25*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jan 31 2012

LinearRecurrence[{5, 5, -25}, {1, 5, 15}, 31] (* Vincenzo Librandi, Jan 31 2012 *)
k=5; Table[(k^n+k^Ceiling[n/2])/2,{n,0,30}] (*Robert A. Russell, Nov 25 2017*)

a(n)=(5^((n+1)\2)+5^n)/2 \\ Charles R Greathouse IV, Jan 31 2012

"BIK" (reversible, indistinct, unlabeled) transform of 5, 0, 0, 0...
a(n) = 1/2 * (5^n + 5^floor((n+1)/2)) = 5*A001447(n+1). - Ralf Stephan, Jul 07 2003
G.f.: (1-15*x^2) / ((1-5*x)*(1-5*x^2)). - Colin Barker, Jan 30 2012 [Adapted to offset 0 by Robert A. Russell, Nov 10 2018]
a(n) = 5*a(n-1) + 5*a(n-2) - 25*a(n-3). - Vincenzo Librandi, Jan 31 2012
a(n) = (A000351(n) + A056451(n)) / 2. - Robert A. Russell, Nov 10 2018

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A293500 Number of orientable strings of length n using a maximum of k colors, array read by descending antidiagonals, T(n,k) for n >= 1 and k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A032122 Number of reversible strings with n beads of 5 colors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A032072 Number of reversible strings with n labeled beads of 5 colors, no palindromes of more than 1 bead.

Views

Author

Keywords

Links

Formula