login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A025192 a(0)=1 and a(n)=2*3^(n-1) for n >= 1. 66
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 (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 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->inf} 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

Row sums of triangle in A035002. - Jon Perry, May 30 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>0, tr(M^n) x^n  / n)], implying sum(n>0, 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(5Pi/6)^n ] = n-th power sum of the eigenvalues of M = n-th power sum of the zeroes of the characteristic polynomial.

The relation det(I - x M) = exp[-sum(n>0, 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 betweeen 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)

REFERENCES

R. 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

D Bevan, D Levin, P Nugent, J Pantone, L Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510.08036, 2015

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

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

M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, 2014; http://matinf.pmfbl.org/wp-content/uploads/2015/01/za-arhiv-18.-1.pdf

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.

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

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(n) = phi(3^n) = A000010(A000244(n)). - Labos Elemer, Apr 14 2003

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

Row sums of triangle A134318 - Gary W. Adamson, Oct 19 2007

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

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 + ...

MAPLE

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

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

(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

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

CROSSREFS

First differences of 3^n (A000244). Other self-convolved sequences: A000108, A007460 - A007464, A061922.

Apart from initial term, same as A008776.

Cf. A134318, A160760, A003946, A035002.

Cf. A036039, A263916, A265185, A127672.

Sequence in context: A179349 A179355 A179362 * A008776 A134635 A192338

Adjacent sequences:  A025189 A025190 A025191 * A025193 A025194 A025195

KEYWORD

nonn,nice,easy,eigen

AUTHOR

Clark Kimberling

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 07:54 EDT 2017. Contains 283985 sequences.