|
|
A045623
|
|
Number of 1's in all compositions of n+1.
(Formerly M1412)
|
|
80
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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
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
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
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
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
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)
|
|
EXAMPLE
|
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 ]
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
|
|
MAPLE
|
seq(ceil(1/4*2^n*(n+3)), n=0..50);
|
|
MATHEMATICA
|
CoefficientList[Series[(1 -2x +x^2)/(1-2x)^2, {x, 0, 30}], x] (* or *)
|
|
PROG
|
(PARI) a(n)=if(n<1, n==0, (n+3)*2^(n-2))
(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
(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
(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 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|