A032087 -id:A032087 - cp's OEIS frontend

A056450 a(n) = (3*2^n - (-2)^n)/2.

1, 4, 4, 16, 16, 64, 64, 256, 256, 1024, 1024, 4096, 4096, 16384, 16384, 65536, 65536, 262144, 262144, 1048576, 1048576, 4194304, 4194304, 16777216, 16777216, 67108864, 67108864, 268435456, 268435456, 1073741824, 1073741824, 4294967296

Offset: 0

Marks R. Nester

Number of palindromes of length n using a maximum of four different symbols.
Number of achiral rows of n colors using up to four colors. - Robert A. Russell, Nov 09 2018
Interleaving of A000302 and 4*A000302.
Unsigned version of A141125.
Binomial transform is A164907. Second binomial transform is A164908. Third binomial transform is A057651. Fourth binomial transform is A016129.

			At length n=1 there are a(1)=4 palindromes, A, B, C, D.
At length n=2, there are a(2)=4 palindromes, AA, BB, CC, DD.
At length n=3, there are a(3)=16 palindromes, AAA, BBB, CCC, DDD, ABA, BAB, ... , CDC, DCD.

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
Sean A. Irvine, Walks on Graphs.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (0,4).

Column k=4 of A321391.
Cf. A000302 (powers of 4), A056450, A141125, A164907, A164908, A057651, A016129.
Cf. A016116.
Essentially the same as A213173.
Cf. A000302 (oriented), A032121 (unoriented), A032087(n>1) (chiral).

Magma
```
[ (3*2^n-(-2)^n)/2: n in [0..31] ];
```

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

Table[4^Ceiling[n/2], {n,0,40}] (* or *)
CoefficientList[Series[(1 + 4 x)/((1 + 2 x) (1 - 2 x)), {x, 0, 31}], x] (* or *)
LinearRecurrence[{0, 4}, {1, 4}, 40] (* Robert A. Russell, Nov 07 2018 *)

a(n)=4^((n+1)\2) \\ Charles R Greathouse IV, Apr 08 2012

a(n)=(3*2^n-(-2)^n)/2 \\ Charles R Greathouse IV, Oct 03 2016

a(n) = 4^floor((n+1)/2).
a(n) = 4*a(n-2) for n > 1; a(0) = 1, a(1) = 4.
G.f.: (1+4*x) / (1-4*x^2). - R. J. Mathar, Jan 19 2011 [Adapted to offset 0 by Robert A. Russell, Nov 07 2018]
a(n+3) = a(n+2)*a(n+1)/a(n). - Reinhard Zumkeller, Mar 04 2011
a(n) = 4*abs(A164111(n-1)). - R. J. Mathar, Jan 19 2011
a(n) = C(4,0)*A000007(n) + C(4,1)*A057427(n) + C(4,2)*A056453(n) + C(4,3)*A056454(n) + C(4,4)*A056455(n). - Robert A. Russell, Nov 08 2018

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

Edited by N. J. A. Sloane, Sep 29 2019

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)

A032121 Number of reversible strings with n beads of 4 colors.

Original entry on oeis.org

1, 4, 10, 40, 136, 544, 2080, 8320, 32896, 131584, 524800, 2099200, 8390656, 33562624, 134225920, 536903680, 2147516416, 8590065664, 34359869440, 137439477760, 549756338176, 2199025352704, 8796095119360, 35184380477440, 140737496743936, 562949986975744

Offset: 0

Christian G. Bower

Also the number of 4-ary strings of length m = n+1 with number of 1's, 2's and 3's all even. Bijective proof, anyone? - Frank Ruskey, Jul 14 2002

			a(2) = 10 = |{000, 110,101,011, 220,202,022, 330,303,033}|.

Colin Barker, Table of n, a(n) for n = 0..1000
Christian Barrientos, Sarah Minion, Series-Parallel Operations with Alpha-Graphs, Theory and Applications of Graphs (2019) Vol. 6, Issue 1, Article 4.
C. G. Bower, Transforms (2)
Index entries for linear recurrences with constant coefficients, signature (4,4,-16).

Column 4 of A277504.

Cf. A000302 (oriented), A032087(n>1) (chiral), A056450 (achiral).

k = 4; Table[(k^n + k^Ceiling[n/2])/2, {n, 0, 30}] (* Robert A. Russell, Nov 25 2017 *)
LinearRecurrence[{4, 4, -16}, {1, 4, 10}, 31] (* Robert A. Russell, Nov 10 2018 *)
CoefficientList[Series[1/4 E^(-2 x) (-1 + 3 E^(4 x) + 2 E^(6 x)), {x, 0, 20}], x]*Table[n!, {n, 0, 20}] (* Stefano Spezia, Nov 12 2018 *)

Vec((1-10*x^2) / ((1 - 2*x)*(1 + 2*x)*(1 - 4*x)) + O(x^40)) \\ Colin Barker, Nov 25 2017

"BIK" (reversible, indistinct, unlabeled) transform of 4, 0, 0, 0, ...
a(n) = (4^m+3*2^m+(-2)^m)/8, where m = n+1. - Frank Ruskey, Jul 14 2002
G.f.: (1-10x^2) / ((1-4x)*(1-4x^2)). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009; corrected by R. J. Mathar, Sep 16 2009 [Adapted to offset 0 by Robert A. Russell, Nov 10 2018]
From Colin Barker, Nov 25 2017: (Start)
a(n) = 2^(n-2) * (3 + (-1)^(1+n) + 2^(1+n)).
a(n) = 4*a(n-1) + 4*a(n-2) - 16*a(n-3) for n>2.
(End)
a(n) = (4^n + 4^floor((n+1)/2)) / 2 = (A000302(n) + A056450(n)) / 2. - Robert A. Russell and Danny Rorabaugh, Jun 22 2018
E.g.f.: (1/4)*exp(-2*x)*(- 1 + 3*exp(4*x) + 2*exp(6*x)). - Stefano Spezia, Nov 12 2018

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

cp's OEIS Frontend

A056450 a(n) = (3*2^n - (-2)^n)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Magma

Mathematica

PARI

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

A032121 Number of reversible strings with n beads of 4 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Formula