cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A045623 Number of 1's in all compositions of n+1.

Original entry on oeis.org

1, 2, 5, 12, 28, 64, 144, 320, 704, 1536, 3328, 7168, 15360, 32768, 69632, 147456, 311296, 655360, 1376256, 2883584, 6029312, 12582912, 26214400, 54525952, 113246208, 234881024, 486539264, 1006632960, 2080374784, 4294967296, 8858370048, 18253611008, 37580963840
Offset: 0

Views

Author

Wolfdieter Lang

Keywords

Comments

Let M_n be the n X n matrix m_(i,j) = 2 + abs(i-j) then det(M_n) = (-1)^(n-1)*a(n-1). - Benoit Cloitre, May 28 2002
a(n) is the number of triangulations of a regular (n+3)-gon in which every triangle shares at least one side with the polygon itself. - David Callan, Mar 25 2004
Number of compositions of j+n, j>n and j the maximum part. E.g. a(4) is derived from the number of compositions of, for example: 54(2), 531(6), 522(3), 5211(12) and 51111(5) giving 2+6+3+12+5=28. - Jon Perry, Sep 13 2005
If X_1,X_2,...,X_n are 2-blocks of a (2n+2)-set X then, for n>=1, a(n+1) is the number of (n+1)-subsets of X intersecting each X_i, (i=1,2,...,n). - Milan Janjic, Nov 18 2007
Generated from iterates of M * [1,1,1,...], where M = an infinite triadiagonal matrix with (1,1,1,...) in the main and superdiagonals and (1,0,0,0,...) in the subdiagonal. - Gary W. Adamson, Jan 04 2009
a(n) is the number of weak compositions of n with exactly 1 part equal to 0. - Milan Janjic, Jun 27 2010
An elephant sequence, see A175654. For the corner squares 16 A[5] vectors, with decimal values between 19 and 400, lead to this sequence. For the central square these vectors lead to the companion sequence A045891 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010
Equals first finite difference row of A001792: (1, 3, 8, 20, 48, 112, ...). - Gary W. Adamson, Oct 26 2010
With alternating signs the g.f. is: (1 + x)^2/(1 + 2*x)^2.
Number of 132-avoiding permutations of [n+2] containing exactly one 213 pattern. - David Scambler, Nov 07 2011
a(n) is the number of 1's in all compositions of n+1 = the number of 2's in all compositions of n+2 = the number of 3's in all compositions of n+3 = ... So the partial sums = A001792. - Geoffrey Critzer, Feb 12 2012
Also number of compositions of n into 2 sorts of parts where all parts of the first sort precede all parts of the second sort; see example. - Joerg Arndt, Apr 28 2013
a(n) is also the difference of the total number of parts between all compositions of n+1 and all compositions of n. The equivalent sequence for partitions is A138137. - Omar E. Pol, Aug 28 2013
Except for an initial 1, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = (1 - S)^2; see A291000. - Clark Kimberling, Aug 24 2017
For a composition of n, the total number of runs of parts of size k is a(n-k) - a(n-2k). - Gregory L. Simay, Feb 17 2018
a(n) is the number of binary trees on n+1 nodes that are isomorphic to a path graph. The ratio of a(n)/A000108(n+1) gives the probability that a random Catalan tree on n+1 nodes is isomorphic to a path graph. - Marcel K. Goh, May 09 2020
a(n) is the number of words of length n over the alphabet {0,1,2} such that the first letter is not 2 and the last 1 occurs before the first 0. - Henri Mühle, Mar 08 2021
Also the number of "special permutations" in the Weng and Zagier reference. - F. Chapoton, Sep 30 2022
a(n-k) is the total number of runs of 1s of length k over all binary n-strings. - Félix Balado, Dec 11 2022

Examples

			E.g. a(2)=5 because in the compositions of 3, namely 3,2+1,1+2,1+1+1, we have five 1's altogether.
