|
|
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) + ...
|
|
38
|
|
|
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
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
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
|
|
REFERENCES
|
R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
|
|
LINKS
|
|
|
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
|
|
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
|
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)):
# third Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
add(a(n-i)*i, i=1..n))
end:
|
|
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 *)
|
|
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]
(PARI)
N=66; x='x+O('x^N);
Vec( 1/( 1 - sum(k=1, N, k*x^k ) ) )
(Magma) [1] cat [Fibonacci(2*n): n in [1..40]]; // G. C. Greubel, Dec 16 2022
(SageMath)
def A088305(n): return 1 if (n==0) else fibonacci(2*n)
|
|
CROSSREFS
|
Apart from initial term, same as A001906.
|
|
KEYWORD
|
easy,nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Further terms from Edward Scheinerman (ers(AT)jhu.edu), Feb 28 2007
|
|
STATUS
|
approved
|
|
|
|