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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A088305 a(0)=1, a(n)=F(2*n) where F(n) = Fibonacci numbers A000045. Has the property: a(n) = 1*a(n-1) + 2*a(n-2) + 3*a(n-3) + 4*a(n-4) + ... 16
1, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976, 12586269025, 32951280099, 86267571272, 225851433717 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of compositions of n into one sort of 1's, two sorts of 2's, ..., k sorts of k's, ...  [Joerg Arndt, Jun 21 2011]

Also the number of spanning trees of a graph formed by joining a single vertex to all vertices of a path on n-1 vertices. - Edward Scheinerman (ers(AT)jhu.edu), Feb 28 2007

Row sums of triangle A128908 . - Philippe Deléham, Nov 21 2007

Let P = the partial sum operator, A000012: (1; 1,1; 1,1,1;...) and A153463 = M, the partial sum & shift operator. It appears that beginning with any randomly taken sequence S(n), iterates of the operations M * S(n), -> M * ANS, -> P * ANS,...etc, (or starting with P) will rapidly converge upon a two- sequence limit cycle of (1, 2, 5, 13, 34,...) and (1, 1, 3, 8, 21,...). - Gary W. Adamson, Dec 27 2008

Eigensequence of triangle A004736. [From Paul Barry, Nov 03 2010]

a(n) = the sum of the products of all compositions of n.

Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n, with exactly 2 elements of each rank level above 0.(Uniform used in the sense of Retakh, Serconek and Wilson.  Graded poset is being used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 26 2012

a(n) is the top left entry in the n-th power of the 3X3 matrix [1, 1, 1; 1, 1, 1; 1, 0, 1] or of the 3X3 matrix [1, 1, 1; 1, 1, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

REFERENCES

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

V. Retakh, S. Serconek, and R. Wilson,  Hilbert Series of Algebras Associated to Directed Graphs and Order Homology

J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738. Mentions this sequence. - N. J. A. Sloane, Mar 14 2014

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

FORMULA

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

G.f.: 1/(1-sum(k>=1, k*x^k)). [Joerg Arndt, Jun 21 2011]

G.f.: sum(n>=0, q^n / (1-q)^(2*n) ). [Joerg Arndt, Dec 09 2012]

a(0) = 1, a(n) = (h^(2n) - h^(-2n))/sqrt(5), where h = (1+sqrt(5))/2.

a(n) = Sum{k=1..n+1} binomial(n+k-1,n-k), with a(0)=1. - Paolo P. Lava, Apr 13 2007

a(0) = 1, a(1) = 1, a(2) = 3, a(n+1) = 3*a(n)-a(n-1) for n>=2. - Philippe Deléham, Nov 21 2007

a(n) = (((3+sqrt(5))/2)^n-((3-sqrt(5))/2)^n)/sqrt(5) [Geoffrey Critzer, Sep 23 2008]

F(2n)=1*F(2n-2)+2*F(2n-4)+3*F(2n-6)+4*F(2n-8)+... F(2n+1)=1+1*F(2n-1)+2*F(2n-3)+3*F(2n-5)+4*F(2n-7)+... Convolution with 1,3,6,10,...n(n+1)/2: 1*F(2n)+3*F(2n-2)+6*F(2n-4)+10*F(2n-6)+...=F(2n+3)-1 1*F(2n-1)+3*F(2n-3)+6*F(2n-5)+10*F(2n-7)+...=F(2n+2)-n-1

G.f.: 1/( 1 - G(0)*(1+x)*x), where G(k)= 1 + x/(1 - x*(k+2)/(x*(k+2) + (k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 31 2013

G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x/(x + (1-x)^2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 31 2013

EXAMPLE

a(5) = 55=1*21+2*8+3*3+4*1+5*1 = 21+16+9+4+5.

a(3) = 8 because if we multiply the compositions of three:

3; 2,1; 1,2; 1,1,1  we get 3,2,2,1 respectively, which sums to eight.

MAPLE

with(combstruct): ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), b): ZL1:=Prod(begin_blockP, Z, end_blockP): ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL1, ZL2), b=ZL1], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n), n=1..29); - Zerinvary Lajos, Mar 08 2008

MATHEMATICA

f[list_]:=Apply[Times, list]; Table[Total[Map[f, Level[Map[Permutations, Partitions[n]], {2}]]], {n, 0, 20}]

CoefficientList[Series[(1 - 2 x + x^2)/(1 - 3 x + x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 16 2014 *)

PROG

(Python)

def a(n, adict={0:1, 1:1, 2:3}):

.if n in adict:

..return adict[n]

.adict[n]=3*a(n-1)-a(n-2)

.return adict[n]

# David Nacin, Mar 04 2012

(PARI)

N=66;  x='x+O('x^N);

Vec( 1/( 1 - sum(k=1, N, k*x^k ) ) )

/* Joerg Arndt, Sep 30 2012 */

CROSSREFS

Cf. A000045. Apart from initial term, same as A001906.

Sequence in context: A231436 A027932 A084625 * A001906 A278613 A072632

Adjacent sequences:  A088302 A088303 A088304 * A088306 A088307 A088308

KEYWORD

easy,nonn

AUTHOR

Miklos Kristof, Nov 05 2003

EXTENSIONS

More terms from Ray Chandler, Nov 06 2003

Further terms from Edward Scheinerman (ers(AT)jhu.edu), Feb 28 2007

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 May 25 10:24 EDT 2017. Contains 287026 sequences.