Displaying 1-10 of 20 results found.
Eigenvector of triangle A055151 of Motzkin polynomial coefficients, where A055151(n,k) = n!/((n-2k)!*k!*(k+1)!) for 0<=k<=[n/2], n>=0.
+20
3
1, 1, 2, 4, 11, 31, 96, 302, 1023, 3607, 13318, 50348, 195361, 772565, 3112630, 12715692, 52648847, 220705119, 937145214, 4028239116, 17522172021, 77071709841, 342583183572, 1537550150766, 6961838925069, 31774593686661
FORMULA
Eigenvector: a(n) = Sum_{k=0..[n/2]} n!/((n-2k)!*k!*(k+1)!)*a(k), for n>=0, with a(0)=1. G.f. satisfies: A(x) = A(-x/(1-2*x))/(1-2*x)); i.e., 2nd inverse binomial transform equals A(-x). G.f. satisfies: A(x/(1-x))/(1-x)) = A(-x/(1-3*x))/(1-3*x). G.f. of inverse binomial transform: A(x/(1+x))/(1+x)) = B(x^2) where [x^n] B(x) = a(n)*C(2*n,n)/(n+1) = a(n)* A000108(n) and A000108=Catalan.
EXAMPLE
A(x) = 1 + x + 2*x^2 + 4*x^3 + 11*x^4 + 31*x^5 + 96*x^6 +...
A(x/(1+x))/(1+x) = 1 + x^2 + 2*2*x^4 + 4*5*x^6 + 11*14*x^8 +...
PROG
(PARI) {a(n)=if(n==0, 1, sum(k=0, n\2, n!/((n-2*k)!*k!*(k+1)!)*a(k)))}
Irregular triangle of numbers read by rows: {binomial(n-k, k), n >= 0, 0 <= k <= floor(n/2)}; or, triangle of coefficients of (one version of) Fibonacci polynomials.
+10
89
1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 4, 3, 1, 5, 6, 1, 1, 6, 10, 4, 1, 7, 15, 10, 1, 1, 8, 21, 20, 5, 1, 9, 28, 35, 15, 1, 1, 10, 36, 56, 35, 6, 1, 11, 45, 84, 70, 21, 1, 1, 12, 55, 120, 126, 56, 7, 1, 13, 66, 165, 210, 126, 28, 1, 1, 14, 78, 220, 330, 252, 84, 8, 1, 15, 91, 286, 495, 462
COMMENTS
T(n,k) is the number of subsets of {1,2,...,n-1} of size k and containing no consecutive integers. Example: T(6,2)=6 because the subsets of size 2 of {1,2,3,4,5} with no consecutive integers are {1,3},{1,4},{1,5},{2,4},{2,5} and {3,5}. Equivalently, T(n,k) is the number of k-matchings of the path graph P_n. - Emeric Deutsch, Dec 10 2003 T(n,k) = number of compositions of n+2 into k+1 parts, all >= 2. Example: T(6,2)=6 because we have (2,2,4),(2,4,2),(4,2,2),(2,3,3),(3,2,3) and (3,3,2). - Emeric Deutsch, Apr 09 2005 Given any recurrence sequence S(k) = x*a(k-1) + a(k-2), starting (1, x, x^2+1, ...); the (k+1)-th term of the series = f(x) in the k-th degree polynomial: (1, (x), (x^2 + 1), (x^3 + 2x), (x^4 + 3x^2 + 1), (x^5 + 4x^3 + 3x), (x^6 + 5x^4 + 6x^2 + 1), ...). Example: let x = 2, then S(k) = 1, 2, 5, 12, 29, 70, 169, ... such that A000129(7) = 169 = f(x), x^6 + 5x^4 + 6x^2 + 1 = (64 + 80 + 24 + 1). - Gary W. Adamson, Apr 16 2008 Row k gives the nonzero coefficients of U(k,x/2) where U is the Chebyshev polynomial of the second kind. For example, row 6 is 1,5,6,1 and U(6,x/2) = x^6 - 5x^4 + 6x^2 - 1. - David Callan, Jul 22 2008 T(n,k) is the number of nodes at level k in the Fibonacci tree f(k-1). The Fibonacci trees f(k) of order k are defined as follows: 1. f(-1) and f(0) each consist of a single node. 2. For k >= 1, to the root of f(k-1), taken as the root of f(k), we attach with a rightmost edge the tree f(k-2). See the Iyer and Reddy references. These trees are not the same as the Fibonacci trees in A180566. Example: T(3,0)=1 and T(3,1)=2 because in f(2) = /\ we have 1 node at level 0 and 2 nodes at level 1. - Emeric Deutsch, Jun 21 2011 Triangle, with zeros omitted, given by (1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2011 This sequence is the elements on the rising diagonals of the Pascal triangle, where the sum of the elements in each rising diagonal represents a Fibonacci number. - Mohammad K. Azarian, Mar 08 2012 If we set F(0;x) = 0, F(1;x) = 1, F(n+1;x) = x*F(n;x) + F(n-1;x), then we obtain the sequence of Vieta-Fibonacci polynomials discussed by Gary W. Adamson above. We note that F(n;x) = (-i)^n * U(n;i*x/2), where U denotes the respective Chebyshev polynomial of the second kind (see David Callan's remark above). Let us fix a,b,f(0),f(1) in C, b is not the zero, and set f(n) = a*f(n-1) + b*f(n-2). Then we deduce the relation: f(n) = b^((n-1)/2) * F(n;a/sqrt(b))*f(1) + b^(n/2) * F(n-1;a/sqrt(b))*f(0), where for a given value of the complex root sqrt(b) we set b^(n/2) = (sqrt(b))^n. Moreover, if b=1 then we get f(n+k) + (-1)^k * f(n-k) = L(k;a)*f(n), for every k=0,1,...,n, and where L(0;a)=2, L(1;a)=a, L(n+1;a)=a*L(n;a) + L(n-1;a) are the Vieta-Lucas polynomials. Let us observe that L(n+2;a) = F(n+2;a) + F(n;a), L(m+n;a) = L(m;a)*F(n;a) + L(m-1;a)*F(n-1;a), which implies also L(n+1;a) = a*F(n;a) + 2*F(n-1;a). Further we have L(n;a) = 2*(-i)^n * T(n;i*x/2), where T(n;x) denotes the n-th Chebyshev polynomial of the first kind. For the proofs, other relations and facts - see Witula-Slota's papers. - Roman Witula, Oct 12 2012 Aside from signs and index shift, the coefficients of the characteristic polynomial of the Coxeter adjacency matrix for the Coxeter group A_n related to the Chebyshev polynomial of the second kind (cf. Damianou link p. 19). - Tom Copeland, Oct 11 2014 For a mirrored, shifted version showing the relation of these coefficients to the Pascal triangle, Fibonacci, and other number triangles, see A030528. See also A053122 for a relation to Cartan matrices. - Tom Copeland, Nov 04 2014 For a relation to a formulation for a universal Lie Weyl algebra for su(1,1), see page 16 of Durov et al. - Tom Copeland, Nov 29 2014 A reversed, signed and aerated version is given by A049310, related to Chebyshev polynomials. - Tom Copeland, Dec 06 2015 For n >= 3, the n-th row gives the coefficients of the independence polynomial of the (n-2)-path graph P_{n-2}. - Eric W. Weisstein, Apr 07 2017 For n >= 2, the n-th row gives the coefficients of the matching-generating polynomial of the (n-1)-path graph P_{n-1}. - Eric W. Weisstein, Apr 10 2017 Antidiagonals of the Pascal matrix A007318 read bottom to top. These are also the antidiagonals read from top to bottom of the numerical coefficients of the Maurer-Cartan form matrix of the Leibniz group L^(n)(1,1) presented on p. 9 of the Olver paper), which is generated as exp[c. * M] with (c.)^n = c_n and M the Lie infinitesimal generator A218272. Reverse is A102426. - Tom Copeland, Jul 02 2018 T(n,k) is the number of Markov equivalence classes with skeleton the path on n+1 nodes having exactly k immoralities. See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - Liam Solus, Aug 23 2018 T(n, k) = number of compositions of n+1 into n+1-2*k odd parts. For example, T(6,2) = 6 because 7 = 5+1+1 = 3+3+1 = 3+1+3 = 1+1+5 = 1+3+3 = 1+1+5. - Michael Somos, Sep 19 2019 Alternate rows can be parsed into those with odd integer coefficients to the right of the leftmost 1, and those with even integer coefficients to the right of the leftmost 1. The first set is shown in A054142 and are characteristic polynomials of submatrices of an infinite tridiagonal matrix ( A332602) with all -1's in the super and subdiagonals and (1,2,2,2,...) as the main diagonal. For example, the characteristic equation of the 3 X 3 submatrix (1,-1,0; -1,2,-1; 0,-1,2) is x^3 - 5x^2 + 6x - 1. The roots are the Beraha constants B(7,1) = 3.24697...; B(7,2) = 1.55495...; and B(7,3) = 0.198062.... For n X n matrices of this form, the largest eigenvalue is B(2n+1, 1). The 3 X 3 matrix has an eigenvalue of 3.24697... = B(7,1). Polynomials with even integer coefficients to the right of the leftmost 1 are in A053123 with roots being the even-indexed Beraha constants. The generating Cartan matrices are those with (2,2,2,...) as the main diagonal and -1's as the sub- and superdiagonals. The largest eigenvalue of n X n matrices of this form are B(2n+2,1). For example, the largest eigenvalue of (2,-1,0; -1,2,-1; 0,-1,2) is 3.414... = B(8,1) = a root to x^3 - 6x^2 + 10x - 4. (End) T(n,k) is the number of edge covers of P_(n+2) with (n-k) edges. For example, T(6,2)=6 because among edges 1, 2, ..., 7 of P_8, we can eliminate any two non-consecutive edges among 2-6. These numbers can be found using the recurrence relation for the edge cover polynomial of P_n, which is E(P_n,x) = xE(P_(n-1),x)+xE(P_(n-2),x) and E(P_1,x)=0, E(P_2,x)=x (ref. Akbari and Oboudi). - Feryal Alayont, Jun 03 2022 T(n,k) is the number of ways to tile an n-board (an n X 1 array of 1 X 1 cells) using k dominoes and n-2*k squares. - Michael A. Allen, Dec 28 2022 T(n,k) is the number of positive integer sequences (s(1),s(2),...,s(n-2k)) such that s(i) < s(i+1), s(1) is odd, s(n-2k) <= n, and s(i) and s(i+1) have opposite parity (ref. Donnelly, Dunkum, and McCoy). Example: T(6,0)=1 corresponds to 123456; T(6,1)=5 corresponds to 1234, 1236, 1256, 1456, 3456; T(6,2)=6 corresponds to 12, 14, 16, 34, 36; and T(6,3)=1 corresponds to the empty sequence () with length 0. - Molly W. Dunkum, Jun 27 2023
REFERENCES
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 141ff.
C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. See p. 117.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 182-183.
LINKS
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Table 3).
FORMULA
Let F(n, x) be the n-th Fibonacci polynomial in x; the g.f. for F(n, x) is Sum_{n>=0} F(n, x)*y^n = (1 + x*y)/(1 - y - x*y^2). - Paul D. HannaT(m, n) = 0 for n != 0 and m <= 1 T(0, 0) = T(1, 0) = 1 T(m, n) = T(m - 1, n) + T(m-2, n-1) for m >= 2 (i.e., like the recurrence for Pascal's triangle A007318, but going up one row as well as left one column for the second summand). E.g., T(7, 2) = 10 = T(6, 2) + T(5, 1) = 6 + 4. - Rob Arthan, Sep 22 2003 G.f. for k-th column: x^(2*k-1)/(1-x)^(k+1).
Identities for the Fibonacci polynomials F(n, x):
F(m+n+1, x) = F(m+1, x)*F(n+1, x) + x*F(m, x)F(n, x).
F(n, x)^2-F(n-1, x)*F(n+1, x) = (-x)^(n-1).
The degree of F(n, x) is floor((n-1)/2) and F(2p, x) = F(p, x) times a polynomial of equal degree which is 1 mod p.
p(x,n) = Sum_{m=0..floor((n+1)/2)} binomial(n-m+1, m)*x^m;
p(x,n) = p(x, n - 1) + x*p(x, n - 2). (End)
G.f.: 1/(1-x-y*x^2) = R(0)/2, where R(k) = 1 + 1/(1 - (2*k+1+ x*y)*x/((2*k+2+ x*y)*x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013 O.g.f. G(x,t) = x/(1-x-tx^2) = x + x^2 + (1+t) x^3 + (1+2t) x^4 + ... has the inverse Ginv(x,t) = -[1+x-sqrt[(1+x)^2 + 4tx^2]]/(2tx) = x - x^2 + (1-t) x^3 + (-1+3t) x^4 + ..., an o.g.f. for the signed Motzkin polynomials of A055151, consistent with A134264 with h_0 = 1, h_1 = -1, h_2 = -t, and h_n = 0 otherwise. - Tom Copeland, Jan 21 2016 O.g.f. H(x,t) = x (1+tx)/ [1-x(1+tx)] = x + (1+t) x^2 + (1+2t) x^3 + ... = -L[Cinv(-tx)/t], where L(x) = x/(1+x) with inverse Linv(x) = x/(1-x) and Cinv(x) = x (1-x) is the inverse of C(x) = (1-sqrt(1-4x))/2, the o.g.f. of the shifted Catalan numbers A000108. Then Hinv(x,t) = -C[t Linv(-x)]/t = [-1 + sqrt(1+4tx/(1+x))]/2t = x - (1+t) x^2 + (1+2t+2t^2) x^3 - (1+3t+6t^2+5t^3) x^4 + ..., which is signed A098474, reverse of A124644. - Tom Copeland, Jan 25 2016 T(n, k) = GegenbauerC(k, (n+1)/2-k, 1). - Peter Luschny, May 10 2016
EXAMPLE
The first few Fibonacci polynomials (defined here by F(0,x) = 0, F(1,x) = 1; F(n+1, x) = F(n, x) + x*F(n-1, x)) are:
0: 0
1: 1
2: 1
3: 1 + x
4: 1 + 2*x
5: 1 + 3*x + x^2
6: (1 + x)*(1 + 3*x)
7: 1 + 5*x + 6*x^2 + x^3
8: (1 + 2*x)*(1 + 4*x + 2*x^2)
9: (1 + x)*(1 + 6*x + 9*x^2 + x^3)
10: (1 + 3*x + x^2 )*(1 + 5*x + 5*x^2)
11: 1 + 9*x + 28*x^2 + 35*x^3 + 15*x^4 + x^5
1
1
1 1
1 2
1 3 1
1 4 3
1 5 6 1
1 6 10 4
1 7 15 10 1
1 8 21 20 5
1 9 28 35 15 1
1 10 36 56 35 6
1 11 45 84 70 21 1
1 12 55 120 126 56 7 (End)
For n=9 and k=4, T(9,4) = C(5,4) = 5 since there are exactly five size-4 subsets of {1,2,...,8} that contain no consecutive integers, namely, {1,3,5,7}, {1,3,5,8}, {1,3,6,8}, {1,4,6,8}, and {2,4,6,8}. - Dennis P. Walsh, Mar 31 2011 When the rows of the triangle are displayed as centered text, the falling diagonal sums are A005314. The first few terms are row1 = 1 = 1; row2 = 1+1 = 2; row3 = 2+1 = 3; row4 = 1+3+1 = 5; row5 = 1+3+4+1 = 9; row6 = 4+6+5+1 = 16; row7 = 1+10+10+6+1 = 28; row8 = 1+5+20+15+7+1 = 49; row9 = 6+15+35+21+8+1 = 86; row10 = 1+21+35+56+28+9+1 = 151. - John Molokach, Jul 08 2013 In the example, you can see that the n-th row of Pascal's triangle is given by T(n, 0), T(n+1, 1), ..., T(2n-1, n-1), T(2n, n). - Daniel Forgues, Jul 07 2018
MAPLE
a := proc(n) local k; [ seq(binomial(n-k, k), k=0..floor(n/2)) ]; end;
T := proc(n, k): if k<0 or k>floor(n/2) then return(0) fi: binomial(n-k, k) end: seq(seq(T(n, k), k=0..floor(n/2)), n=0..15); # Johannes W. Meijer, Aug 26 2013
MATHEMATICA
(* first: sum method *) Table[CoefficientList[Sum[Binomial[n - m + 1, m]*x^m, {m, 0, Floor[(n + 1)/2]}], x], {n, 0, 12}] (* Roger L. Bagula, Feb 20 2009 *) (* second: polynomial recursion method *) Clear[L, p, x, n, m]; L[x, 0] = 1; L[x, 1] = 1 + x; L[x_, n_] := L[x, n - 1] + x*L[x, n - 2]; Table[ExpandAll[L[x, n]], {n, 0, 10}]; Table[CoefficientList[ExpandAll[L[x, n]], x], {n, 0, 12}]; Flatten[%] (* Roger L. Bagula, Feb 20 2009 *) (* Center option shows falling diagonals are A224838 *) Column[Table[Binomial[n - m, m], {n, 0, 25}, {m, 0, Floor[n/2]}], Center] (* John Molokach, Jul 26 2013 *) Table[ Select[ CoefficientList[ Fibonacci[n, x], x], Positive] // Reverse, {n, 1, 18} ] // Flatten (* Jean-François Alcover, Oct 21 2013 *) CoefficientList[LinearRecurrence[{1, x}, {1 + x, 1 + 2 x}, {-1, 10}], x] // Flatten (* Eric W. Weisstein, Apr 07 2017 *) CoefficientList[Table[x^((n - 1)/2) Fibonacci[n, 1/Sqrt[x]], {n, 15}], x] // Flatten (* Eric W. Weisstein, Apr 07 2017 *)
PROG
(PARI) {T(n, k) = if( k<0 || 2*k>n, 0, binomial(n-k, k))};
(Sage) # Prints the table; cf. A145574. for n in (2..20): [Compositions(n, length=m, min_part=2).cardinality() for m in (1..n//2)] # Peter Luschny, Oct 18 2012 (Haskell)
a011973 n k = a011973_tabf !! n !! k
a011973_row n = a011973_tabf !! n
a011973_tabf = zipWith (zipWith a007318) a025581_tabl a055087_tabf
Triangle read by rows: T(n,k) = C(n+k,n)*C(n,k)/(k+1), for n >= 0, k = 0..n.
+10
38
1, 1, 1, 1, 3, 2, 1, 6, 10, 5, 1, 10, 30, 35, 14, 1, 15, 70, 140, 126, 42, 1, 21, 140, 420, 630, 462, 132, 1, 28, 252, 1050, 2310, 2772, 1716, 429, 1, 36, 420, 2310, 6930, 12012, 12012, 6435, 1430, 1, 45, 660, 4620, 18018, 42042, 60060, 51480, 24310, 4862
COMMENTS
Row sums: A006318 (Schroeder numbers). Essentially same as triangle A060693 transposed. T(n,k) is number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0), having k U's. E.g., T(2,1)=3 because we have UHD, UDH and HUD. - Emeric Deutsch, Dec 06 2003 Conjecture: The expected number of U's in a Schroeder n-path is asymptotically Sqrt[1/2]*n for large n. - David Callan, Jul 25 2008 T(n, k) is also the number of order-preserving and order-decreasing partial transformations (of an n-chain) of width k (width(alpha) = |Dom(alpha)|). - Abdullahi Umar, Oct 02 2008 The antidiagonals of this lower triangular matrix are the rows of A055151. - Tom Copeland, Jun 17 2015
REFERENCES
Charles Jordan, Calculus of Finite Differences, Chelsea 1965, p. 449.
FORMULA
Triangle T(n, k) read by rows; given by [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...] DELTA [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...] where DELTA is Deléham's operator defined in A084938. Sum_{k=0..n} T(n, k)*x^k*(1-x)^(n-k) = A000108(n), A001003(n), A007564(n), A059231(n), A078009(n), A078018(n), A081178(n), A082147(n), A082181(n), A082148(n), A082173(n) for x = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. - Philippe Deléham, Aug 18 2005 Sum_{k=0..n} T(n,k)*x^k = (-1)^n* A107841(n), A080243(n), A000007(n), A000012(n), A006318(n), A103210(n), A103211(n), A133305(n), A133306(n), A133307(n), A133308(n), A133309(n) for x = -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8 respectively. - Philippe Deléham, Oct 18 2007 O.g.f. (with initial 1 excluded) is the series reversion with respect to x of (1-t*x)*x/(1+x). Cf. A062991 and A089434. - Peter Bala, Jul 31 2012 G.f.: 1 + (1 - x - T(0))/y, where T(k) = 1 - x*(1+y)/( 1 - x*y/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 03 2013 O.g.f. A(x,t) = ( 1 - x - sqrt((1 - x)^2 - 4*x*t) )/(2*x*t) = 1 + (1 + t)*x + (1 + 3*t + 2*t^2)*x^2 + ....
1 + x*(dA(x,t)/dx)/A(x,t) = 1 + (1 + t)*x + (1 + 4*t + 3*t^2)*x^2 + ... is the o.g.f. for A123160. For n >= 1, the n-th row polynomial equals (1 + t)/(n+1)*Jacobi_P(n-1,1,1,2*t+1). Removing a factor of 1 + t from the row polynomials gives the row polynomials of A033282. (End) The o.g.f. G(x,t) = {1 - (2t+1) x - sqrt[1 - (2t+1) 2x + x^2]}/2x = (t + t^2) x + (t + 3t^2 + 2t^3) x^2 + (t + 6t^2 + 10t^3 + 5t^3) x^3 + ... generating shifted rows of this entry, excluding the first, was given in my 2008 formulas for A033282 with an o.g.f. f1(x,t) = G(x,t)/(1+t) for A033282. Simple transformations presented there of f1(x,t) are related to A060693 and A001263, the Narayana numbers. See also A086810. The inverse of G(x,t) is essentially given in A033282 by x1, the inverse of f1(x,t): Ginv(x,t) = x [1/(t+x) - 1/(1+t+x)] = [((1+t) - t) / (t(1+t))] x - [((1+t)^2 - t^2) / (t(1+t))^2] x^2 + [((1+t)^3 - t^3) / (t(1+t))^3] x^3 - ... . The coefficients in t of Ginv(xt,t) are the o.g.f.s of the diagonals of the Pascal triangle A007318 with signed rows and an extra initial column of ones. The numerators give the row o.g.f.s of signed A074909. (End)
T(n, k) = [x^k] hypergeom([-n, 1 + n], [2], -x). - Peter Luschny, Apr 26 2022
EXAMPLE
Triangle begins:
[0] 1;
[1] 1, 1;
[2] 1, 3, 2;
[3] 1, 6, 10, 5;
[4] 1, 10, 30, 35, 14;
[5] 1, 15, 70, 140, 126, 42;
[6] 1, 21, 140, 420, 630, 462, 132;
[7] 1, 28, 252, 1050, 2310, 2772, 1716, 429;
[8] 1, 36, 420, 2310, 6930, 12012, 12012, 6435, 1430;
[9] 1, 45, 660, 4620, 18018, 42042, 60060, 51480, 24310, 4862;
MAPLE
R := n -> simplify(hypergeom([-n, n + 1], [2], -x)):
Trow := n -> seq(coeff(R(n, x), x, k), k = 0..n):
MATHEMATICA
Table[Binomial[n+k, n] Binomial[n, k]/(k+1), {n, 0, 10}, {k, 0, n}]//Flatten (* Michael De Vlieger, Aug 10 2017 *)
PROG
(PARI) {T(n, k)= if(k+1, binomial(n+k, n)*binomial(n, k)/(k+1))}
(Magma) [[Binomial(n+k, n)*Binomial(n, k)/(k+1): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jun 18 2015 (SageMath) flatten([[binomial(n+k, 2*k)*catalan_number(k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 22 2022
Catalan triangle read by rows. Also triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).
+10
32
1, 1, 1, 1, 1, 2, 1, 3, 2, 1, 4, 5, 1, 5, 9, 5, 1, 6, 14, 14, 1, 7, 20, 28, 14, 1, 8, 27, 48, 42, 1, 9, 35, 75, 90, 42, 1, 10, 44, 110, 165, 132, 1, 11, 54, 154, 275, 297, 132, 1, 12, 65, 208, 429, 572, 429, 1, 13, 77, 273, 637, 1001, 1001, 429, 1, 14, 90, 350, 910, 1638, 2002, 1430, 1, 15, 104
COMMENTS
Number of standard tableaux of shape (n-k,k) (0<=k<=floor(n/2)). Example: T(4,1)=3 because in th top row we can have 124, 134, or 123 (but not 234). - Emeric Deutsch, May 23 2004 T(n,k) is the number of n-digit binary words (length n sequences on {0,1}) containing k 1's such that no initial segment of the sequence has more 1's than 0's. - Geoffrey Critzer, Jul 31 2009 T(n,k) is the number of dispersed Dyck paths (i.e. Motzkin paths with no (1,0) steps at positive heights) of length n and having k (1,1)-steps. Example: T(5,1)=4 because, denoting U=(1,1), D=(1,-1), H=(1,0), we have HHHUD, HHUDH, HUDHH, and UDHHH. - Emeric Deutsch, May 30 2011 T(n,k) is the number of length n left factors of Dyck paths having k (1,-1)-steps. Example: T(5,1)=4 because, denoting U=(1,1), D=(1,-1), we have UUUUD, UUUDU, UUDUU, and UDUUU. There is a simple bijection between length n left factors of Dyck paths and dispersed Dyck paths of length n, that takes D steps into D steps. - Emeric Deutsch, Jun 19 2011 Triangle, with zeros omitted, given by (1, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -1, 1, ...) DELTA (0, 1, -1, 0, 0, 1, -1, 0, 0, 1, -1, 0, 0, 1, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2011
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. 796.
P. J. Larcombe, A question of proof..., Bull. Inst. Math. Applic. (IMA), 30, Nos. 3/4, 1994, 52-54.
LINKS
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]. Chassidy Bozeman, Christine Cheng, Pamela E. Harris, Stephen Lasinis, and Shanise Walker, The Pinnacle Sets of a Graph, arXiv:2406.19562 [math.CO], 2024. See pp. 9-10. L. W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976), no. 1, 83-90. [Annotated scanned copy]
FORMULA
T(n, 0) = 1 if n >= 0; T(2*k, k) = T(2*k-1, k-1) if k>0; T(n, k) = T(n-1, k-1) + T(n-1, k) if k=1, 2, ..., floor(n/2). - Michael Somos, Aug 17 1999 T(n, k) = binomial(n, k) - binomial(n, k-1). - Michael Somos, Aug 17 1999 Sum_{k=0..n} T(n,k)*x^k = A000012(n), A001405(n), A126087(n), A128386(n), A121724(n), A128387(n), A132373(n), A132374(n), A132375(n), A121725(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - Philippe Deléham, Dec 12 2011
EXAMPLE
Triangle begins:
1;
1;
1, 1;
1, 2;
1, 3, 2;
1, 4, 5;
1, 5, 9, 5;
1, 6, 14, 14;
1, 7, 20, 28, 14;
...
T(5,2) = 5 because there are 5 such sequences: {0, 0, 0, 1, 1}, {0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 1, 0}. - Geoffrey Critzer, Jul 31 2009
MAPLE
b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
`if`(x=0, 1, add(b(x-1, y+j), j=[-1, 1])))
end:
T:= (n, k)-> b(n, n-2*k):
MATHEMATICA
Table[Binomial[k, i]*(k - 2 i + 1)/(k - i + 1), {k, 0, 20}, {i, 0, Floor[k/2]}] // Grid (* Geoffrey Critzer, Jul 31 2009 *)
PROG
(PARI) {T(n, k) = if( k<0 || k>n\2, 0, if( n==0, 1, T(n-1, k-1) + T(n-1, k)))}; /* Michael Somos, Aug 17 1999 */ (Haskell)
a008315 n k = a008315_tabf !! n !! k
a008315_row n = a008315_tabf !! n
a008315_tabf = map reverse a008313_tabf
CROSSREFS
T(2n, n) = A000108 (Catalan numbers), row sums = A001405 (central binomial coefficients).
Triangle read by rows: T(n,k) is number of Motzkin paths of length n and having k horizontal steps.
+10
22
1, 0, 1, 1, 0, 1, 0, 3, 0, 1, 2, 0, 6, 0, 1, 0, 10, 0, 10, 0, 1, 5, 0, 30, 0, 15, 0, 1, 0, 35, 0, 70, 0, 21, 0, 1, 14, 0, 140, 0, 140, 0, 28, 0, 1, 0, 126, 0, 420, 0, 252, 0, 36, 0, 1, 42, 0, 630, 0, 1050, 0, 420, 0, 45, 0, 1, 0, 462, 0, 2310, 0, 2310, 0, 660, 0, 55, 0, 1, 132, 0, 2772, 0
COMMENTS
Row sums are the Motzkin numbers ( A001006). Column 0 gives the aerated Catalan numbers ( A000108). Let P_n(x) = Sum_{k=0..n} T(n,k)*x^k. P_0(x) = 1, P_1(x) = x, P_n(x) = x*P_(n-1)(x) + Sum_{j=0..n-2} P_j(x)*P_(n-2-j)(x); essentially the same as A124027. - Philippe Deléham, Oct 03 2007 G. J. Chaitin's numbers of s-expressions of size n are given by the coefficients of polynomials p(k, x) satisfying: p(k, x) = Sum_{j=2..k-1} p(j, x)*p(k-j, x). The coefficients of these polynomials also give (essentially) the triangle shown here. - Roger L. Bagula, Oct 31 2006 Exponential Riordan array [Bessel_I(1,2x)/x,x]. - Paul Barry, Mar 24 2010 Diagonal sums are the aerated large Schroeder numbers. - Paul Barry, Apr 21 2010 These polynomials are related to the Gegenbauer polynomials which in turn are specializations of the Jacobi polynomials. The o.g.f. of the Gegenbauer polynomials is 1 / [1-2tx+x^2]^a. For the generating function Gb(x,h1,h2,a) = [x / (1 + h1 x + h2 x^2)]^a, the compositional inverse in x is Gbinv(x,h1,h2,a) = [(1-h1*y) - sqrt[(1-h1*y)^2-4h2*y^2]]/(2*h2*y) with y = x^(1/a). The polynomials of this entry are generated by Gbinv(x,t,1,1). The Legendre polynomials are related to the o.g.f. Gb(x,-2t,1,1/2). Cf. A121448. - Tom Copeland, Feb 07 2016 The bivariate o.g.f. in Copeland's Jan 29 2016 formulas can be related to conformal mappings of the complex plane and a solution of the dKP hierarchy. Cf. p. 24 of the Takebe et al. paper. - Tom Copeland, May 30 2018
REFERENCES
G. J. Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987, page 169.
FORMULA
G.f.: [1-tz-sqrt(1-2tz+t^2*z^2-4z^2)]/(2z^2).
T(n, k) = n!/[k!((n-k)/2)!((n-k)/2-1)! ] = A055151(n, (n-k)/2) if n-k is a nonnegative even number; otherwise T(n, k) = 0. T(n, k) = C(n, k)*C((n-k)/2)*(1+(-1)^(n-k))/2 if k <= n, 0 otherwise. - Paul Barry, May 18 2005 G.f.: 1/(1-x*y-x^2/(1-x*y-x^2/(1-x*y-x^2/.... (continued fraction). - Paul Barry, Dec 15 2008 E.g.f.: M(x,t) = e^(xt) AC(t) = e^(xt) I_1(2t)/t = e(xt) * e.g.f.( A126120(t)) = e^(xt) Sum_{n>=0} t^(2n)/(n!(n+1)!) = exp[t P(.,x)]. The e.g.f. of this Appell sequence of polynomials P(n,x) is e^(xt) times the e.g.f. AC(t) of the aerated Catalan numbers A126120. AC(t) = I_1(2t)/t, where I_n(x) = T_n(d/dx) I_0(x) are the modified Bessel functions of the first kind and T_n, the Chebyshev polynomials of the first kind. P(n,x) has the lowering and raising operators L = d/dx = D and R = d/dD log{M(x,D)} = x + d/dD log{AC(D)} = x + Sum_{n>=0} c(n) D^(2n+1)/(2n+1)! with c(n) = (-1)^n A180874(n+1), i.e., L P(n,x) = n P(n-1,x) and R P(n,x) = P(n+1,x). (P(.,x) + y)^n = P(n,x+y) = Sum_{k=0..n} binomial(n,k) P(k,x) y^(n-k) = (b.+x+y)^n, where (b.)^k = b_k = A126120(k). Exp(b.D) e^(xt) = exp[(x+b.)t] = exp[P(.,x)t] = e^(b.t) e^(xt) = e^(xt) AC(t).
See p. 12 of the Alexeev et al. link and A055151 for a refinement. Shifted o.g.f: G(x,t) = [1-tx-sqrt[(1-tx)^2-4x^2]] / 2x = x + t x^2 + (1+t) x^3 + ... has the compositional inverse Ginv(x,t) = x / [1 + tx + x^2] = x - t x^2 +(-1+t^2) x^3 + (2t-t^3) x^4 + (1-3t^2+t^4) x^5 + ..., a shifted o.g.f. for the signed Chebyshev polynomials of the second kind of A049310 (cf. also the Fibonacci polynomials of A011973). Then the inversion formula of A134264, involving non-crossing partitions and free probability with their multitude of interpretations (cf. A125181 also), can be used with h_0 = 1, h_1 = t, and h_2 = 1 to interpret the coefficients of the Motzkin polynomials combinatorially. (End)
Provides coefficients of the inverse of f(x) = x / [1 + h1 x + h2 x^2], a bivariate generating function of A049310 (mod signs). finv(x) = [(1-h1*x) - sqrt[(1-h1*x)^2-4h2*x^2]]/(2*h2*x) = x + h1 x^2 + (h2 + h1^2) x^3 + (3 h1 h2 + h1^3) x^4 + ... is a bivariate o.g.f. for this entry.
The infinitesimal generator for finv(x) is g(x) d/dx with g(x) = 1 /[df(x)/dx] = x^2 / [(f(x))^2 (1 - h2 x^2)] = (1 + h1 x + h2 x^2)^2 / (1 - h2 x^2) so that [g(x)d/dx]^n/n! x evaluated at x = 0 gives the row polynomials FI(n,h1,h2) of the compositional inverse of f(x), i.e., exp[x g(u)d/du] u |_(u=0) = finv(x) = 1 / [1 -x FI(.,h1,h2)]. Cf. A145271. E.g., FI(0,h1,h2) = 0
FI(1,h1,h2) = 1
FI(2,h1,h2) = 1 h1
FI(3,h1,h2) = 1 h2 + 1 h1^2
FI(4,h1,h2) = 3 h2 h1 + 1 h1^3
FI(5,h1,h2) = 2 h2^2 + 6 h2 h1^2 + 1 h1^4
FI(6,h1,h2) = 10 h2^2 h1 + 10 h2 h1^3 + 1 h1^5.
And with D = d/dh1, FI(n+1, h1,h2) = MT(n,h1,h2) = (b.y + h1)^n = Sum_{k=0..n} binomial(n,k) b(k) y^k h1^(n-k) = exp[(b.y D] (h1)^n = AC(y D) (h1)^n, where b(k) = A126120(k), y = sqrt(h2), and AC(t) is defined in my Jan 23 formulas above. Equivalently, AC(y D) e^(x h1) = exp[x MT(.,h1,h2)]. The MT polynomials comprise an Appell sequence in h1 with e.g.f. e^(h1*x) AC(xy) = exp[x MT(.,h1,h2)] with lowering operator L = d/dh1 = D, i.e., L MT(n,h1,h2) = dMT(n,h1,h2)/dh1 = n MT(n-1,h1,h2) and raising operator R = h1 + dlog{AC(y L)}/dL = h1 + Sum_{n>=0} c(n) h2^(n+1) D^(2n+1)/(2n+1)! = h1 + h2 d/dh1 - h2^2 (d/dh1)^3/3! + 5 h2^3 (d/dh1)^5/5! - ... with c(n) = (-1)^n A180874(n+1) (consistent with the raising operator in the Jan 23 formulas). The compositional inverse finv(x) is also obtained from the non-crossing partitions of A134264 (or A125181) with h_0 = 1, h_1 = h1, h_2 = h2, and h_n = 0 for all other n. See A238390 for the umbral compositional inverse in h1 of MT(n,h1,h2) and inverse matrix. (End)
z1(x,h1,h2) = finv(x), the bivariate o.g.f. above for this entry, is the zero that vanishes for x=0 for the quadratic polynomial Q(z;z1(x,h1,h2),z2(x,h1,h2)) = (z-z1)(z-z2) = z^2 - (z1+z2) z + (z1*z2) = z^2 - e1 z + e2 = z^2 - [(1-h1*x)/(h2*x)] z + 1/h2, where e1 and e2 are the elementary symmetric polynomials for two indeterminates.
The other zero is given by z2(x,h1,h2) = (1 - h1*x)/(h2*x) - z1(x,h1,h2) = [1 - h1*x + sqrt[(1-h1*x)^2 - 4 h2*x^2]] / (2h2*x).
The two are the nontrivial zeros of the elliptic curve in Legendre normal form y^2 = z (z-z1)(z-z2), (see Landweber et al., p. 14, Ellingsrud, and A121448), and the zeros for the Riccati equation z' = (z - z1)(z - z2), associated to soliton solutions of the KdV equation (see Copeland link). (End)
Comparing the shifted o.g.f. S(x) = x / (1 - h_1 x + h_2 x^2) for the bivariate Chebyshev polynomials S_n(h_1,h_2) of A049310 with the shifted o.g.f. H(x) = x / ((1 - a x)(1 - b x)) for the complete homogeneous symmetric polynomials H_n(a,b) = (a^(n+1)-b^(n+1)) / (a - b) shows that S_n(h_1,h_2) = H_n(a,b) for h_1 = a + b and h_2 = ab and, conversely, a = (h_1 + sqrt(h_1^2 - 4 h_2)) / 2 and b = (h_1 - sqrt(h_1^2 - 4 h_2)) / 2. The compositional inverse about the origin of S(x) gives a bivariate o.g.f. for signed Motzkin polynomials M_n(h_1,h_2) of this entry, and that of H(x) gives one for signed Narayana polynomials N_n(a,b) of A001263, thereby relating the bivariate Motzkin and Narayana polynomials by the indeterminate transformations. E.g., M_2(h_1,h_2) = h_2 + h_1^2 = ab + (a + b)^2 = a^2 + 3 ab + b^2 = N_2(a,b). - Tom Copeland, Jan 27 2024
EXAMPLE
Triangle begins:
1;
0, 1;
1, 0, 1;
0, 3, 0, 1;
2, 0, 6, 0, 1;
0, 10, 0, 10, 0, 1;
5, 0, 30, 0, 15, 0, 1;
Row n has n+1 terms.
T(4,2)=6 because we have HHUD, HUDH, UDHH, HUHD, UHDH, UHHD, where U=(1,1), D=(1,-1) and H=(1,0).
MAPLE
G:=(1-t*z-sqrt(1-2*t*z+t^2*z^2-4*z^2))/2/z^2:
Gser:=simplify(series(G, z=0, 16)): P[0]:=1:
for n from 1 to 13 do P[n]:=sort(coeff(Gser, z^n)) od:
seq(seq(coeff(t*P[n], t^k), k=1..n+1), n=0..13);
# Maple program for the triangular array:
T:=proc(n, k) if n-k mod 2 = 0 and k<=n then n!/k!/((n-k)/2)!/((n-k)/2+1)! else 0 fi end: TT:=(n, k)->T(n-1, k-1): matrix(10, 10, TT);
MATHEMATICA
T[n_, k_]:=If[n>=k&&EvenQ[n-k], n!/(k!((n-k)/2)!((n-k)/2+1)!), 0];
T[n_, k_] := If[OddQ[n - k], 0, Binomial[n, k] CatalanNumber[(n - k)/2]]; (* Peter Luschny, Jun 06 2018 *)
CROSSREFS
Cf. A011973, A049310, A055151, A060693, A180874, A121448, A125181, A126120, A134264, A145271, A238390.
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k ddu's [here u = (1,1) and d = (1,-1)].
+10
20
1, 1, 2, 4, 1, 8, 6, 16, 24, 2, 32, 80, 20, 64, 240, 120, 5, 128, 672, 560, 70, 256, 1792, 2240, 560, 14, 512, 4608, 8064, 3360, 252, 1024, 11520, 26880, 16800, 2520, 42, 2048, 28160, 84480, 73920, 18480, 924, 4096, 67584, 253440, 295680, 110880, 11088, 132
COMMENTS
Number of Dyck paths of semilength n, having k uu's with midpoint at even height. Example: T(4,1) = 6 because we have u(uu)duddd, u(uu)udddd, udu(uu)ddd, u(uu)dddud, u(uu)ddudd and uud(uu)ddd [here u = (1,1), d = (1,-1) and the uu's with midpoint at even height are shown between parentheses]. Row sums are the Catalan numbers ( A000108). T(2n+1,n) = A000108(n) (the Catalan numbers). Sum_{k>=0} k*T(n,k) = binomial(2n-2,n-3) = A002694(n-1). Sometimes called the Touchard distribution (after Touchard's Catalan number identity). T(n,k) = number of full binary trees on 2n edges with k deep interior vertices (deep interior means you have to traverse at least 2 edges to reach a leaf) = number of binary trees on n-1 edges with k vertices having a full complement of 2 children. - David Callan, Jul 19 2004 T(n,k) = number of ordered trees on n edges with k prolific edges. A prolific edge is one whose child vertex has at least two children. For example with n=3, drawing ordered trees down from the root, /|\ has no prolific edge and the only tree with one prolific edge has the shape of an inverted Y, so T(3,1)=1.
Proof: Consider the following bijection, recorded by Emeric Deutsch, from ordered trees on n edges to Dyck n-paths. For a given ordered tree, traverse the tree in preorder (walk-around from root order). To each node of outdegree r there correspond r upsteps followed by 1 downstep; nothing corresponds to the last leaf. This bijection sends prolific edges to noninitial ascents of length >=2, that is, to DUU's. Then reverse the resulting Dyck n-path so that prolific edges correspond to DDU's. (End)
T(n,k) is the number of Łukasiewicz paths of length n having k fall steps (1,-1) that start at an even level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1) = 1 because we have U(2)(D)D, where U(2) = (1,2), D = (1,-1) and the fall steps that start at an even level are shown between parentheses. Row n contains ceiling(n/2) terms (n >= 1). - Emeric Deutsch, Jan 06 2005 Number of binary trees with n-1 edges and k+1 leaves (a binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child). - Emeric Deutsch, Jul 31 2006 Number of full binary trees with 2n edges and k+1 vertices both children of which are leaves (n >= 1; a full binary tree is a rooted tree in which each vertex has either 0 or two children). - Emeric Deutsch, Dec 26 2006 Number of ordered trees with n edges and k jumps. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007 It is remarkable that we can generate the coefficients of the right hand columns of triangle A175136 with the aid of the coefficients in the rows of the triangle given above. See A175136 for more information. - Johannes W. Meijer, May 06 2011 This array also counts 231-avoiding permutations according to the number of peaks, i.e., positions w[i-1] < w[i] > w[i+1]. For example, 123, 213, 312, and 321 have no peaks, while 132 has one peak. Note also T(n,k) = 2^(n - 1 - 2*k)* A055151(n-1,k). - Kyle Petersen, Aug 02 2013
REFERENCES
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.
FORMULA
T(n,k) = 2^(n - 2*k - 1)*binomial(n-1,2*k)*binomial(2*k,k)/(k + 1), T(0,0) = 1, for 0 <= k <= floor((n-1)/2).
G.f.: G = G(t,z) satisfies: t*z*G^2 - (1 - 2*z + 2*t*z)*G + 1 - z + t*z = 0.
With first row zero, the o.g.f. is g(x,t) = (1 - 2*x - sqrt((1 - 2*x)^2 - 4*t*x^2)) / (2*t*x) with the inverse ginv(x,t) = x / (1 + 2*x + t*x^2), an o.g.f. for shifted A207538 and A133156 mod signs, so A134264 and A125181 can be used to interpret the polynomials of this entry. Cf. A097610. - Tom Copeland, Feb 08 2016 If we delete the first 1 from the data these are the coefficients of the polynomials p(n) = 2^n*hypergeom([(1 - n)/2, - n/2], [2], x). - Peter Luschny, Jan 23 2018
EXAMPLE
T(4,1) = 6 because we have uduu(ddu)d, uu(ddu)dud, uuu(ddu)dd, uu(ddu)udd, uudu(ddu)d and uuud(ddu)d [here u = (1,1), d = (1,-1) and the ddu's are shown between parentheses].
Triangle begins:
1;
1;
2;
4, 1;
8, 6;
16, 24, 2;
32, 80, 20;
64, 240, 120, 5;
128, 672, 560, 70;
256, 1792, 2240, 560, 14;
...
MAPLE
a := proc(n, k) if n=0 and k=0 then 1 elif n=0 then 0 else 2^(n-2*k-1)*binomial(n-1, 2*k)*binomial(2*k, k)/(k+1) fi end: 1, seq(seq(a(n, k), k=0..(n-1)/2), n=1..15);
MATHEMATICA
A091894[n_] := Prepend[Table[ CoefficientList[ 2^i (1 - z)^((2 i + 3)/2) Hypergeometric2F1[(i + 3)/2, (i + 4)/2, 2, z], z], {i, 0, n}], {1}] (* computes a table of the first n rows. Stumbled accidentally on it. Perhaps someone can find a relationship here? Thies Heidecke (theidecke(AT)astrophysik.uni-kiel.de), Sep 23 2008 *)
Join[{1}, Select[Flatten[Table[2^(n-2k-1) Binomial[n-1, 2k] Binomial[2k, k]/ (k+1), {n, 20}, {k, 0, n}]], #!=0&]] (* Harvey P. Dale, Mar 05 2012 *) p[n_] := 2^n Hypergeometric2F1[(1 - n)/2, -n/2, 2, x]; Flatten[Join[{{1}}, Table[CoefficientList[p[n], x], {n, 0, 12}]]] (* Peter Luschny, Jan 23 2018 *)
PROG
(PARI) {T(n, k) = if( n<1, n==0 && k==0, polcoeff( polcoeff( serreverse( x / (1 + 2*x*y + x^2) + x * O(x^n)), n), n-1 - 2*k))} /* Michael Somos, Sep 25 2006 */ (GAP) T:=Concatenation([1], Flat(List([1..13], n->List([0..Int((n-1)/2)], k->2^(n-2*k-1)*Binomial(n-1, 2*k)*Binomial(2*k, k)/(k+1))))); # Muniru A Asiru, Nov 29 2018 (Sage) [1] + [[2^(n-2*k-1)*binomial(n-1, 2*k)*binomial(2*k, k)/(k+1) for k in (0..floor((n-1)/2))] for n in (1..12)] # G. C. Greubel, Nov 30 2018
T(n,k) = binomial(n,2*k)*binomial(2*k,k) for 0 <= k <= n, triangle read by rows.
+10
17
1, 1, 0, 1, 2, 0, 1, 6, 0, 0, 1, 12, 6, 0, 0, 1, 20, 30, 0, 0, 0, 1, 30, 90, 20, 0, 0, 0, 1, 42, 210, 140, 0, 0, 0, 0, 1, 56, 420, 560, 70, 0, 0, 0, 0, 1, 72, 756, 1680, 630, 0, 0, 0, 0, 0, 1, 90, 1260, 4200, 3150, 252, 0, 0, 0, 0, 0, 1, 110, 1980, 9240, 11550, 2772, 0, 0, 0, 0, 0, 0, 1, 132, 2970, 18480, 34650, 16632, 924, 0, 0, 0, 0, 0, 0, 1, 156, 4290, 34320, 90090, 72072, 12012, 0, 0, 0, 0, 0, 0, 0, 1, 182, 6006, 60060, 210210, 252252, 84084, 3432, 0, 0, 0, 0, 0, 0, 0
COMMENTS
The rows of this triangle are the gamma vectors of the n-dimensional type B associahedra (Postnikov et al., p.38 ). Cf. A055151 and A101280. - Peter Bala, Oct 28 2008 The result Sum_{k = 0..floor(n/2)} C(n,2*k)*C(2*k,k)*x^k = (sqrt(1 - 4*x))^n* P(n,1/sqrt(1 - 4*x)) expressing the row polynomials of this triangle in terms of the Legendre polynomials P(n,x) is due to Catalan. See Laden, equation 7.10, p. 56. - Peter Bala, Mar 18 2018
FORMULA
T(n,k) = n!/((n-2*k)!*k!*k!).
O.g.f.: ( 1 - x - sqrt(1 - 2*x + x^2 - 4*x^2*y))/(2*x^2*y). - Geoffrey Critzer, Feb 05 2014 R(n, x) = hypergeom([1/2 - n/2, -n/2], [1], 4*x) are the row polynomials. - Peter Luschny, Mar 18 2018 T(n,k) = Sum_{i = 0..k} (-1)^i*binomial(n, i)*binomial(n-i, k-i)^2. Cf. A063007(n,k) = Sum_{i = 0..k} binomial(n, i)^2*binomial(n-i, k-i). T(n,k) = A063007(n-k,k); that is, the diagonals of this table are the rows of A063007. (End)
EXAMPLE
Triangle begins:
1
1, 0
1, 2, 0
1, 6, 0, 0
1, 12, 6, 0, 0
1, 20, 30, 0, 0, 0
1, 30, 90, 20, 0, 0, 0
1, 42, 210, 140, 0, 0, 0, 0
1, 56, 420, 560, 70, 0, 0, 0, 0
1, 72, 756, 1680, 630, 0, 0, 0, 0, 0
1, 90, 1260, 4200, 3150, 252, 0, 0, 0, 0, 0
1, 110, 1980, 9240, 11550, 2772, 0, 0, 0, 0, 0, 0
1, 132, 2970, 18480, 34650, 16632, 924, 0, 0, 0, 0, 0, 0
Relocating the zeros to be evenly distributed and interpreting the triangle as the coefficients of polynomials
1
1
1 + 2 q^2
1 + 6 q^2
1 + 12 q^2 + 6 q^4
1 + 20 q^2 + 30 q^4
1 + 30 q^2 + 90 q^4 + 20 q^6
1 + 42 q^2 + 210 q^4 + 140 q^6
1 + 56 q^2 + 420 q^4 + 560 q^6 + 70 q^8
then the substitution q^k -> 1/(floor(k/2)+1) gives the Motzkin numbers A001006.
MAPLE
for i from 0 to 12 do seq(binomial(i, j)*binomial(i-j, j), j=0..i) od; # Zerinvary Lajos, Jun 07 2006 # Alternatively:
R := (n, x) -> simplify(hypergeom([1/2 - n/2, -n/2], [1], 4*x)):
Trow := n -> seq(coeff(R(n, x), x, j), j=0..n):
MATHEMATICA
nn=15; mxy=(1-x-(1-2x+x^2-4x^2y)^(1/2))/(2x^2 y); Map[Select[#, #>0&]&, CoefficientList[Series[1/(1-x-2y x^2mxy), {x, 0, nn}], {x, y}]]//Grid (* Geoffrey Critzer, Feb 05 2014 *)
PROG
(PARI)
T(n, k) = binomial(n, 2*k)*binomial(2*k, k);
concat(vector(15, n, vector(n, k, T(n-1, k-1)))) \\ Gheorghe Coserea, Sep 01 2018
Form array in which n-th row is obtained by expanding (1+x+x^2)^n and taking the 2nd column from the center.
+10
15
1, 3, 10, 30, 90, 266, 784, 2304, 6765, 19855, 58278, 171106, 502593, 1477035, 4343160, 12778152, 37616427, 110797569, 326527350, 962803170, 2840372304, 8383467708, 24755608584, 73133433800, 216143407675, 639062383401
COMMENTS
Number of "up" steps in all Motzkin paths of length n+1. E.g. a(2)=3 because in the four Motzkin paths of length 3, HHH, HUD, UDH and UHD, where H=(1,0), U=(1,1), D=(1,-1), we have altogether three U steps. - Emeric Deutsch, Dec 26 2003 a(n) = number of paths in the half-plane x>=0, from (0,0) to (n+1,2), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=2, we have the 3 paths: UUH, HUU, UHU. - José Luis Ramírez Ramírez, Apr 19 2015
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
FORMULA
E.g.f.: exp(x)*(2*x*BesselI(1, 2*x)+(x-2)*BesselI(2, 2*x))/x. - Vladeta Jovovic, Aug 21 2003 G.f.: [1-2z-z^2-(1-z)q]/(2z^3q), where q=sqrt(1-2z-3z^2). - Emeric Deutsch, Dec 26 2003 a(n) = Sum_{k=0..n+1} C(n+1,k)*C(n-k+1,k+2). - Paul Barry, Sep 20 2004 D-finite with recurrence (n+3)*(n-1)*a(n) -(n+1)*(2n+1)*a(n-2)-3*n*(n+1)*a(n-2)=0. - R. J. Mathar, Dec 08 2011 a(n) = n*(n+1)*hypergeom([(1-n)/2, 1-n/2], [3], 4)/2. - Peter Luschny, Nov 23 2014 a(n) = GegenbauerC(n-1, -n-1, -1/2). - Peter Luschny, May 09 2016
MAPLE
seq( add(binomial(i+1, k)*binomial(i-k+1, k+2), k=0..floor(i/2)), i=1..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
a := n -> simplify(GegenbauerC(n-1, -n-1, -1/2)):
MATHEMATICA
Table[Sum[Binomial[i + 1, k]*Binomial[i - k + 1, k + 2], {k, 0, Floor[i/2]}], {i, 30}] (* Michael De Vlieger, Apr 20 2015 *) Table[GegenbauerC[n - 1, -n - 1, -1/2], {n, 1, 50}] (* G. C. Greubel, Feb 28 2017 *)
PROG
(Sage)
a = lambda n: n*(n+1)*hypergeometric([(1-n)/2, 1-n/2], [3], 4)/2
(PARI) for(n=1, 25, print1(sum(k=0, n+1, binomial(n+1, k)*binomial(n-k+1, k+2)), ", ")) \\ G. C. Greubel, Feb 28 2017
A Motzkin related triangle.
+10
12
1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 2, 6, 1, 0, 0, 0, 10, 10, 1, 0, 0, 0, 5, 30, 15, 1, 0, 0, 0, 0, 35, 70, 21, 1, 0, 0, 0, 0, 14, 140, 140, 28, 1, 0, 0, 0, 0, 0, 126, 420, 252, 36, 1, 0, 0, 0, 0, 0, 42, 630, 1050, 420, 45, 1, 0, 0, 0, 0, 0, 0, 462, 2310, 2310, 660, 55, 1
COMMENTS
Inverse binomial transform of Narayana number triangle A001263. - Paul Barry, May 15 2005 T(n,k)=number of Motzkin paths of length n with k steps U=(1,1) or H=(1,0). Example: T(3,2)=3 because we have HUD, UDH and UHD (here D=(1,-1)). T(n,k) = number of bushes with n+1 edges and k+1 leaves (a bush is an ordered tree in which the outdegree of each nonroot node is at least two). - Emeric Deutsch, May 29 2005 Rows of A088617 are shifted columns of A107131, whose reversed rows are the Motzkin polynomials of A055151, which give the row polynomials (mod signs) of the o.g.f. that is the compositional inverse for an o.g.f. of the Fibonacci polynomials of A011973. The diagonals of A055151 give the rows of A088671, and the antidiagonals (top to bottom) of A088617 give the rows of A107131. The diagonals of A107131 give the columns of A055151. From the relation between A088617 and A107131, the o.g.f. of this entry is (1 - t*x - sqrt((1-t*x)^2 - 4*t*x^2))/(2*t*x^2). - Tom Copeland, Jan 21 2016
FORMULA
Number triangle T(n, k) = binomial(k+1, n-k+1)*binomial(n, k)/(k+1).
T(n, k) = Sum_{j=0..n} (-1)^(n-j)C(n, j)*C(j+1, k)*C(j+1, k+1)/(j+1). - Paul Barry, May 15 2005 G.f.: G = G(t, z) satisfies G = 1 + t*z*G + t*z^2*G^2. - Emeric Deutsch, May 29 2005 Coefficient array for the polynomials x^n*Hypergeometric2F1((1-n)/2, -n/2; 2; 4/x). - Paul Barry, Oct 04 2008 G.f.: 1/(1-xy(1+x)/(1-x^2*y/(1-xy(1+x)/(1-x^2y/(1-xy(1+x).... (continued fraction).
T(n,k) = C(n, 2n-2k)* A000108(n-k). (End)
EXAMPLE
Triangle begins
1;
0, 1;
0, 1, 1;
0, 0, 3, 1;
0, 0, 2, 6, 1;
0, 0, 0, 10, 10, 1;
0, 0, 0, 5, 30, 15, 1;
0, 0, 0, 0, 35, 70, 21, 1;
0, 0, 0, 0, 14, 140, 140, 28, 1;
0, 0, 0, 0, 0, 126, 420, 252, 36, 1;
MAPLE
egf := exp(t*x)*hypergeom([], [2], t*x^2);
s := n -> n!*coeff(series(egf, x, n+2), x, n);
seq(print(seq(coeff(s(n), t, j), j=0..n)), n=0..9); # Peter Luschny, Oct 29 2014
MATHEMATICA
T[n_, k_] := Binomial[k+1, n-k+1] Binomial[n, k]/(k+1);
PROG
(Magma) [Binomial(n, 2*(n-k))*Catalan(n-k): k in [0..n], n in [0..13]]; // G. C. Greubel, May 22 2022 (SageMath) flatten([[binomial(n, 2*(n-k))*catalan_number(n-k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 22 2022
Extended Motzkin numbers, Sum_{k>=0} C(n,k)C(k), C(k) the extended Catalan number A057977(k).
+10
9
1, 2, 4, 10, 25, 66, 177, 484, 1339, 3742, 10538, 29866, 85087, 243478, 699324, 2015082, 5822619, 16865718, 48958404, 142390542, 414837699, 1210439958, 3536809521, 10347314544, 30306977757, 88861597426, 260798283502, 766092871654, 2252240916665
COMMENTS
a(n) = Sum_{k=0..n} binomial(n,k)* A057977(k). For comparison: Thus one might simply say: The extended Motzkin numbers are the binomial sum of the extended Catalan numbers. Moreover: The Catalan numbers aerated with 0's at odd positions ( A126120) are the inverse binomial transform of the Motzkin numbers ( A001006). The complementary Catalan numbers ( A001700) aerated with 0's at even positions ( A138364) are the inverse binomial transform of the complementary Motzkin numbers ( A005717). The extended Catalan numbers ( A057977 = A126120 + A138364) are the inverse binomial transform of the extended Motzkin numbers ( A189912). David Scambler observed that [1, a(n-1)] for n >= 1 count the Dyck paths of semilength n which satisfy the condition "number of peaks <= number of returns + number of hills". - Peter Luschny, Oct 22 2012
FORMULA
a(n) = Sum_{k=0..n}(n!/(((n-k)!*floor(k/2)!^2)*(floor(k/2)+1)).
Recurrence: (n+2)*(n^2 + 2*n - 5)*a(n) = (2*n^3 + 7*n^2 - 14*n - 7)*a(n-1) + 3*(n-1)*(n^2 + 4*n - 2)*a(n-2). - Vaclav Kotesovec, Mar 20 2014
MAPLE
add(n!/(((n-k)!*iquo(k, 2)!^2)*(iquo(k, 2)+1)), k=0..n) end:
M := proc(n) option remember; `if`(n<2, 1, (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2)) end:
MATHEMATICA
A057977[n_] := n!/(Quotient[n, 2]!^2*(Quotient[n, 2] + 1)); a[n_] := Sum[Binomial[n, k]* A057977[k], {k, 0, n}]; Table[a[n], {n, 0, 28}] (* Jean-François Alcover, May 21 2013, after Peter Luschny *)
Table[Sum[n!/(((n-k)!*Floor[k/2]!^2)*(Floor[k/2]+1)), {k, 0, n}], {n, 0, 30}] (* G. C. Greubel, Jan 24 2017 *)
PROG
(Sage)
@CachedFunction
def M(n): return (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2) if n>1 else 1
A189912 = lambda n: n*M(n-1) + M(n)
(PARI) a(n) = sum(k=0, n, binomial(n, k)*k!/( (k\2)!^2 * (k\2+1)) );
Search completed in 0.034 seconds
|