A088305 a(0) = 1, a(n) = Fibonacci(2*n). It has the property that a(n) = 1*a(n-1) + 2*a(n-2) + 3*a(n-3) + 4*a(n-4) + ...

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

Offset: 0

Author

Miklos Kristof, Nov 05 2003

Keywords

• easy
• nonn

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. - 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 3 X 3 matrix [1, 1, 1; 1, 1, 1; 1, 0, 1] or of the 3 X 3 matrix [1, 1, 1; 1, 1, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

Examples

			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.
		

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
• A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
• Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See pp 25, 29.
• Meghann M. Gibson, Combinatorics of Compositions, Electronic Theses & Dissertations, Georgia Southern University, 2017.
• Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.
• Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
• 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.
• 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, arXiv:0711.1738 [cond-mat.stat-mech], 2007-2009; J. Stat. Phys. 135 (2009) 279-373. Mentions this sequence. - _N. J. A. Sloane_, Mar 14 2014
• Luigi Santocanale, On discrete idempotent paths, arXiv:1906.05590 [math.LO], 2019.
• Index entries for linear recurrences with constant coefficients, signature (3,-1).

Crossrefs

Cf. A000012, A000045, A004736, A128908, A153463.

Apart from initial term, same as A001906.

Programs

Magma

[1] cat [Fibonacci(2*n): n in [1..40]]; // G. C. Greubel, Dec 16 2022

Maple

H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):
a := n -> `if`(n = 0, 1, H(2*n, 1, 1/2)):
seq(simplify(a(n)), n=0..28); # Peter Luschny, Sep 03 2019
# third Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
      add(a(n-i)*i, i=1..n))
    end:
seq(a(n), n=0..36);  # Alois P. Heinz, Feb 09 2021

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 *)
Join[{1}, Fibonacci[2*Range[40]]] (* G. C. Greubel, Dec 16 2022 *)

PARI

N=66;  x='x+O('x^N);
Vec( 1/( 1 - sum(k=1,N, k*x^k ) ) )
/* Joerg Arndt, Sep 30 2012 */

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

SageMath

def A088305(n): return 1 if (n==0) else fibonacci(2*n)
[A088305(n) for n in range(41)] # G. C. Greubel, Dec 16 2022

Formula

a(n) = 1*a(n-1) + 2*a(n-2) + 3*a(n-3) + 4*a(n-4) + ...

G.f.: (1 -2*x + x^2)/(1 - 3*x + x^2) = 1 + x/(1 - 3*x + x^2) (see Agarwal (2000), p. 1424).

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^(2*n) - h^(-2*n))/sqrt(5), where h = (1+sqrt(5))/2.

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

Convolutions 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

a(n) = H(2*n, 1, 1/2) for n > 0 where H(n, a, b) = hypergeom([a - n/2, b - n/2], [1 - n], -4). - Peter Luschny, Sep 03 2019

INVERT transform of the identity function. - Alois P. Heinz, Feb 09 2021

Extensions

More terms from Ray Chandler, Nov 06 2003

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