|
%I M3881 N1591 #177 Mar 31 2024 17:26:02
%S 1,5,18,56,160,432,1120,2816,6912,16640,39424,92160,212992,487424,
%T 1105920,2490368,5570560,12386304,27394048,60293120,132120576,
%U 288358400,627048448,1358954496,2936012800,6325010432,13589544960,29125246976
%N a(n) = n*(n+3)*2^(n-3).
%C Coefficients of Chebyshev T polynomials: the subdiagonal A053120(n+3, n-1), for n > = 1. [rewritten by _Wolfdieter Lang_, Nov 25 2019]
%C Number of 132-avoiding permutations of [n+3] containing exactly two 123 patterns. - _Emeric Deutsch_, Jul 13 2001
%C 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
%C 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
%C 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
%C 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
%C Sum of all nodes of all integer compositions of n, see example. - _Olivier Gérard_, Oct 22 2011
%C Number of compositions of 2n with exactly two odd summands (see example). - _Mamuka Jibladze_, Sep 04 2013
%C 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
%C From _Paul Weisenhorn_, Oct 18 2019: (Start)
%C 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.
%C 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]
%D 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.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001793/b001793.txt">Table of n, a(n) for n = 1..500</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H Jean-Luc Baril, Sergey Kirgizov and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1803.06706">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, arXiv:1803.06706 [math.CO], 2018.
%H David Callan, <a href="https://arxiv.org/abs/math/0211380">A recursive bijective approach to counting permutations containing 3-letter patterns</a>, arXiv:math/0211380 [math.CO], 2002.
%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 Alain Denise and Rodica Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., Vol. 137, No. 1-3 (1995), pp. 155-176.
%H Filippo Disanto, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Disanto/disanto5.html">Some Statistics on the Hypercubes of Catalan Permutations</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2.
%H Milan Janjic, <a href="https://pmf.unibl.org/wp-content/uploads/2017/10/enumfor.pdf">Two Enumerative Functions</a>.
%H Milan Janjić, <a href="https://arxiv.org/abs/1905.04465">On Restricted Ternary Words and Insets</a>, arXiv:1905.04465 [math.CO], 2019.
%H C. W. Jones, J. C. P. Miller, J. F. C. Conn and R. C. Pankhurst, <a href="http://dx.doi.org/10.1017/S0080454100006579">Tables of Chebyshev polynomials</a> Proc. Roy. Soc. Edinburgh. Sect. A., Vol. 62, No. 2 (1946), pp. 187-203.
%H Igor Makhlin, <a href="https://arxiv.org/abs/2003.02916">Gröbner fans of Hibi ideals, generalized Hibi ideals and flag varieties</a>, arXiv:2003.02916 [math.CO], 2020.
%H Ran Pan and Jeffrey B. Remmel, <a href="https://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H Lara Pudwell, Connor Scholten, Tyler Schrock and Alexa Serrato, <a href="https://doi.org/10.1155/2014/316535">Noncontiguous pattern containment in binary trees</a>, ISRN Comb. 2014, Article ID 316535, 8 p. (2014), tr_{t4}(n,2).
%H Aaron Robertson, Herbert S. Wilf and Doron Zeilberger, <a href="https://doi.org/10.37236/1470">Permutation patterns and continued fractions</a>, Electr. J. Combin., Vol. 6 (1999), Article R38.
%H I. Tasoulas, K. Manes, and A. Sapounakis, <a href="https://doi.org/10.37236/12144">Hamiltonian intervals in the lattice of binary paths</a>, Elect. J. Comb. (2024) Vol. 31, Issue 1, P1.39.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials</a>.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-12,8).
%F G.f.: x*(1-x)/(1-2*x)^3. Binomial transform of squares [1, 4, 9, ...].
%F a(n) = Sum_{k=0..floor((n+4)/2)} C(n+4, 2k)*C(k, 2). - _Paul Barry_, May 15 2003
%F With two leading zeros, binomial transform of quarter-squares A002620. - _Paul Barry_, May 27 2003
%F a(n) = Sum_{k=0..n+2} C(n+2, k) * floor(k^2/4). - _Paul Barry_, May 27 2003
%F a(n) = Sum_{i=0..j} binomial(i+1, 2)*binomial(j, i). - _Jon Perry_, Feb 26 2004
%F With one leading zero, binomial transform of triangular numbers A000217. - _Philippe Deléham_, Aug 02 2005
%F 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
%F Left-shifted sequence is binomial transform of left-shifted squares (A000290). - _Franklin T. Adams-Watters_, Nov 29 2006
%F Binomial transform of a(n) = n^2 offset 1. a(3)=18. - Al Hakanson (hawkuu(AT)gmail.com), Jun 01 2009
%F a(n) = (1/n) * Sum_{k=0..n} binomial(n,k)*k^3. - _Gary Detlefs_, Nov 26 2011
%F 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
%F 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
%F E.g.f.: (1/2)*exp(2*x)*x*(2 + x). - _Stefano Spezia_, Aug 17 2019
%F From _Amiram Eldar_, Jan 05 2022: (Start)
%F Sum_{n>=1} 1/a(n) = 128/9 - 56*log(2)/3.
%F Sum_{n>=1} (-1)^(n+1)/a(n) = 24*log(3/2) - 80/9. (End)
%e 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.
%e 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
%e 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
%p A001793 := n*(n+3)*2^(n-3); seq(A001793(n), n=1..40);
%p A001793:=(-1+z)/(2*z-1)**3; # _Simon Plouffe_ in his 1992 dissertation.
%t 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 *)
%o (PARI) a(n)=n*(n+3)<<(n-3) \\ _Charles R Greathouse IV_, Sep 24 2015
%o (Magma) [2^(n-3)*n*(n+3): n in [1..30]]; // _G. C. Greubel_, Nov 06 2019
%o (Sage) [2^(n-3)*n*(n+3) for n in (1..30)] # _G. C. Greubel_, Nov 06 2019
%o (GAP) List([1..30], n-> 2^(n-3)*n*(n+3) ); # _G. C. Greubel_, Nov 06 2019
%Y a(n) = A039991(n+3, 4) = A055252(n, 1).
%Y Cf. A058396, A058645.
%Y Cf. A053120.
%K easy,nonn
%O 1,2
%A _N. J. A. Sloane_ and _Simon Plouffe_
|
