A032086 -id:A032086 - cp's OEIS frontend

A056449 a(n) = 3^floor((n+1)/2).

1, 3, 3, 9, 9, 27, 27, 81, 81, 243, 243, 729, 729, 2187, 2187, 6561, 6561, 19683, 19683, 59049, 59049, 177147, 177147, 531441, 531441, 1594323, 1594323, 4782969, 4782969, 14348907, 14348907, 43046721, 43046721, 129140163, 129140163, 387420489, 387420489, 1162261467

Offset: 0

Marks R. Nester

One followed by powers of 3 with positive exponent, repeated. - Omar E. Pol, Jul 27 2009

Number of achiral rows of n colors using up to three colors. E.g., for a(3) = 9, the rows are AAA, ABA, ACA, BAB, BBB, BCB, CAC, CBC, and CCC. - Robert A. Russell, Nov 07 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,3).

Column k=3 of A321391.
Cf. A000007, A000244, A016116, A056391, A056453, A056454, A057427.
Essentially the same as A108411 and A162436.
Cf. A000244 (oriented), A032120 (unoriented), A032086(n>1) (chiral).

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

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

a(n)=3^floor((n+1)/2); \\ Joerg Arndt, Apr 23 2013

def A056449(n): return 3**(n+1>>1) # Chai Wah Wu, Oct 28 2024

G.f.: (1 + 3*x) / (1 - 3*x^2). - R. J. Mathar, Jul 06 2011 [Adapted to offset 0 by Robert A. Russell, Nov 07 2018]
a(n) = k^ceiling(n/2), where k = 3 is the number of possible colors. - Robert A. Russell, Nov 07 2018
a(n) = C(3,0)*A000007(n) + C(3,1)*A057427(n) + C(3,2)*A056453(n) + C(3,3)*A056454(n). - Robert A. Russell, Nov 08 2018
E.g.f.: cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x). - Stefano Spezia, Dec 31 2022

Edited by N. J. A. Sloane at the suggestion of Klaus Brockhaus, Jul 03 2009

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

A032120 Number of reversible strings with n beads of 3 colors.

Original entry on oeis.org

1, 3, 6, 18, 45, 135, 378, 1134, 3321, 9963, 29646, 88938, 266085, 798255, 2392578, 7177734, 21526641, 64579923, 193720086, 581160258, 1743421725, 5230265175, 15690618378, 47071855134, 141215033961, 423645101883

Offset: 0

Christian G. Bower

"BIK" (reversible, indistinct, unlabeled) transform of 3, 0, 0, 0, ...

a(n) is the dimension of the homogeneous component of degree n of the free unital special Jordan algebra on 3 generators (this follows from Cohn 1959). Note that this is no longer true for 4 generators and further. - Vladimir Dotsenko, Mar 31 2025

			For a(2)=6, the three achiral strings are AA, BB, CC; the three (equivalent) chiral pairs are AB-BA, AC-CA, BC-CB.
In the language of special Jordan algebras, the three latter correspond to the Jordan products (AB+BA)/2, (AC+CA)/2, (BC+CB)/2.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
C. G. Bower, Transforms (2)
P. M. Cohn, Two embedding theorems for Jordan algebras, Proceedings of the London Mathematical Society, Volume s3-9, Issue 4, October 1959, pp. 503-524.
Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

Column 3 of A277504.

Cf. A000244 (oriented), A032086(n>1) (chiral), A056449 (achiral), A382233 (free Jordan algebras).

I:=[1, 3, 6]; [n le 3 select I[n] else 3*Self(n-1)+3*Self(n-2)-9*Self(n-3): n in [1..25]]; // Vincenzo Librandi, Apr 22 2012

f[n_] := If[EvenQ[n], (3^n + 3^(n/2))/2, (3^n + 3^Ceiling[n/2])/2];
Table[f[n],{n,0,25}] (* Geoffrey Critzer, Apr 24 2011 *)
CoefficientList[Series[(1-6x^2)/((1-3x) (1-3x^2)), {x, 0, 30}], x] (* Vincenzo Librandi, Apr 22 2012 *) (* Adapted to offset 0 by Robert A. Russell, Nov 10 2018 *)
Table[(1/2) ((2 - (-1)^n) 3^Floor[n/2] + 3^n), {n, 0, 25}] (* Bruno Berselli, Apr 22 2012 *)
LinearRecurrence[{3, 3, -9}, {1, 3, 6}, 31] (* Robert A. Russell, Nov 10 2018 *)

a(n) = (3^n + 3^(ceil(n/2)))/2; \\ Andrew Howroyd, Oct 10 2017

a(n) = (1/2)*((2-(-1)^n)*3^floor(n/2) + 3^n). - Ralf Stephan, May 11 2004
For n>0, a(n) = 3 * A001444(n-1). - N. J. A. Sloane, Sep 22 2004
From Colin Barker, Apr 02 2012: (Start)
a(n) = 3*a(n-1) + 3*a(n-2) - 9*a(n-3).
G.f.: (1-6x^2) / ((1-3x)*(1-3x^2)). (End) [Adapted to offset 0 by Robert A. Russell, Nov 10 2018]
a(n) = (1/2)*(3^(ceiling(n/2)) + 3^n). - Andrew Howroyd, Oct 10 2017
a(n) = (A000244(n) + A056449(n)) / 2. - Robert A. Russell, Nov 10 2018

a(0)=1 prepended by Robert A. Russell, Nov 10 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)

cp's OEIS Frontend

A056449 a(n) = 3^floor((n+1)/2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

Extensions

A032120 Number of reversible strings with n beads of 3 colors.

Views

Author

Keywords

Comments

Examples

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

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

Views

Author

Keywords

Links

Formula