There are a(3)=12 compositions of 3 into 2 sorts of parts where all parts of the first sort precede all parts of the second sort. Here p:s stands for "part p of sort s":
01:  [ 1:0  1:0  1:0  ]
02:  [ 1:0  1:0  1:1  ]
03:  [ 1:0  1:1  1:1  ]
04:  [ 1:0  2:0  ]
05:  [ 1:0  2:1  ]
06:  [ 1:1  1:1  1:1  ]
07:  [ 1:1  2:1  ]
08:  [ 2:0  1:0  ]
09:  [ 2:0  1:1  ]
10:  [ 2:1  1:1  ]
11:  [ 3:0  ]
12:  [ 3:1  ]
- _Joerg Arndt_, Apr 28 2013
For the compositions of 6, the total number of runs of parts of size 2 is a(6-2) - a(6-2*2) = 28 - 5 = 23, enumerated as follows (with the runs of 2 enclosed in []): 4,[2]; [2],4; [2],3,1; [2],1,3; 3,[2],1; 1,[2],3; 3,1,[2]; 1,3,[2]; [2,2,2]; [2,2],1,1; 1,[2,2],1; 1,1,[2,2]; [2],1,[2],1; 1,[2],1,[2]; [2],1,1,[2]; [2],1,1,1,1; 1,[2],1,1,1; 1,1,[2],1,1; 1,1,1,[2],1; and 1,1,1,1[2]. - _Gregory L. Simay_, Feb 17 2018
There are a(3)=12 triwords of length 3: (0,0,0), (0,0,2), (0,2,0), (0,2,2), (1,0,0), (1,0,2), (1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2). - _Henri Mühle_, Mar 08 2021

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Convolution of A011782.
Row sums of A103450, A152195, A177992, A198069.
Cf. A001792.

Programs

  • GAP
    a:=[2,5];; for n in [3..40] do a[n]:=4*a[n-1]-4*a[n-2]; od; Concatenation([1],a); # Muniru A Asiru, Oct 16 2018
  • Haskell
    a045623 n = a045623_list !! n
a045623_list = tail $ f a011782_list [] where
   f (u:us) vs = sum (zipWith (*) vs $ reverse ws) : f us ws
     where ws = u : vs
-- Reinhard Zumkeller, Jul 21 2013
  • Maple
    seq(ceil(1/4*2^n*(n+3)),n=0..50);
  • Mathematica
    Table[If[n==0, 1, 2^(n-2)(n+3)], {n, 0, 29}] (* Robert G. Wilson v, Jun 27 2005 *)
CoefficientList[Series[(1 -2x +x^2)/(1-2x)^2, {x, 0, 30}], x] (* or *)
LinearRecurrence[{4, -4}, {1, 2, 5}, 31] (* Robert G. Wilson v, Feb 18 2018 *)
  • Maxima
    a(n):=sum(((2*m+2)*n-2*m^2+1)*binomial(2*n+2,2*m+1),m,0,n)/((4*n+2)*2^n); /* Vladimir Kruchinin, Nov 01 2020 */
  • PARI
    a(n)=if(n<1,n==0,(n+3)*2^(n-2))

Formula

Sum_{k = 0..n} (k+2)*binomial(n,k) gives the sequence but with a different offset: 2, 5, 12, 28, 64, 144, 320, 704, 1536, ... - N. J. A. Sloane, Jan 30 2008 - formula corrected by Robert G. Wilson v, Feb 26 2018
Binomial transform of 1,1,2,2,3,3,... . - Paul Barry, Mar 06 2003
a(0)=1, a(n) = (n+3)*2^(n-2), n >= 1.
a(n+1) = 2*a(n) + 2^(n-1), n>0.
G.f.: (1-x)^2/(1-2*x)^2. - Detlef Pauly (dettodet(AT)yahoo.de), Mar 03 2003
G.f.: 1/(1-x-x^2-x^3-...)^2. - Jon Perry, Jul 04 2004
a(n) = Sum_{0 <= j <= k <= n} binomial(n, j+k). - Benoit Cloitre, Oct 14 2004
a(n) = Sum_{k=0..n} C(n, k)*floor((k+2)/2). - Paul Barry, Mar 06 2003
a(n+1) - 2*a(n) = A131577(n). - Paul Curtz, May 18 2008
G.f.: 1/(1-x) + Q(0)*x/(1-x)^3, where Q(k)= 1 + (k+1)*x/(1 - x - x*(1-x)/(x + (k+1)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 25 2013
a(n) = Sum_{k=0..n} (k+1)*C(n-1,n-k). - Peter Luschny, Apr 20 2015
a(n) = Sum_{k=0..n-1} a(k) + 2^(n-1) = A001787(n-1) + 2^n, a(0)=1. - Yuchun Ji, May 22 2020
a(n) = Sum_{m=0..n}((2*m+2)*n-2*m^2+1)*C(2*n+2,2*m+1)/((4*n+2)*2^n). - Vladimir Kruchinin, Nov 01 2020
E.g.f.: (1 + exp(2*x)*(3 + 2*x))/4. - Stefano Spezia, Dec 19 2021
From Amiram Eldar, Jan 05 2022: (Start)
Sum_{n>=0} 1/a(n) = 32*log(2) - 61/3.
Sum_{n>=0} (-1)^n/a(n) = 32*log(3/2) - 37/3. (End)

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.