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. - 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
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).
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)):
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 *)
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 */
(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)
[A088305(n) for n in range(41)] # G. C. Greubel, Dec 16 2022
CROSSREFS
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