

A025192


a(0)=1; a(n) = 2*3^(n1) for n >= 1.


82



1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 1062882, 3188646, 9565938, 28697814, 86093442, 258280326, 774840978, 2324522934, 6973568802, 20920706406, 62762119218, 188286357654, 564859072962, 1694577218886, 5083731656658, 15251194969974
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Warning: there is considerable overlap between this entry and the essentially identical A008776.
Shifts one place left when plusconvolved (PLUSCONV) with itself. a(n) = 2*Sum_{i=0..n1} a(i).  Antti Karttunen, May 15 2001
Let M = { 0, 1, ..., 2^n1 } be the set of all nbit 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^(n1) 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(i1) = 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. AdamsWatters, 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 stillvalid 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
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>infinity} M^n, the leftshifted 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 3element 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
Number of vertices (or sides) of the (n1)th iteration of a Gosper island.  Arkadiusz Wesolowski, Feb 07 2013
a(n) counts walks (closed) on the graph G(1vertex; 1loop, 1loop, 2loop, 2loop, 3loop, 3loop, ...).  David Neil McGrath, Jan 01 2015
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) = nth power sum of the eigenvalues of M = nth 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 3colorings of the grid graph P_2 X P_(n1). More generally, for q > 1, the number of qcolorings 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(n1).  M. Farrokhi D. G., Oct 25 2023


REFERENCES

Richard P. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96100.


LINKS



FORMULA

G.f.: (1x)/(13*x).
E.g.f.: (2*exp(3*x) + exp(0))/3.  Paul Barry, Apr 20 2003
a(0) = 1, a(n) = Sum_{k=0..n1} (a(k) + a(nk1)).  Benoit Cloitre, Jun 24 2003
a(n) = lcm(a(n1), Sum_{k=1..n1} a(k)) for n >= 3.  David W. Wilson, Sep 27 2011
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, 3step).
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, 1step). (End)
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
Construct the power matrix T(n,j) = [A(n)^*j]*[S(n)^*(j1)] 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)^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 ]
G.f. = 1 + 2*x + 6*x^2 + 18*x^3 + 54*x^4 + 162*x^5 + 486*x^6 + 1458*x^7 + ...


MAPLE

A025192 := proc(n): if n=0 then 1 else 2*3^(n1) fi: end: seq(A025192(n), n=0..26);


MATHEMATICA



PROG

(PARI) Vec((1x)/(13*x) + O(x^100)) \\ Altug Alkan, Dec 05 2015
(Python) [1]+[2*3**(n1) for n in range(1, 30)] # David Nacin, Mar 04 2012
(Haskell)
a025192 0 = 1
a025192 n = 2 * 3 ^ (n 1)


CROSSREFS

Apart from initial term, same as A008776.


KEYWORD

nonn,nice,easy,eigen


AUTHOR



EXTENSIONS



STATUS

approved



