|
%I M1412 #217 Feb 26 2023 19:34:39
%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,8858370048,18253611008,37580963840
%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) 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
%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: (1 + x)^2/(1 + 2*x)^2.
%C Number of 132-avoiding permutations of [n+2] containing exactly one 213 pattern. - _David Scambler_, Nov 07 2011
%C 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
%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
%C 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
%C 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
%C Also the number of "special permutations" in the Weng and Zagier reference. - _F. Chapoton_, Sep 30 2022
%C 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
%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 and 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., Vol. 335 (2014), pp. 1-7. MR3248794.
%H Marco Abrate, Stefano Barbero, Umberto Cerruti and 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 and Yuval Roichman, <a href="http://arxiv.org/abs/1301.1675">Matrices, Characters and Descents</a>, arXiv:1301.1675 [math.CO], 2013-2014; see p.10.
%H Félix Balado and Guénolé C. M. Silvestre, <a href="https://arxiv.org/abs/2302.11532">Runs of Ones in Binary Strings</a>, arXiv:2302.11532 [math.CO], 2023. See pp. 6-7.
%H Freddy Cachazo and Nick Early, <a href="https://arxiv.org/abs/2010.09708">Planar Kinematics: Cyclic Fixed Points, Mirror Superpotential, k-Dimensional Catalan Numbers, and Root Polytopes</a>, arXiv:2010.09708 [math.CO], 2020.
%H Camille Combe, <a href="https://arxiv.org/abs/2007.00048">A geometric and combinatorial exploration of Hochschild lattices</a>, arXiv:2007.00048 [math.CO], 2020.
%H Éva Czabarka, Rigoberto Flórez, Leandro Junes and José L. Ramírez, <a href="https://doi.org/10.1016/j.disc.2018.06.032">Enumerations of peaks and valleys on non-decreasing Dyck paths</a>, Discrete Math., Vol. 341, No. 10 (2018), pp. 2789-2807. See p. 2798.
%H Michael Dairyko, Lara Pudwell, Samantha Tyner and Casey Wynn, <a href="https://doi.org/10.37236/2099">Non-contiguous pattern avoidance in binary trees</a>. Electron. J. Combin., Vol. 19, No. 3 (2012), Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013
%H Robert Davis and Greg Simay, <a href="https://arxiv.org/abs/2001.11089">Further Combinatorics and Applications of Two-Toned Tilings</a>, arXiv:2001.11089 [math.CO], 2020.
%H Frank Ellermann, <a href="/A001792/a001792.txt">Illustration of binomial transforms</a>.
%H Nickolas Hein and 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="https://pmf.unibl.org/wp-content/uploads/2017/10/enumfor.pdf">Two Enumerative Functions</a>.
%H Milan Janjic and Boris Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv 1301.4550 [math.CO], 2013.
%H Milan Janjic and Boris 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., Vol. 17 (2014), Article 14.3.5.
%H Sergey Kitaev, Jeffrey Remmel and 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 and 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, Vol. 15 (2015), Article A16.
%H Henri Mühle <a href="https://arxiv.org/abs/2008.13247">Hochschild lattices and shuffle lattices</a>, arXiv:2008.13247 [math.CO], 2020.
%H Koushik Sinha and Bhabani P. Sinha, <a href="https://doi.org/10.1016/j.camwa.2009.07.057">On the distribution of runs of ones in binary strings</a>, Computers & Mathematics with Applications, Vol. 58, No. 9 (2009), pp. 1816-1829.
%H Lin Weng and Don Zagier, <a href="https://doi.org/10.1073/pnas.1912501117">Higher-rank zeta functions and SLn-zeta functions for curves</a>, PNAS 117 (12), 2020.
%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.
%F 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 <= j <= k <= n} binomial(n, j+k). - _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) - 2*a(n) = A131577(n). - _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
%F 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
%F 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
%F E.g.f.: (1 + exp(2*x)*(3 + 2*x))/4. - _Stefano Spezia_, Dec 19 2021
%F From _Amiram Eldar_, Jan 05 2022: (Start)
%F Sum_{n>=0} 1/a(n) = 32*log(2) - 61/3.
%F Sum_{n>=0} (-1)^n/a(n) = 32*log(3/2) - 37/3. (End)
%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
%e 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
%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
%o (Maxima)
%o 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 */
%Y Convolution of A011782.
%Y Row sums of A103450, A128254, A152195, A177992, A198069.
%Y Cf. A001792.
%K easy,nonn
%O 0,2
%A _Wolfdieter Lang_
|
