|
%I #142 Mar 09 2024 12:32:29
%S 1,1,3,8,21,55,144,377,987,2584,6765,17711,46368,121393,317811,832040,
%T 2178309,5702887,14930352,39088169,102334155,267914296,701408733,
%U 1836311903,4807526976,12586269025,32951280099,86267571272,225851433717
%N 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 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 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 Row sums of triangle A128908. - _Philippe Deléham_, Nov 21 2007
%C 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 Eigensequence of triangle A004736. - _Paul Barry_, Nov 03 2010
%C a(n) = the sum of the products of all compositions of n.
%C 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 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 R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
%H Vincenzo Librandi, <a href="/A088305/b088305.txt">Table of n, a(n) for n = 0..1000</a>
%H 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 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 Meghann M. Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of Compositions</a>, Electronic Theses & Dissertations, Georgia Southern University, 2017.
%H 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 Â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 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 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 Luigi Santocanale, <a href="https://arxiv.org/abs/1906.05590">On discrete idempotent paths</a>, arXiv:1906.05590 [math.LO], 2019.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1).
%F a(n) = 1*a(n-1) + 2*a(n-2) + 3*a(n-3) + 4*a(n-4) + ...
%F 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 G.f.: 1/(1 - Sum_{k >= 1} k*x^k). - _Joerg Arndt_, Jun 21 2011
%F G.f.: Sum_{n >= 0} q^n / (1 - q)^(2*n). - _Joerg Arndt_, Dec 09 2012
%F a(0) = 1, a(n) = (h^(2*n) - h^(-2*n))/sqrt(5), where h = (1+sqrt(5))/2.
%F 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 a(n) = (((3 + sqrt(5))/2)^n - ((3 - sqrt(5))/2)^n)/sqrt(5). - _Geoffrey Critzer_, Sep 23 2008
%F F(2n) = 1*F(2n-2) + 2*F(2n-4) + 3*F(2n-6) + 4*F(2n-8) + ...
%F F(2n+1) = 1 + 1*F(2n-1) + 2*F(2n-3) + 3*F(2n-5) + 4*F(2n-7) + ...
%F Convolutions with 1, 3, 6, 10, ..., n*(n+1)/2:
%F 1*F(2n) + 3*F(2n-2) + 6*F(2n-4) + 10*F(2n-6) + ... = F(2n+3) - 1.
%F 1*F(2n-1) + 3*F(2n-3) + 6*F(2n-5) + 10*F(2n-7) + ... = F(2n+2) - n - 1.
%F 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 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 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 INVERT transform of the identity function. - _Alois P. Heinz_, Feb 09 2021
%e a(5) = 55 = 1*21 + 2*8 + 3*3 + 4*1 + 5*1 = 21 + 16 + 9 + 4 + 5.
%e a(3) = 8 because if we multiply the compositions of three:
%e 3; 2,1; 1,2; 1,1,1, we get 3,2,2,1 respectively, which sums to eight.
%p H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):
%p a := n -> `if`(n = 0, 1, H(2*n, 1, 1/2)):
%p seq(simplify(a(n)), n=0..28); # _Peter Luschny_, Sep 03 2019
%p # third Maple program:
%p a:= proc(n) option remember; `if`(n=0, 1,
%p add(a(n-i)*i, i=1..n))
%p end:
%p seq(a(n), n=0..36); # _Alois P. Heinz_, Feb 09 2021
%t f[list_]:=Apply[Times,list]; Table[Total[Map[f, Level[Map[Permutations, Partitions[n]], {2}]]], {n, 0, 20}]
%t CoefficientList[Series[(1 - 2 x + x^2)/(1 - 3 x + x^2), {x, 0, 40}], x] (* _Vincenzo Librandi_, Mar 16 2014 *)
%t Join[{1}, Fibonacci[2*Range[40]]] (* _G. C. Greubel_, Dec 16 2022 *)
%o (Python)
%o def a(n, adict={0:1, 1:1, 2:3}):
%o if n in adict:
%o return adict[n]
%o adict[n]=3*a(n-1)-a(n-2)
%o return adict[n]
%o # _David Nacin_, Mar 04 2012
%o (PARI)
%o N=66; x='x+O('x^N);
%o Vec( 1/( 1 - sum(k=1,N, k*x^k ) ) )
%o /* _Joerg Arndt_, Sep 30 2012 */
%o (Magma) [1] cat [Fibonacci(2*n): n in [1..40]]; // _G. C. Greubel_, Dec 16 2022
%o (SageMath)
%o def A088305(n): return 1 if (n==0) else fibonacci(2*n)
%o [A088305(n) for n in range(41)] # _G. C. Greubel_, Dec 16 2022
%Y Cf. A000012, A000045, A004736, A128908, A153463.
%Y Apart from initial term, same as A001906.
%K easy,nonn
%O 0,3
%A _Miklos Kristof_, Nov 05 2003
%E More terms from _Ray Chandler_, Nov 06 2003
%E Further terms from Edward Scheinerman (ers(AT)jhu.edu), Feb 28 2007
|
