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
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 (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) = 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: (-x^2-2*x-1) / (-4*x^2-4*x-1).

Number of 132-avoiding permutations of [n+2] containing exactly one 213 pattern. - David Scambler, Nov 07 2011

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

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

REFERENCES

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.

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Marco Abrate, Stefano Barbero, Umberto Cerruti, Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", Discrete Math. 335 (2014), 1--7. MR3248794.

Marco Abrate, Stefano Barbero, Umberto Cerruti, Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", arXiv:1409.6454 [math.NT], 2014.

Ron M. Adin, Yuval Roichman, Matrices, Characters and Descents, arXiv:1301.1675 [math.CO], (11-September-2013); see p.10

Michael Dairyko, Lara Pudwell, Samantha Tyner, Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From N. J. A. Sloane, Feb 01 2013

F. Ellermann, Illustration of binomial transforms

Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.

V. E. Hoggatt, Jr., Letters to N. J. A. Sloane, 1974-1975

Milan Janjic, Two Enumerative Functions

M. Janjic and B. Petkovic, A Counting Function, arXiv 1301.4550 [math.CO], 2013.

M. Janjic, B. Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5

Sergey Kitaev, Jeffrey Remmel, Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, arXiv:1302.2274 [math.CO], 2013.

Sergey Kitaev, Jeffrey Remmel, Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 (2015), #A16.

Index entries for linear recurrences with constant coefficients, signature (4,-4).

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<=i_1<=i_2<=n} binomial(n, i_1+i_2). - 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)-2a(n)= 0, 1, 2, 4, 8, 16, ... = A131577. - 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

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  ]

- 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

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 *)

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

-- Reinhard Zumkeller, Jul 21 2013

(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

CROSSREFS

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

Cf. A001792.

Sequence in context: A006979 A019301 A006980 * A290990 A324586 A001410

Adjacent sequences:  A045620 A045621 A045622 * A045624 A045625 A045626

KEYWORD

easy,nonn

AUTHOR

Wolfdieter Lang

STATUS

approved

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 May 21 09:15 EDT 2019. Contains 323441 sequences. (Running on oeis4.)