cp's OEIS Frontend

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

%I A088305 #142 Mar 09 2024 12:32:29
%S A088305 1,1,3,8,21,55,144,377,987,2584,6765,17711,46368,121393,317811,832040,
%T A088305 2178309,5702887,14930352,39088169,102334155,267914296,701408733,
%U A088305 1836311903,4807526976,12586269025,32951280099,86267571272,225851433717
%N 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) + ...
%C A088305 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
%C A088305 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
%C A088305 Row sums of triangle A128908. - _Philippe Deléham_, Nov 21 2007
%C A088305 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
%C A088305 Eigensequence of triangle A004736. - _Paul Barry_, Nov 03 2010
%C A088305 a(n) = the sum of the products of all compositions of n.
%C A088305 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
%C A088305 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
%D A088305 R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
%H A088305 Vincenzo Librandi, <a href="/A088305/b088305.txt">Table of n, a(n) for n = 0..1000</a>
%H A088305 A. K. Agarwal, <a href="https://web.archive.org/web/20200714215813/https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005b15_1421.pdf">n-colour compositions</a>, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
%H A088305 Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See pp 25, 29.
%H A088305 Meghann M. Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of Compositions</a>, Electronic Theses & Dissertations, Georgia Southern University, 2017.
%H A088305 Meghann Moriah Gibson, Daniel Gray, and Hua Wang, <a href="https://doi.org/10.1016/j.disc.2018.08.001">Combinatorics of n-color compositions</a>, Discrete Mathematics 341 (2018), 3209-3226.
%H A088305 Ângela Mestre and José Agapito, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL22/Mestre/mestre2.html">Square Matrices Generated by Sequences of Riordan Arrays</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
%H A088305 V. Retakh, S. Serconek, and R. Wilson,  <a href="http://arxiv.org/abs/1010.6295">Hilbert Series of Algebras Associated to Directed Graphs and Order Homology</a>, arXiv:1010.6295 [math.RA], 2010-2011.
%H A088305 J. Salas and A. D. Sokal, <a href="http://arxiv.org/abs/0711.1738">Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial</a>, 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
%H A088305 Luigi Santocanale, <a href="https://arxiv.org/abs/1906.05590">On discrete idempotent paths</a>, arXiv:1906.05590 [math.LO], 2019.
%H A088305 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1).
%F A088305 a(n) = 1*a(n-1) + 2*a(n-2) + 3*a(n-3) + 4*a(n-4) + ...
%F A088305 G.f.: (1 -2*x + x^2)/(1 - 3*x + x^2) = 1 + x/(1 - 3*x + x^2) (see Agarwal (2000), p. 1424).
%F A088305 G.f.: 1/(1 - Sum_{k >= 1} k*x^k). - _Joerg Arndt_, Jun 21 2011
%F A088305 G.f.: Sum_{n >= 0} q^n / (1 - q)^(2*n). - _Joerg Arndt_, Dec 09 2012
%F A088305 a(0) = 1, a(n) = (h^(2*n) - h^(-2*n))/sqrt(5), where h = (1+sqrt(5))/2.
%F A088305 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
%F A088305 a(n) = (((3 + sqrt(5))/2)^n - ((3 - sqrt(5))/2)^n)/sqrt(5). - _Geoffrey Critzer_, Sep 23 2008
%F A088305 F(2n) = 1*F(2n-2) + 2*F(2n-4) + 3*F(2n-6) + 4*F(2n-8) + ...
%F A088305 F(2n+1) = 1 + 1*F(2n-1) + 2*F(2n-3) + 3*F(2n-5) + 4*F(2n-7) + ...
%F A088305 Convolutions with 1, 3, 6, 10, ..., n*(n+1)/2:
%F A088305 1*F(2n) + 3*F(2n-2) + 6*F(2n-4) + 10*F(2n-6) + ... = F(2n+3) - 1.
%F A088305 1*F(2n-1) + 3*F(2n-3) + 6*F(2n-5) + 10*F(2n-7) + ... = F(2n+2) - n - 1.
%F A088305 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
%F A088305 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
%F A088305 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
%F A088305 INVERT transform of the identity function. - _Alois P. Heinz_, Feb 09 2021
%e A088305 a(5) = 55 = 1*21 + 2*8 + 3*3 + 4*1 + 5*1 = 21 + 16 + 9 + 4 + 5.
%e A088305 a(3) = 8 because if we multiply the compositions of three:
%e A088305 3; 2,1; 1,2; 1,1,1, we get 3,2,2,1 respectively, which sums to eight.
%p A088305 H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):
%p A088305 a := n -> `if`(n = 0, 1, H(2*n, 1, 1/2)):
%p A088305 seq(simplify(a(n)), n=0..28); # _Peter Luschny_, Sep 03 2019
%p A088305 # third Maple program:
%p A088305 a:= proc(n) option remember; `if`(n=0, 1,
%p A088305       add(a(n-i)*i, i=1..n))
%p A088305     end:
%p A088305 seq(a(n), n=0..36);  # _Alois P. Heinz_, Feb 09 2021
%t A088305 f[list_]:=Apply[Times,list]; Table[Total[Map[f, Level[Map[Permutations, Partitions[n]], {2}]]], {n, 0, 20}]
%t A088305 CoefficientList[Series[(1 - 2 x + x^2)/(1 - 3 x + x^2), {x, 0, 40}], x] (* _Vincenzo Librandi_, Mar 16 2014 *)
%t A088305 Join[{1}, Fibonacci[2*Range[40]]] (* _G. C. Greubel_, Dec 16 2022 *)
%o A088305 (Python)
%o A088305 def a(n, adict={0:1, 1:1, 2:3}):
%o A088305     if n in adict:
%o A088305         return adict[n]
%o A088305     adict[n]=3*a(n-1)-a(n-2)
%o A088305     return adict[n]
%o A088305 # _David Nacin_, Mar 04 2012
%o A088305 (PARI)
%o A088305 N=66;  x='x+O('x^N);
%o A088305 Vec( 1/( 1 - sum(k=1,N, k*x^k ) ) )
%o A088305 /* _Joerg Arndt_, Sep 30 2012 */
%o A088305 (Magma) [1] cat [Fibonacci(2*n): n in [1..40]]; // _G. C. Greubel_, Dec 16 2022
%o A088305 (SageMath)
%o A088305 def A088305(n): return 1 if (n==0) else fibonacci(2*n)
%o A088305 [A088305(n) for n in range(41)] # _G. C. Greubel_, Dec 16 2022
%Y A088305 Cf. A000012, A000045, A004736, A128908, A153463.
%Y A088305 Apart from initial term, same as A001906.
%K A088305 easy,nonn
%O A088305 0,3
%A A088305 _Miklos Kristof_, Nov 05 2003
%E A088305 More terms from _Ray Chandler_, Nov 06 2003
%E A088305 Further terms from Edward Scheinerman (ers(AT)jhu.edu), Feb 28 2007