A001793 a(n) = n*(n+3)*2^(n-3).

1, 5, 18, 56, 160, 432, 1120, 2816, 6912, 16640, 39424, 92160, 212992, 487424, 1105920, 2490368, 5570560, 12386304, 27394048, 60293120, 132120576, 288358400, 627048448, 1358954496, 2936012800, 6325010432, 13589544960, 29125246976

Offset: 1

Author

N. J. A. Sloane and Simon Plouffe

Keywords

• easy
• nonn

Comments

Coefficients of Chebyshev T polynomials: the subdiagonal A053120(n+3, n-1), for n > = 1. [rewritten by Wolfdieter Lang, Nov 25 2019]

Number of 132-avoiding permutations of [n+3] containing exactly two 123 patterns. - Emeric Deutsch, Jul 13 2001

Number of Dyck paths of semilength n+2 having pyramid weight n+1 (for pyramid weight see Denise and Simion). Example: a(2)=5 because the Dyck paths of semilength 4 having pyramid weight 3 are: (ud)u(ud)(ud)d, u(ud)(ud)d(ud), u(ud)(ud)(ud)d, u(ud)(uudd)d and u(uudd)(ud)d [here u=(1,1), d=(1,-1) and the maximal pyramids, of total length 3, are shown between parentheses]. - Emeric Deutsch, Mar 10 2004

a(n) is the number of dissections of a regular (n+3)-gon using n-1 noncrossing diagonals such that every piece of the dissection contains at least one non-base side of the (n+3)-gon. (One side of the (n+3)-gon is designated the base.) - David Callan, Mar 23 2004

If X_1,X_2,...,X_n are 2-blocks of a (2n+1)-set X then a(n) is the number of (n+2)-subsets of X intersecting each X_i, (i=1..n). - Milan Janjic, Nov 18 2007

The second corrector line for transforming 2^n offset 0 with a leading 1 into the Fibonacci sequence. - Al Hakanson (hawkuu(AT)gmail.com), Jun 01 2009

Sum of all nodes of all integer compositions of n, see example. - Olivier Gérard, Oct 22 2011

Number of compositions of 2n with exactly two odd summands (see example). - Mamuka Jibladze, Sep 04 2013

4*a(n) is the number of North-East paths from (0,0) to (n+2,n+2) with exactly two east steps below y = x-1 or above y = x+1. It is related to paired pattern P_1 and P_6 in Pan and Remmel's link. - Ran Pan, Feb 04 2016

From Paul Weisenhorn, Oct 18 2019: (Start)

The polynomials S(n,x)= Sum_(k>=1) b(n,k)*x^k has the recurrence relation S(n+2,x)=2*S(n+1,x))-x*S(n) with S(1,x)=1, S(2,x)=2-x and are generated by the coefficients b(n,k). b(n,k) is defined by b(n,k)=Sum_(j=1..k) binomials(k+1,j)*b(n-j,k) or by b(n,k)=((n-2+k)!*(n-1+2k)*2^n)/(4*(n-1)!*k!). b(n,1)=A001792, b(n,2)=A001793, b(n,3)=A001794, b(n,4)=A006974, b(n,5)=A006975, b(n,6)=A006976, b(n,7)=A209404.

The general formula for the sequences with k>=1: a(n)=((n-2+k)!*(n-1+2k)*2^n)/(4*(n-1)!*k!) with n >= 1. (End) [See a comment in A053120 on subdiagonal sequences. - Wolfdieter Lang, Jan 03 2020]

Examples

			a(2)=5 since 32415, 32451, 34125, 42135 and 52134 are the only 132-avoiding permutations of 12345 containing exactly two increasing subsequences of length 3.
a(4)=56: the compositions of 4 are 4, 3+1, 1+3, 2+2, 2+1+1, 1+2+1, 1+1+2, 1+1+1+1, the corresponding nodes (partial sums) are {0, 4}, {0, 3, 4}, {0, 1, 4}, {0, 2, 4}, {0, 2, 3, 4}, {0, 1, 3, 4}, {0, 1, 2, 4}, {0, 1, 2, 3, 4}, with individual sums {4, 7, 5, 6, 9, 8, 7, 10} and total 56. - _Olivier Gérard_, Oct 22 2011
The a(3)=18 compositions of 2*3=6 with two odd summands are 5+1, 1+5, 3+3, 4+1+1, 1+4+1, 1+1+4, 3+2+1, 3+1+2, 2+3+1, 2+1+3, 1+3+2, 1+2+3, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+2+2+1, 1+2+1+2, 1+1+2+2. - _Mamuka Jibladze_, Sep 04 2013
		

References

• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 795.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 1..500
• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
• Jean-Luc Baril, Sergey Kirgizov and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
• David Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.
• Robert Davis and Greg Simay, Further Combinatorics and Applications of Two-Toned Tilings, arXiv:2001.11089 [math.CO], 2020.
• Alain Denise and Rodica Simion, Two combinatorial statistics on Dyck paths, Discrete Math., Vol. 137, No. 1-3 (1995), pp. 155-176.
• Filippo Disanto, Some Statistics on the Hypercubes of Catalan Permutations, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2.
• Milan Janjic, Two Enumerative Functions.
• Milan Janjić, On Restricted Ternary Words and Insets, arXiv:1905.04465 [math.CO], 2019.
• C. W. Jones, J. C. P. Miller, J. F. C. Conn and R. C. Pankhurst, Tables of Chebyshev polynomials Proc. Roy. Soc. Edinburgh. Sect. A., Vol. 62, No. 2 (1946), pp. 187-203.
• Igor Makhlin, Gröbner fans of Hibi ideals, generalized Hibi ideals and flag varieties, arXiv:2003.02916 [math.CO], 2020.
• Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
• Lara Pudwell, Connor Scholten, Tyler Schrock and Alexa Serrato, Noncontiguous pattern containment in binary trees, ISRN Comb. 2014, Article ID 316535, 8 p. (2014), tr_{t4}(n,2).
• Aaron Robertson, Herbert S. Wilf and Doron Zeilberger, Permutation patterns and continued fractions, Electr. J. Combin., Vol. 6 (1999), Article R38.
• I. Tasoulas, K. Manes, and A. Sapounakis, Hamiltonian intervals in the lattice of binary paths, Elect. J. Comb. (2024) Vol. 31, Issue 1, P1.39.
• Index entries for sequences related to Chebyshev polynomials.
• Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Crossrefs

a(n) = A039991(n+3, 4) = A055252(n, 1).

Cf. A058396, A058645.

Cf. A053120.

Programs

GAP

List([1..30], n-> 2^(n-3)*n*(n+3) ); # G. C. Greubel, Nov 06 2019

Magma

[2^(n-3)*n*(n+3): n in [1..30]]; // G. C. Greubel, Nov 06 2019

Maple

A001793 := n*(n+3)*2^(n-3); seq(A001793(n), n=1..40);
A001793:=(-1+z)/(2*z-1)**3; # Simon Plouffe in his 1992 dissertation.

Mathematica

Table[n(n+3)*2^(n-3), {n, 28}] (* or *) Rest@ CoefficientList[Series[x(1-x)/(1-2x)^3, {x, 0, 28}], x] (* Michael De Vlieger, Sep 21 2017 *)

PARI

a(n)=n*(n+3)<<(n-3) \\ Charles R Greathouse IV, Sep 24 2015

Sage

[2^(n-3)*n*(n+3) for n in (1..30)] # G. C. Greubel, Nov 06 2019

Formula

G.f.: x*(1-x)/(1-2*x)^3. Binomial transform of squares [1, 4, 9, ...].

a(n) = Sum_{k=0..floor((n+4)/2)} C(n+4, 2k)*C(k, 2). - Paul Barry, May 15 2003

With two leading zeros, binomial transform of quarter-squares A002620. - Paul Barry, May 27 2003

a(n) = Sum_{k=0..n+2} C(n+2, k) * floor(k^2/4). - Paul Barry, May 27 2003

a(n) = Sum_{i=0..j} binomial(i+1, 2)*binomial(j, i). - Jon Perry, Feb 26 2004

With one leading zero, binomial transform of triangular numbers A000217. - Philippe Deléham, Aug 02 2005

a(n) = Sum_{k=0..n+1} (-1)^(n-k+1)*C(k, n-k+1)*k*C(2k, k)/2. - Paul Barry, Oct 07 2005

Left-shifted sequence is binomial transform of left-shifted squares (A000290). - Franklin T. Adams-Watters, Nov 29 2006

Binomial transform of a(n) = n^2 offset 1. a(3)=18. - Al Hakanson (hawkuu(AT)gmail.com), Jun 01 2009

a(n) = (1/n) * Sum_{k=0..n} binomial(n,k)*k^3. - Gary Detlefs, Nov 26 2011

For n > 1, a(n) = Sum_{k=0..n-1} Sum_{i=0..n} (k+2) * C(n-2,i). - Wesley Ivan Hurt, Sep 20 2017

a(n) = a(-3-n)*2^(2*n+3), a(n)*(n+3) = -A058645(-3-n)*2^(2*n+3) for all n in Z. - Michael Somos, Apr 19 2019

E.g.f.: (1/2)*exp(2*x)*x*(2 + x). - Stefano Spezia, Aug 17 2019

From Amiram Eldar, Jan 05 2022: (Start)

Sum_{n>=1} 1/a(n) = 128/9 - 56*log(2)/3.

Sum_{n>=1} (-1)^(n+1)/a(n) = 24*log(3/2) - 80/9. (End)