OFFSET

0,2

COMMENTS

Warning: there is considerable overlap between this entry and the essentially identical A008776.

Shifts one place left when plus-convolved (PLUSCONV) with itself. a(n) = 2*Sum_{i=0..n-1} a(i). - Antti Karttunen, May 15 2001

Let M = { 0, 1, ..., 2^n-1 } be the set of all n-bit numbers. Consider two operations on this set: "sum modulo 2^n" (+) and "bitwise exclusive or" (XOR). The results of these operations are correlated.

To give a numerical measure, consider the equations over M: u = x + y, v = x XOR y and ask for how many pairs (u,v) is there a solution? The answer is exactly a(n) = 2*3^(n-1) for n >= 1. The fraction a(n)/4^n of such pairs vanishes as n goes to infinity. - Max Alekseyev, Feb 26 2003

Number of (s(0), s(1), ..., s(2n+2)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+2, s(0) = 3, s(2n+2) = 3. - Herbert Kociemba, Jun 10 2004

Number of compositions of n into parts of two kinds. For a string of n objects, before the first, choose first kind or second kind; before each subsequent object, choose continue, first kind, or second kind. For example, compositions of 3 are 3; 2,1; 1,2; and 1,1,1. Using parts of two kinds, these produce respectively 2, 4, 4 and 8 compositions, 2+4+4+8 = 18. - Franklin T. Adams-Watters, Aug 18 2006

In the compositions the kinds of parts are ordered inside a run of identical parts, see example. Replacing "ordered" by "unordered" gives A052945. - Joerg Arndt, Apr 28 2013

Number of permutations of {1, 2, ..., n+1} such that no term is more than 2 larger than its predecessor. For example, a(3) = 18 because all permutations of {1, 2, 3, 4} are valid except 1423, 1432, 2143, 3142, 2314, 3214, in which 1 is followed by 4. Proof: removing (n + 1) gives a still-valid sequence. For n >= 2, can insert (n + 1) either at the beginning or immediately following n or immediately following (n - 1), but nowhere else. Thus the number of such permutations triples when we increase the sequence length by 1. - Joel B. Lewis, Nov 14 2006

Antidiagonal sums of square array A081277. - Philippe Deléham, Dec 04 2006

Equals row sums of triangle A160760. - Gary W. Adamson, May 25 2009

Let M = a triangle with (1, 2, 4, 8, ...) as the left border and all other columns = (0, 1, 2, 4, 8, ...). A025192 = lim_{n->oo} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010

Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n with no 3-element antichain. ("Uniform" used in the sense of Retakh, Serconek and Wilson. By "graded" we mean that all maximal chains have the same length n.) - David Nacin, Feb 13 2012

Equals partial sums of A003946 prefaced with a 1: (1, 1, 4, 12, 36, 108, ...). - Gary W. Adamson, Feb 15 2012

Number of vertices (or sides) of the (n-1)-th iteration of a Gosper island. - Arkadiusz Wesolowski, Feb 07 2013

a(n) counts walks (closed) on the graph G(1-vertex; 1-loop, 1-loop, 2-loop, 2-loop, 3-loop, 3-loop, ...). - David Neil McGrath, Jan 01 2015

From Tom Copeland, Dec 03 2015: (Start)

For n > 0, a(n) are the traces of the even powers of the adjacency matrix M of the simple Lie algebra B_3, tr(M^(2n)) where M = Matrix(row 1; row 2; row 3) = Matrix[0,1,0; 1,0,2; 0,1,0], same as the traces of Matrix[0,2,0; 1,0,1; 0,1,0] (cf. Damianou). The traces of the odd powers vanish.

The characteristic polynomial of M equals determinant(x*I - M) = x^3 - 3x = A127672(3,x), so 1 - 3*x^2 = det(I - x M) = exp(-Sum_{n>=1} tr(M^n) x^n / n), implying Sum_{n>=1} a(n+1) x^(2n) / (2n) = -log(1 - 3*x^2), giving a logarithmic generating function for the aerated sequence, excluding a(0) and a(1).

a(n+1) = tr(M^(2n)), where tr(M^n) = 3^(n/2) + (-1)^n * 3^(n/2) = 2^n*(cos(Pi/6)^n + cos(5*Pi/6)^n) = n-th power sum of the eigenvalues of M = n-th power sum of the zeros of the characteristic polynomial.

The relation det(I - x M) = exp(-Sum_{n>=1} tr(M^n) x^n / n) = Sum_{n>=0} P_n(-tr(M), -tr(M^2), ..., -tr(M^n)) x^n/n! = exp(P.(-tr(M), -tr(M^2), ...)x), where P_n(x(1), ..., x(n)) are the partition polynomials of A036039 implies that with x(2n) = -tr(M^(2n)) = -a(n+1) for n > 0 and x(n) = 0 otherwise, the partition polynomials evaluate to zero except for P_2(x(1), x(2)) = P_2(0,-6) = -6.

Because of the inverse relation between the partition polynomials of A036039 and the Faber polynomials F_k(b1,b2,...,bk) of A263916, F_k(0,-3,0,0,...) = tr(M^k) gives aerated a(n), excluding n=0,1. E.g., F_2(0,-3) = -2(-3) = 6, F_4(0,-3,0,0) = 2 (-3)^2 = 18, and F_6(0,-3,0,0,0,0) = -2(-3)^3 = 54. (Cf. A265185.)

(End)

Number of permutations of length n > 0 avoiding the partially ordered pattern (POP) {1>2, 1>3, 1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is the largest. - Sergey Kitaev, Dec 08 2020

For n > 0, a(n) is the number of 3-colorings of the grid graph P_2 X P_(n-1). More generally, for q > 1, the number of q-colorings of the grid graph P_2 X P_n is given by q*(q - 1)*((q - 1)*(q - 2) + 1)^(n - 1). - Sela Fried, Sep 25 2023

For n > 1, a(n) is the largest solution to the equation phi(x) = a(n-1). - M. Farrokhi D. G., Oct 25 2023

Number of dotted compositions of degree n. - Diego Arcis, Feb 01 2024

REFERENCES

Richard P. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..200

George E. Andrews and Greg Simay, Parity palindrome compositions, Integers 21, Paper No A85, (2021), 13 pp.

Diego Arcis, Camilo González, and Sebastián Márquez On the Hopf algebra of noncommutative symmetric functions in superspace, arXiv:2205.11813 [math.CO], 2022.

D. Bevan, D. Levin, P. Nugent, J. Pantone and L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510.08036 [math.CO], 2015.

Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.

Pantelis A. Damianou, On the characteristic polynomials of Cartan matrices and Chebyshev polynomials, arXiv preprint arXiv:1110.6620 [math.RT], 2014.

Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.

Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 13.

Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

V. Retakh, S. Serconek, and R. Wilson, Hilbert Series of Algebras Associated to Directed Graphs and Order Homology, arXiv:1010.6295 [math.RA], 2010-2011.

Jacob Sprittulla, On Colored Factorizations, arXiv:2008.09984 [math.CO], 2020.

Richard P. Stanley, An Equivalence Relation on the Symmetric Group and Multiplicity-free Flag h-Vectors.

Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.

Vincent Vatter, Counting parity palindrome compositions, arXiv:2109.13155 [math.CO], 2021.

Index entries for linear recurrences with constant coefficients, signature (3).

FORMULA

G.f.: (1-x)/(1-3*x).

E.g.f.: (2*exp(3*x) + exp(0))/3. - Paul Barry, Apr 20 2003

a(0) = 1, a(n) = Sum_{k=0..n-1} (a(k) + a(n-k-1)). - Benoit Cloitre, Jun 24 2003

a(n) = A002326((3^n-1)/2). - Vladimir Shevelev, May 26 2008

a(1) = 2, a(n) = 3*a(n-1). - Vincenzo Librandi, Jan 01 2011

a(n) = lcm(a(n-1), Sum_{k=1..n-1} a(k)) for n >= 3. - David W. Wilson, Sep 27 2011

a(n) = ((2*n-1)*a(n-1) + (3*n-6)*a(n-2))/(n-1); a(0)=1, a(1)=2. - Sergei N. Gladkovskii, Jul 16 2012

From Sergei N. Gladkovskii, Jul 17 2012: (Start)

For the e.g.f. E(x) = (2/3)*exp(3*x) + exp(0)/3 we have

E(x) = 2*G(0)/3 where G(k) = 1 + k!/(3*(9*x)^k - 3*(9*x)^(2*k+1)/((9*x)^(k+1) + (k+1)!/G(k+1))); (continued fraction, 3rd kind, 3-step).

E(x) = 1+2*x/(G(0)-3*x) where G(k) = 3*x + 1 + k - 3*x*(k+1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). (End)

a(n) = A114283(0,0). - Reinhard Zumkeller, Nov 27 2012

G.f.: 1 + ((1/2)/G(0) - 1)/x where G(k) = 1 - 2^k/(2 - 4*x/(2*x - 2^k/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 22 2012

G.f.: 1 + x*W(0), where W(k) = 1 + 1/(1 - x*(2*k+3)/(x*(2*k+4) + 1/W(k+1))); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013

G.f.: 1 / (1 - 2*x / (1 - x)). - Michael Somos, Apr 03 2014

Construct the power matrix T(n,j) = [A(n)^*j]*[S(n)^*(j-1)] where A(n)=(2,2,2,...) and S(n)=(0,1,0,0,...). (* is convolution operation.) Then a(n) = Sum_{j=1..n} T(n,j). - David Neil McGrath, Jan 01 2015

G.f.: 1 + 2*x/(1 + 2*x)*( 1 + 5*x/(1 + 5*x)*( 1 + 8*x/(1 + 8*x)*( 1 + 11*x/(1 + 11*x)*( 1 + .... - Peter Bala, May 27 2017

Sum_{n>=0} 1/a(n) = 7/4. - Bernard Schott, Oct 02 2021

From Amiram Eldar, May 08 2023: (Start)

Sum_{n>=0} (-1)^n/a(n) = 5/8.

Product_{n>=1} (1 - 1/a(n)) = A132019. (End)

EXAMPLE

There are a(3)=18 compositions of 3 into 2 kinds of parts. Here p:s stands for "part p of sort s":

01: [ 1:0 1:0 1:0 ]

02: [ 1:0 1:0 1:1 ]

03: [ 1:0 1:1 1:0 ]

04: [ 1:0 1:1 1:1 ]

05: [ 1:0 2:0 ]

06: [ 1:0 2:1 ]

07: [ 1:1 1:0 1:0 ]

08: [ 1:1 1:0 1:1 ]

09: [ 1:1 1:1 1:0 ]

10: [ 1:1 1:1 1:1 ]

11: [ 1:1 2:0 ]

12: [ 1:1 2:1 ]

13: [ 2:0 1:0 ]

14: [ 2:0 1:1 ]

15: [ 2:1 1:0 ]

16: [ 2:1 1:1 ]

17: [ 3:0 ]

18: [ 3:1 ]

- Joerg Arndt, Apr 28 2013

G.f. = 1 + 2*x + 6*x^2 + 18*x^3 + 54*x^4 + 162*x^5 + 486*x^6 + 1458*x^7 + ...

MATHEMATICA

Join[{1}, 2*3^(Range[30]-1)] (* Harvey P. Dale, Mar 22 2011 *)

PROG

(PARI) a(n)=max(1, 2*3^(n-1)) \\ Charles R Greathouse IV, Jul 25 2011

(PARI) Vec((1-x)/(1-3*x) + O(x^100)) \\ Altug Alkan, Dec 05 2015

(Python) [1]+[2*3**(n-1) for n in range(1, 30)] # David Nacin, Mar 04 2012

(Haskell)

a025192 0 = 1

a025192 n = 2 * 3 ^ (n -1)

a025192_list = 1 : iterate (* 3) 2 -- Reinhard Zumkeller, Nov 27 2012

CROSSREFS

KEYWORD

nonn,nice,easy,eigen

AUTHOR

EXTENSIONS

Additional comments from Barry E. Williams, May 27 2000

a(22) corrected by T. D. Noe, Feb 08 2008

Maple programs simplified by Johannes W. Meijer, Jun 02 2011

STATUS

approved