login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A045623 Number of 1's in all compositions of n+1.
(Formerly M1412)
72

%I M1412

%S 1,2,5,12,28,64,144,320,704,1536,3328,7168,15360,32768,69632,147456,

%T 311296,655360,1376256,2883584,6029312,12582912,26214400,54525952,

%U 113246208,234881024,486539264,1006632960,2080374784,4294967296

%N Number of 1's in all compositions of n+1.

%C 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

%C a(n) = 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

%C 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

%C 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

%C 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

%C a(n) is the number of weak compositions of n with exactly 1 part equal to 0. - _Milan Janjic_, Jun 27 2010

%C 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

%C Equals first finite difference row of A001792: (1, 3, 8, 20, 48, 112, ...). - _Gary W. Adamson_, Oct 26 2010

%C With alternating signs the g.f. is: (-x^2-2*x-1) / (-4*x^2-4*x-1).

%C Number of 132-avoiding permutations of [n+2] containing exactly one 213 pattern. - _David Scambler_, Nov 07 2011

%C a(n) = 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

%C 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

%C 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

%C 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

%C 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

%D Czabarka, É., Flórez, R., Junes, L., & Ramírez, J. L. (2018). Enumerations of peaks and valleys on non-decreasing Dyck paths. Discrete Mathematics, 341(10), 2789-2807. See p. 2798.

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

%H Vincenzo Librandi, <a href="/A045623/b045623.txt">Table of n, a(n) for n = 0..1000</a>

%H Marco Abrate, Stefano Barbero, Umberto Cerruti, Nadir Murru, <a href="http://dx.doi.org/10.1016/j.disc.2014.06.026">Colored compositions, Invert operator and elegant compositions with the "black tie"</a>, Discrete Math. 335 (2014), 1--7. MR3248794.

%H Marco Abrate, Stefano Barbero, Umberto Cerruti, Nadir Murru, <a href="http://arxiv.org/abs/1409.6454">Colored compositions, Invert operator and elegant compositions with the "black tie"</a>, arXiv:1409.6454 [math.NT], 2014.

%H Ron M. Adin, Yuval Roichman, <a href="http://arxiv.org/abs/1301.1675">Matrices, Characters and Descents</a>, arXiv:1301.1675 [math.CO], (11-September-2013); see p.10

%H Michael Dairyko, Lara Pudwell, Samantha Tyner, Casey Wynn, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p22">Non-contiguous pattern avoidance in binary trees</a>. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013

%H F. Ellermann, <a href="/A001792/a001792.txt">Illustration of binomial transforms</a>

%H Nickolas Hein, Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.

%H V. E. Hoggatt, Jr., <a href="/A001628/a001628.pdf">Letters to N. J. A. Sloane, 1974-1975</a>

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Two Enumerative Functions</a>

%H M. Janjic and B. Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv 1301.4550 [math.CO], 2013.

%H M. Janjic, B. Petkovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic/janjic45.html">A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers</a>, J. Int. Seq. 17 (2014) # 14.3.5

%H Sergey Kitaev, Jeffrey Remmel, Mark Tiefenbruck, <a href="https://arxiv.org/abs/1302.2274">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, arXiv:1302.2274 [math.CO], 2013.

%H Sergey Kitaev, Jeffrey Remmel, Mark Tiefenbruck, <a href="https://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 (2015), #A16.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4).

%F 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

%F Binomial transform of 1,1,2,2,3,3,... . - _Paul Barry_, Mar 06 2003

%F a(0)=1, a(n)=(n+3)*2^(n-2), n >= 1. a(n+1) = 2*a(n) + 2^(n-1), n>0.

%F G.f.: (1-x)^2/((1-2*x)^2). - Detlef Pauly (dettodet(AT)yahoo.de), Mar 03 2003

%F G.f.: 1/(1-x-x^2-x^3-...)^2. - _Jon Perry_, Jul 04 2004

%F a(n) = sum_{0<=i_1<=i_2<=n} binomial(n, i_1+i_2). - _Benoit Cloitre_, Oct 14 2004

%F a(n) = Sum{k=0..n, C(n, k)*floor((k+2)/2)}. - _Paul Barry_, Mar 06 2003

%F a(n+1)-2a(n)= 0, 1, 2, 4, 8, 16, ... = A131577. - _Paul Curtz_, May 18 2008

%F 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

%F a(n) = Sum_{k=0..n} (k+1)*C(n-1,n-k). - _Peter Luschny_, Apr 20 2015

%e 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.

%e 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":

%e 01: [ 1:0 1:0 1:0 ]

%e 02: [ 1:0 1:0 1:1 ]

%e 03: [ 1:0 1:1 1:1 ]

%e 04: [ 1:0 2:0 ]

%e 05: [ 1:0 2:1 ]

%e 06: [ 1:1 1:1 1:1 ]

%e 07: [ 1:1 2:1 ]

%e 08: [ 2:0 1:0 ]

%e 09: [ 2:0 1:1 ]

%e 10: [ 2:1 1:1 ]

%e 11: [ 3:0 ]

%e 12: [ 3:1 ]

%e - _Joerg Arndt_, Apr 28 2013

%e 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

%p seq(ceil(1/4*2^n*(n+3)),n=0..50);

%t Table[ If[n == 0, 1, 2^(n - 2)(n + 3)], {n, 0, 29}] (* _Robert G. Wilson v_, Jun 27 2005 *)

%t CoefficientList[Series[(1 - 2x + x^2)/(-1 + 2x)^2, {x, 0, 30}], x] (* or *)

%t LinearRecurrence[{4, -4}, {1, 2, 5}, 31] (* _Robert G. Wilson v_, Feb 18 2018 *)

%o (PARI) a(n)=if(n<1,n==0,(n+3)*2^(n-2))

%o (Haskell)

%o a045623 n = a045623_list !! n

%o a045623_list = tail $ f a011782_list [] where

%o f (u:us) vs = sum (zipWith (*) vs $ reverse ws) : f us ws

%o where ws = u : vs

%o -- _Reinhard Zumkeller_, Jul 21 2013

%o (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

%Y Convolution of A011782. Row sums of A103450, A128254, A152195, A177992, A198069.

%Y Cf. A001792.

%K easy,nonn

%O 0,2

%A _Wolfdieter Lang_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 21 07:23 EDT 2019. Contains 321367 sequences. (Running on oeis4.)