|
| |
|
|
A025192
|
|
a(0)=1; a(n) = 2*3^(n-1) 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 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
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 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
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
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
|
|
|
REFERENCES
|
Richard P. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
|
|
|
LINKS
|
|
|
|
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) = lcm(a(n-1), Sum_{k=1..n-1} 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, 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)
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)^*(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)^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^(n-1) fi: end: seq(A025192(n), n=0..26);
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
(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)
|
|
|
CROSSREFS
|
Apart from initial term, same as A008776.
|
|
|
KEYWORD
|
nonn,nice,easy,eigen
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
