A098474 -id:A098474 - cp's OEIS frontend

A039599 Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).

1, 1, 1, 2, 3, 1, 5, 9, 5, 1, 14, 28, 20, 7, 1, 42, 90, 75, 35, 9, 1, 132, 297, 275, 154, 54, 11, 1, 429, 1001, 1001, 637, 273, 77, 13, 1, 1430, 3432, 3640, 2548, 1260, 440, 104, 15, 1, 4862, 11934, 13260, 9996, 5508, 2244, 663, 135, 17, 1

Offset: 0

N. J. A. Sloane

T(n,k) is the number of lattice paths from (0,0) to (n,n) with steps E = (1,0) and N = (0,1) which touch but do not cross the line x - y = k and only situated above this line; example: T(3,2) = 5 because we have EENNNE, EENNEN, EENENN, ENEENN, NEEENN. - Philippe Deléham, May 23 2005
The matrix inverse of this triangle is the triangular matrix T(n,k) = (-1)^(n+k)* A085478(n,k). - Philippe Deléham, May 26 2005
Essentially the same as A050155 except with a leading diagonal A000108 (Catalan numbers) 1, 1, 2, 5, 14, 42, 132, 429, .... - Philippe Deléham, May 31 2005
Number of Grand Dyck paths of semilength n and having k downward returns to the x-axis. (A Grand Dyck path of semilength n is a path in the half-plane x>=0, starting at (0,0), ending at (2n,0) and consisting of steps u=(1,1) and d=(1,-1)). Example: T(3,2)=5 because we have u(d)uud(d),uud(d)u(d),u(d)u(d)du,u(d)duu(d) and duu(d)u(d) (the downward returns to the x-axis are shown between parentheses). - Emeric Deutsch, May 06 2006
Riordan array (c(x),x*c(x)^2) where c(x) is the g.f. of A000108; inverse array is (1/(1+x),x/(1+x)^2). - Philippe Deléham, Feb 12 2007
The triangle may also be generated from M^n*[1,0,0,0,0,0,0,0,...], where M is the infinite tridiagonal matrix with all 1's in the super and subdiagonals and [1,2,2,2,2,2,2,...] in the main diagonal. - Philippe Deléham, Feb 26 2007
Inverse binomial matrix applied to A124733. Binomial matrix applied to A089942. - Philippe Deléham, Feb 26 2007
Number of standard tableaux of shape (n+k,n-k). - Philippe Deléham, Mar 22 2007
From Philippe Deléham, Mar 30 2007: (Start)
This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=x*T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+y*T(n-1,k)+T(n-1,k+1) for k>=1. Other triangles arise by choosing different values for (x,y):
(0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970
(1,0) -> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877;
(1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598;
(2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954;
(3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791;
(4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. (End)
The table U(n,k) = Sum_{j=0..n} T(n,j)*k^j is given in A098474. - Philippe Deléham, Mar 29 2007
Sequence read mod 2 gives A127872. - Philippe Deléham, Apr 12 2007
Number of 2n step walks from (0,0) to (2n,2k) and consisting of step u=(1,1) and d=(1,-1) and the path stays in the nonnegative quadrant. Example: T(3,0)=5 because we have uuuddd, uududd, ududud, uduudd, uuddud; T(3,1)=9 because we have uuuudd, uuuddu, uuudud, ududuu, uuduud, uduudu, uudduu, uduuud, uududu; T(3,2)=5 because we have uuuuud, uuuudu, uuuduu, uuduuu, uduuuu; T(3,3)=1 because we have uuuuuu. - Philippe Deléham, Apr 16 2007, Apr 17 2007, Apr 18 2007
Triangular matrix, read by rows, equal to the matrix inverse of triangle A129818. - Philippe Deléham, Jun 19 2007
Let Sum_{n>=0} a(n)*x^n = (1+x)/(1-mx+x^2) = o.g.f. of A_m, then Sum_{k=0..n} T(n,k)*a(k) = (m+2)^n. Related expansions of A_m are: A099493, A033999, A057078, A057077, A057079, A005408, A002878, A001834, A030221, A002315, A033890, A057080, A057081, A054320, A097783, A077416, A126866, A028230, A161591, for m=-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, respectively. - Philippe Deléham, Nov 16 2009
The Kn11, Kn12, Fi1 and Fi2 triangle sums link the triangle given above with three sequences; see the crossrefs. For the definitions of these triangle sums, see A180662. - Johannes W. Meijer, Apr 20 2011
4^n = (n-th row terms) dot (first n+1 odd integer terms). Example: 4^4 = 256 = (14, 28, 20, 7, 1) dot (1, 3, 5, 7, 9) = (14 + 84 + 100 + 49 + 9) = 256. - Gary W. Adamson, Jun 13 2011
The linear system of n equations with coefficients defined by the first n rows solve for diagonal lengths of regular polygons with N= 2n+1 edges; the constants c^0, c^1, c^2, ... are on the right hand side, where c = 2 + 2*cos(2*Pi/N). Example: take the first 4 rows relating to the 9-gon (nonagon), N = 2*4 + 1; with c = 2 + 2*cos(2*Pi/9) = 3.5320888.... The equations are (1,0,0,0) = 1; (1,1,0,0) = c; (2,3,1,0) = c^2; (5,9,5,1) = c^3. The solutions are 1, 2.53208..., 2.87938..., and 1.87938...; the four distinct diagonal lengths of the 9-gon (nonagon) with edge = 1. (Cf. comment in A089942 which uses the analogous operations but with c = 1 + 2*cos(2*Pi/9).) - Gary W. Adamson, Sep 21 2011
Also called the Lobb numbers, after Andrew Lobb, are a natural generalization of the Catalan numbers, given by L(m,n)=(2m+1)*Binomial(2n,m+n)/(m+n+1), where n >= m >= 0. For m=0, we get the n-th Catalan number. See added reference. - Jayanta Basu, Apr 30 2013
From Wolfdieter Lang, Sep 20 2013: (Start)
T(n, k) = A053121(2*n, 2*k). T(n, k) appears in the formula for the (2*n)-th power of the algebraic number rho(N):= 2*cos(Pi/N) = R(N, 2) in terms of the odd-indexed diagonal/side length ratios R(N, 2*k+1) = S(2*k, rho(N)) in the regular N-gon inscribed in the unit circle (length unit 1). S(n, x) are Chebyshev's S polynomials (see A049310):
  rho(N)^(2*n) = Sum_{k=0..n} T(n, k)*R(N, 2*k+1), n >= 0, identical in N > = 1. For a proof see the Sep 21 2013 comment under A053121. Note that this is the unreduced version if R(N, j) with j > delta(N), the degree of the algebraic number rho(N) (see A055034), appears.
  For the odd powers of rho(n) see A039598. (End)
Unsigned coefficients of polynomial numerators of Eqn. 2.1 of the Chakravarty and Kodama paper, defining the polynomials of A067311. - Tom Copeland, May 26 2016
The triangle is the Riordan square of the Catalan numbers in the sense of A321620. - Peter Luschny, Feb 14 2023

			Triangle T(n, k) begins:
  n\k     0     1     2     3     4     5    6   7   8  9
  0:      1
  1:      1     1
  2:      2     3     1
  3:      5     9     5     1
  4:     14    28    20     7     1
  5:     42    90    75    35     9     1
  6:    132   297   275   154    54    11    1
  7:    429  1001  1001   637   273    77   13   1
  8:   1430  3432  3640  2548  1260   440  104  15   1
  9:   4862 11934 13260  9996  5508  2244  663 135  17  1
  ... Reformatted by _Wolfdieter Lang_, Dec 21 2015
From _Paul Barry_, Feb 17 2011: (Start)
Production matrix begins
  1, 1,
  1, 2, 1,
  0, 1, 2, 1,
  0, 0, 1, 2, 1,
  0, 0, 0, 1, 2, 1,
  0, 0, 0, 0, 1, 2, 1,
  0, 0, 0, 0, 0, 1, 2, 1 (End)
From _Wolfdieter Lang_, Sep 20 2013: (Start)
Example for rho(N) = 2*cos(Pi/N) powers:
n=2: rho(N)^4 = 2*R(N,1) + 3*R(N,3) + 1*R(N, 5) =
  2 + 3*S(2, rho(N)) + 1*S(4, rho(N)), identical in N >= 1. For N=4 (the square with only one distinct diagonal), the degree delta(4) = 2, hence R(4, 3) and R(4, 5) can be reduced, namely to R(4, 1) = 1 and R(4, 5) = -R(4,1) = -1, respectively. Therefore, rho(4)^4 =(2*cos(Pi/4))^4 = 2 + 3 -1 = 4. (End)

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.
T. Myers and L. Shapiro, Some applications of the sequence 1, 5, 22, 93, 386, ... to Dyck paths and ordered trees, Congressus Numerant., 204 (2010), 93-104.

T. D. Noe, Rows n=0..50 of triangle, flattened
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].
Quang T. Bach and Jeffrey B. Remmel, Generating functions for descents over permutations which avoid sets of consecutive patterns, arXiv:1510.04319 [math.CO], 2015 (see p.25).
M. Barnabei, F. Bonetti and M. Silimbani, Two permutation classes enumerated by the central binomial coefficients, arXiv preprint arXiv:1301.1790 [math.CO], 2013 and J. Int. Seq. 16 (2013) #13.3.8
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010), Article 10.8.2, example 15.
Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.
Paul Barry, Comparing two matrices of generalized moments defined by continued fraction expansions, arXiv preprint arXiv:1311.7161 [math.CO], 2013 and J. Int. Seq. 17 (2014) # 14.5.1.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Paul Barry, Notes on the Hankel transform of linear combinations of consecutive pairs of Catalan numbers, arXiv:2011.10827 [math.CO], 2020.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 15, 29.
Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 12.
Jonathan E. Beagley and Paul Drube, Combinatorics of Tableau Inversions, Electron. J. Combin., 22 (2015), #P2.44.
S. Chakravarty and Y. Kodama, A generating function for the N-soliton solutions of the Kadomtsev-Petviashvili II equation, arXiv preprint arXiv:0802.0524v2 [nlin.SI], 2008.
Wun-Seng Chou, Tian-Xiao He, and Peter J.-S. Shiue, On the Primality of the Generalized Fuss-Catalan Numbers, J. Int. Seqs., Vol. 21 (2018), #18.2.1.
Johann Cigler, Some elementary observations on Narayana polynomials and related topics, arXiv:1611.05252 [math.CO], 2016. See p. 11.
Paul Drube, Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers, arXiv:1606.04869 [math.CO], 2016.
Paul Drube, Generalized Path Pairs and Fuss-Catalan Triangles, arXiv:2007.01892 [math.CO], 2020. See Figure 4 p. 8.
T.-X. He and L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Lin. Alg. Applic. 532 (2017) 25-41, example p 32.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Thomas Koshy, Lobb's generalization of Catalan's parenthesization problem, The College Mathematics Journal 40 (2), March 2009, 99-107, DOI:10.1080/07468342.2009.11922344.
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 11.
Andrew Lobb, Deriving the n-th Catalan number, Mathematical Gazette, Vol. 83, No. 496 (March 1999), 109-110.
Donatella Merlini and Renzo Sprugnoli, Arithmetic into geometric progressions through Riordan arrays, Discrete Mathematics 340.2 (2017): 160-174. See page 161.
Pedro J. Miana, Hideyuki Ohtsuka, and Natalia Romero, Sums of powers of Catalan triangle numbers, arXiv:1602.04347 [math.NT], 2016 (see 2.8).
A. Papoulis, A new method of inversion of the Laplace transform, Quart. Appl. Math 14 (1957), 405-414. [Annotated scan of selected pages]
Athanasios Papoulis, A new method of inversion of the Laplace transform, Quart. Appl. Math., Vol. 14, No. 4 (1957), 405-414: 124. [Note: there is a typo]
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp. 29 (129) (1975) 215-222
Yidong Sun and Fei Ma, Some new binomial sums related to the Catalan triangle, Electronic Journal of Combinatorics 21(1) (2014), #P1.33
Yidong Sun and Fei Ma, Four transformations on the Catalan triangle, arXiv preprint arXiv:1305.2017 [math.CO], 2013.
Yidong Sun and Luping Ma, Minors of a class of Riordan arrays related to weighted partial Motzkin paths. Eur. J. Comb. 39, 157-169 (2014), Table 2.2.
Wikipedia, Lobb number
W.-J. Woan, L. Shapiro and D. G. Rogers, The Catalan numbers, the Lebesgue integral and 4^{n-2}, Amer. Math. Monthly, 104 (1997), 926-931.
Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017), 3081-3091.

Columns give: A000108, A000245, A000344, A000588, A001392, A000589, A000590, A000012, A005408, A014107(n>1).
Row sums: A000984.
Triangle sums (see the comments): A000958 (Kn11), A001558 (Kn12), A088218 (Fi1, Fi2).
Cf. A008313, A039598, A084938, A000007, A067311, A321620.

/* As triangle */ [[Binomial(2*n, k+n)*(2*k+1)/(k+n+1): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 16 2015

T:=(n,k)->(2*k+1)*binomial(2*n,n-k)/(n+k+1): for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form # Emeric Deutsch, May 06 2006
T := proc(n, k) option remember; if k = n then 1 elif k > n then 0 elif k = 0 then T(n-1, 0) + T(n-1,1) else T(n-1, k-1) + 2*T(n-1, k) + T(n-1, k+1) fi end:
seq(seq(T(n, k), k = 0..n), n = 0..9) od; # Peter Luschny, Feb 14 2023

Table[Abs[Differences[Table[Binomial[2 n, n + i], {i, 0, n + 1}]]], {n, 0,7}] // Flatten (* Geoffrey Critzer, Dec 18 2011 *)
Join[{1},Flatten[Table[Binomial[2n-1,n-k]-Binomial[2n-1,n-k-2],{n,10},{k,0,n}]]] (* Harvey P. Dale, Dec 18 2011 *)
Flatten[Table[Binomial[2*n,m+n]*(2*m+1)/(m+n+1),{n,0,9},{m,0,n}]] (* Jayanta Basu, Apr 30 2013 *)

a(n, k) = (2*n+1)/(n+k+1)*binomial(2*k, n+k)
trianglerows(n) = for(x=0, n-1, for(y=0, x, print1(a(y, x), ", ")); print(""))
trianglerows(10) \\ Felix Fröhlich, Jun 24 2016

# Algorithm of L. Seidel (1877)
# Prints the first n rows of the triangle
def A039599_triangle(n) :
    D = [0]*(n+2); D[1] = 1
    b = True ; h = 1
    for i in range(2*n-1) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        if b : print([D[z] for z in (1..h-1)])
        b = not b
A039599_triangle(10)  # Peter Luschny, May 01 2012

T(n,k) = C(2*n-1, n-k) - C(2*n-1, n-k-2), n >= 1, T(0,0) = 1.
From Emeric Deutsch, May 06 2006: (Start)
T(n,k) = (2*k+1)*binomial(2*n,n-k)/(n+k+1).
G.f.: G(t,z)=1/(1-(1+t)*z*C), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function. (End)
The following formulas were added by Philippe Deléham during 2003 to 2009: (Start)
Triangle T(n, k) read by rows; given by A000012 DELTA A000007, where DELTA is Deléham's operator defined in A084938.
T(n, k) = C(2*n, n-k)*(2*k+1)/(n+k+1). Sum(k>=0; T(n, k)*T(m, k) = A000108(n+m)); A000108: numbers of Catalan.
T(n, 0) = A000108(n); T(n, k) = 0 if k>n; for k>0, T(n, k) = Sum_{j=1..n} T(n-j, k-1)*A000108(j).
T(n, k) = A009766(n+k, n-k) = A033184(n+k+1, 2k+1).
G.f. for column k: Sum_{n>=0} T(n, k)*x^n = x^k*C(x)^(2*k+1) where C(x) = Sum_{n>=0} A000108(n)*x^n is g.f. for Catalan numbers, A000108.
T(0, 0) = 1, T(n, k) = 0 if n<0 or n=1, T(n, k) = T(n-1, k-1) + 2*T(n-1, k) + T(n-1, k+1).
a(n) + a(n+1) = 1 + A000108(m+1) if n = m*(m+3)/2; a(n) + a(n+1) = A039598(n) otherwise.
T(n, k) = A050165(n, n-k).
Sum_{j>=0} T(n-k, j)*A039598(k, j) = A028364(n, k).
Matrix inverse of the triangle T(n, k) = (-1)^(n+k)*binomial(n+k, 2*k) = (-1)^(n+k)*A085478(n, k).
Sum_{k=0..n} T(n, k)*x^k = A000108(n), A000984(n), A007854(n), A076035(n), A076036(n) for x = 0, 1, 2, 3, 4.
Sum_{k=0..n} (2*k+1)*T(n, k) = 4^n.
T(n, k)*(-2)^(n-k) = A114193(n, k).
Sum_{k>=h} T(n,k) = binomial(2n,n-h).
Sum_{k=0..n} T(n,k)*5^k = A127628(n).
Sum_{k=0..n} T(n,k)*7^k = A115970(n).
T(n,k) = Sum_{j=0..n-k} A106566(n+k,2*k+j).
Sum_{k=0..n} T(n,k)*6^k = A126694(n).
Sum_{k=0..n} T(n,k)*A000108(k) = A007852(n+1).
Sum_{k=0..floor(n/2)} T(n-k,k) = A000958(n+1).
Sum_{k=0..n} T(n,k)*(-1)^k = A000007(n).
Sum_{k=0..n} T(n,k)*(-2)^k = (-1)^n*A064310(n).
T(2*n,n) = A126596(n).
Sum_{k=0..n} T(n,k)*(-x)^k = A000007(n), A126983(n), A126984(n), A126982(n), A126986(n), A126987(n), A127017(n), A127016(n), A126985(n), A127053(n) for x=1,2,3,4,5,6,7,8,9,10 respectively.
Sum_{j>=0} T(n,j)*binomial(j,k) = A116395(n,k).
T(n,k) = Sum_{j>=0} A106566(n,j)*binomial(j,k).
T(n,k) = Sum_{j>=0} A127543(n,j)*A038207(j,k).
Sum_{k=0..floor(n/2)} T(n-k,k)*A000108(k) = A101490(n+1).
T(n,k) = A053121(2*n,2*k).
Sum_{k=0..n} T(n,k)*sin((2*k+1)*x) = sin(x)*(2*cos(x))^(2*n).
T(n,n-k) = Sum_{j>=0} (-1)^(n-j)*A094385(n,j)*binomial(j,k).
Sum_{j>=0} A110506(n,j)*binomial(j,k) = Sum_{j>=0} A110510(n,j)*A038207(j,k) = T(n,k)*2^(n-k).
Sum_{j>=0} A110518(n,j)*A027465(j,k) = Sum_{j>=0} A110519(n,j)*A038207(j,k) = T(n,k)*3^(n-k).
Sum_{k=0..n} T(n,k)*A001045(k) = A049027(n), for n>=1.
Sum_{k=0..n} T(n,k)*a(k) = (m+2)^n if Sum_{k>=0} a(k)*x^k = (1+x)/(x^2-m*x+1).
Sum_{k=0..n} T(n,k)*A040000(k) = A001700(n).
Sum_{k=0..n} T(n,k)*A122553(k) = A051924(n+1).
Sum_{k=0..n} T(n,k)*A123932(k) = A051944(n).
Sum_{k=0..n} T(n,k)*k^2 = A000531(n), for n>=1.
Sum_{k=0..n} T(n,k)*A000217(k) = A002457(n-1), for n>=1.
Sum{j>=0} binomial(n,j)*T(j,k)= A124733(n,k).
Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A000984(n), A089022(n), A035610(n), A130976(n), A130977(n), A130978(n), A130979(n), A130980(n), A131521(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively.
Sum_{k=0..n} T(n,k)*A005043(k) = A127632(n).
Sum_{k=0..n} T(n,k)*A132262(k) = A089022(n).
T(n,k) + T(n,k+1) = A039598(n,k).
T(n,k) = A128899(n,k)+A128899(n,k+1).
Sum_{k=0..n} T(n,k)*A015518(k) = A076025(n), for n>=1. Also Sum_{k=0..n} T(n,k)*A015521(k) = A076026(n), for n>=1.
Sum_{k=0..n} T(n,k)*(-1)^k*x^(n-k) = A033999(n), A000007(n), A064062(n), A110520(n), A132863(n), A132864(n), A132865(n), A132866(n), A132867(n), A132869(n), A132897(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 respectively.
Sum_{k=0..n} T(n,k)*(-1)^(k+1)*A000045(k) = A109262(n), A000045:= Fibonacci numbers.
Sum_{k=0..n} T(n,k)*A000035(k)*A016116(k) = A143464(n).
Sum_{k=0..n} T(n,k)*A016116(k) = A101850(n).
Sum_{k=0..n} T(n,k)*A010684(k) = A100320(n).
Sum_{k=0..n} T(n,k)*A000034(k) = A029651(n).
Sum_{k=0..n} T(n,k)*A010686(k) = A144706(n).
Sum_{k=0..n} T(n,k)*A006130(k-1) = A143646(n), with A006130(-1)=0.
T(n,2*k)+T(n,2*k+1) = A118919(n,k).
Sum_{k=0..j} T(n,k) = A050157(n,j).
Sum_{k=0..2} T(n,k) = A026012(n); Sum_{k=0..3} T(n,k)=A026029(n).
Sum_{k=0..n} T(n,k)*A000045(k+2) = A026671(n).
Sum_{k=0..n} T(n,k)*A000045(k+1) = A026726(n).
Sum_{k=0..n} T(n,k)*A057078(k) = A000012(n).
Sum_{k=0..n} T(n,k)*A108411(k) = A155084(n).
Sum_{k=0..n} T(n,k)*A057077(k) = 2^n = A000079(n).
Sum_{k=0..n} T(n,k)*A057079(k) = 3^n = A000244(n).
Sum_{k=0..n} T(n,k)*(-1)^k*A011782(k) = A000957(n+1).
(End)
T(n,k) = Sum_{j=0..k} binomial(k+j,2j)*(-1)^(k-j)*A000108(n+j). - Paul Barry, Feb 17 2011
Sum_{k=0..n} T(n,k)*A071679(k+1) = A026674(n+1). - Philippe Deléham, Feb 01 2014
Sum_{k=0..n} T(n,k)*(2*k+1)^2 = (4*n+1)*binomial(2*n,n). - Werner Schulte, Jul 22 2015
Sum_{k=0..n} T(n,k)*(2*k+1)^3 = (6*n+1)*4^n. - Werner Schulte, Jul 22 2015
Sum_{k=0..n} (-1)^k*T(n,k)*(2*k+1)^(2*m) = 0 for 0 <= m < n (see also A160562). - Werner Schulte, Dec 03 2015
T(n,k) = GegenbauerC(n-k,-n+1,-1) - GegenbauerC(n-k-1,-n+1,-1). - Peter Luschny, May 13 2016
T(n,n-2) = A014107(n). - R. J. Mathar, Jan 30 2019
T(n,n-3) = n*(2*n-1)*(2*n-5)/3. - R. J. Mathar, Jan 30 2019
T(n,n-4) = n*(n-1)*(2*n-1)*(2*n-7)/6. - R. J. Mathar, Jan 30 2019
T(n,n-5) = n*(n-1)*(2*n-1)*(2*n-3)*(2*n-9)/30. - R. J. Mathar, Jan 30 2019

Corrected by Philippe Deléham, Nov 26 2009, Dec 14 2009

A011973 Irregular triangle read by rows: T(n,k) = binomial(n-k, k), n >= 0, 0 <= k <= floor(n/2); or, coefficients of (one version of) Fibonacci polynomials.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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
Riordan array (1/(1-x),x^2/(1-x). - 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
The diagonal sums of this triangle are A000930. - John Molokach, Jul 04 2013
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
From Gary W. Adamson, Apr 25 2022: (Start)
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

			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
From _Roger L. Bagula_, Feb 20 2009: (Start)
  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

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.

T. D. Noe, Rows n = 0..100 of triangle, flattened
S. Akbari and M. R. Oboudi, On the edge cover polynomial of a graph, European Journal of Combinatorics, 34 (2013), 297-321.
Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See p. 2.
Michael A. Allen and Kenneth Edwards, On Two Families of Generalizations of Pascal's Triangle, J. Int. Seq. 25 (2022) Article 22.7.1.
M. Barnabei, F. Bonetti, S. Elizalde, and M. Silimbani, Descent sets on 321-avoiding involutions and hook decompositions of partitions, arXiv preprint arXiv:1401.3011 [math.CO], 2014.
Paul Barry, On the duals of the Fibonacci and Catalan-Fibonacci polynomials and Motzkin paths, arXiv:2101.10218 [math.CO], 2021.
J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7.
A. Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972, p. 91, 145.
Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, and Graça Tomaz, Intrinsic Properties of a Non-Symmetric Number Triangle, J. Int. Seq., Vol. 26 (2023), Article 23.4.8.
Tom Copeland, Addendum to Elliptic Lie Triad
P. Damianou, On the characteristic polynomials of Cartan matrices and Chebyshev polynomials, arXiv preprint arXiv:1110.6620 [math.RT], 2014.
Alexandru-Nicolae Dimache, Ghiocel Groza, Marilena Jianu, and Iulian Iancu, Existence and Uniqueness of Solution Represented as Fractional Power Series for the Fractional Advection-Dispersion Equation, Symmetry (2024) Vol. 16, No. 9, Art. No. 1137.
Robert G. Donnelly, Molly W. Dunkum, Murray L. Huber, and Lee Knupp, Sign-alternating Gibonacci polynomials, arXiv:2012.14993 [math.CO], 2020.
Robert G. Donnelly, Molly W. Dunkum, Sasha V. Malone, and Alexandra Nance, Symmetric Fibonaccian distributive lattices and representations of the special linear Lie algebras, arXiv:2012.14991 [math.CO], 2020.
Robert G. Donnelly, Molly W. Dunkum, and Rachel McCoy, Olry Terquem's forgotten problem, arXiv:2303.05949 [math.HO], 2023.
N. Durov, S. Meljanac, A. Samsarov, and Z. Skoda, A universal formula for representing Lie algebra generators as formal power series with coefficients in the Weyl algebra, arXiv preprint arXiv:math/0604096 [math.RT], 2006.
Larry Ericksen, Primality Testing and Prime Constellations, Šiauliai Mathematical Seminar, Vol. 3 (11), 2008. See p. 72.
E. J. Farrell, An introduction to matching polynomials, J. Comb. Theory B 27 (1) (1979) 75-86, Table 1.
J. L. Gross, T. Mansour, T. W. Tucker, and D. G. L. Wang, Root geometry of polynomial sequences I: Type (0, 1), arXiv preprint arXiv:1501.06107 [math.CO], 2015.
A. Holme, A combinatorial proof of the duality defect conjecture in codimension 2, Discrete Math., 241 (2001), 363-378; see p. 375.
K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432 [cs.DM], 2009.
Peter Kagey, Ranking and Unranking Restricted Permutations, arXiv:2210.17021 [math.CO], 2022.
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
Franklin H.J. Kenter, and Jephian C.-H. Lin, On the error of a priori sampling: zero forcing sets and propagation time, arXiv:1709.08740 [math.CO], 2017.
Jong Hyun Kim, Hadamard products and tilings, JIS 12 (2009) 09.7.4.
Clark Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40 (4) (2002) 328-338, Example 1A.
H. Li and T. MacHenry, Permanents and Determinants, Weighted Isobaric Polynomials, and Integer Sequences, J. Int. Seq. 16 (2013) #13.3.5, example 41.
C.-K. Lim and K. S. Lam, The characteristic polynomial of ladder graphs and an annihilating uniqueness theorem, Discr. Math., 151 (1996), 161-167.
Paweł Lorek and Piotr Markowski, Conditional gambler's ruin problem with arbitrary winning and losing probabilities with applications, arXiv:1812.00687 [math.PR], 2018.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016, Section 4.1.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Table 3).
P. Olver, The canonical contact form.
A. Radhakrishnan, L. Solus, and C. Uhler, Counting Markov equivalence classes for DAG models on trees, Discrete Applied Mathematics 244 (2018): 170-185.
Michel Rigo, Manon Stipulanti, and Markus A. Whiteland, Gapped Binomial Complexities in Sequences, Univ. Liège (Belgium 2023).
Fernando Szechtman, Closed formulae for certain Fermat-Pell equations, arXiv:2107.02696 [math.NT], 2021. See Table p. 4.
Dennis Walsh, Notes on subsets of {1,2,...,n} that contain no consecutive integers.
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Eric Weisstein's World of Mathematics, Path Graph
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 26, ex. 12.
R. Witula and D. Slota, Conjugate sequences in a Fibonacci-Lucas sense and some identities for sums of powers of their elements, Integers: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A08.
R. Witula and D. Slota, On modified Chebyshev polynomials, J. Math. Anal. Appl., 324 (2006), 321-343.
R. Yanco and A. Bagchi, K-th order maximal independent sets in path and cycle graphs, Unpublished manuscript, 1994. (Annotated scanned copy)
James J. Y. Zhao, Infinite log-concavity and higher order Turán inequality for Speyer's g-polynomial of uniform matroids, arXiv:2409.08085 [math.CO], 2024. See p. 11.
Index entries for triangles and arrays related to Pascal's triangle

Row sums = A000045(n+1) (Fibonacci numbers). - Michael Somos, Apr 02 1999
Cf. A000129, A054123, A052553, A000930, A030528, A053122.
All of A011973, A092865, A098925, A102426, A169803 describe essentially the same triangle in different ways.
Cf. A007318, A025581, A055087.
Cf. A000108, A049310, A055151, A098474, A124644, A134264.
Cf. A054142, A053123, A332602.

a011973 n k = a011973_tabf !! n !! k
a011973_row n = a011973_tabf !! n
a011973_tabf = zipWith (zipWith a007318) a025581_tabl a055087_tabf
-- Reinhard Zumkeller, Jul 14 2015

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

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

{T(n, k) = if( k<0 || 2*k>n, 0, binomial(n-k, k))};

# 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

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. Hanna
T(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.
From Roger L. Bagula, Feb 20 2009: (Start)
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)
T(n, k) = A102541(2*n+2, 2*k+1) + A102541(2*n+1, 2*k) - A102541(2*n+3, 2*k+1), n >= 0 and 0 <= k <= floor(n/2). - Johannes W. Meijer, Aug 26 2013
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

A090344 Number of Motzkin paths of length n with no level steps at odd level.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 23, 47, 102, 221, 493, 1105, 2516, 5763, 13328, 30995, 72556, 170655, 403351, 957135, 2279948, 5449013, 13063596, 31406517, 75701508, 182902337, 442885683, 1074604289, 2612341856, 6361782007, 15518343597, 37912613631, 92758314874

Offset: 0

Emeric Deutsch, Jan 28 2004

nonn

a(n) = number of Motzkin paths of length n that avoid UF. Example: a(3) counts FFF, UDF, FUD but not UFD. - David Callan, Jul 15 2004

Also, number of 1-2 trees with n edges and with thinning limbs. A 1-2 tree is an ordered tree with vertices of outdegree at most 2. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children. - Emeric Deutsch and Louis Shapiro, Nov 04 2006

			a(3)=3 because we have HHH, HUD and UDH, where U=(1,1), D=(1,-1) and H=(1,0).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Rui Duarte and António Guedes de Oliveira, Generating functions of lattice paths, Univ. do Porto (Portugal 2023).

Cf. A001006, A086622, A098474, A124344, A124497.

Cf. A014137, A023431, A144700.

[(&+[Binomial(n-k, k)*Catalan(k): k in [0..Floor(n/2)]]): n in [0..40]]; // G. C. Greubel, Jun 15 2022

C:=x->(1-sqrt(1-4*x))/2/x: G:=C(z^2/(1-z))/(1-z): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n),n=0..36);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, (n^2-n+2)/2,
     ((2*n+2)*a(n-1) -(4*n-6)*a(n-3) +(3*n-4)*a(n-2))/(n+2))
    end:
seq(a(n), n=0..40); # Alois P. Heinz, May 17 2013

Table[HypergeometricPFQ[{1/2, (1-n)/2, -n/2}, {2, -n}, -16], {n, 0, 40}] (* Jean-François Alcover, Feb 20 2015, after Paul Barry *)

{a(n)=local(A=1+x);for(i=1,n,A=1/(1-x+x*O(x^n))+x^2*A^2+x*O(x^n));polcoeff(A,n)} \\ Paul D. Hanna, Jun 24 2012

[sum(binomial(n-k,k)*catalan_number(k) for k in (0..(n//2))) for n in (0..40)] # G. C. Greubel, Jun 15 2022

G.f.: (1-x-sqrt(1-2*x-3*x^2+4*x^3))/(2*x^2*(1-x)).
G.f. satisfies: A(x) = 1/(1-x) + x^2*A(x)^2. - Paul D. Hanna, Jun 24 2012
D-finite with recurrence (n+2)*a(n) = 2*(n+1)*a(n-1) + (3*n-4)*a(n-2) - 2*(2*n-3)*a(n-3). - Vladeta Jovovic, Sep 11 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*binomial(2*k, k)/(k+1). - Paul Barry, Nov 13 2004
a(n) = 1 + Sum_{k=1..n-1} a(k-1)*a(n-k-1). - Henry Bottomley, Feb 22 2005
G.f.: 1/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-... (continued fraction). - Paul Barry, Apr 08 2009
With M = an infinite tridiagonal matrix with all 1's in the super and subdiagonals and [1,0,1,0,1,0,...] in the main diagonal and V = vector [1,0,0,0,...] with the rest zeros, the sequence starting with offset 1 = leftmost column iterates of M*V. - Gary W. Adamson, Jun 08 2011
Recurrence (an alternative): (n+2)*a(n) = 3*(n+1)*a(n-1) + (n-4)*a(n-2) - (7*n-13)*a(n-3) + 2*(2*n-5)*a(n-4), n>=4. - Fung Lam, Apr 01 2014
Asymptotics: a(n) ~ (8/(sqrt(17)-1))^n*( 1/17^(1/4) + 17^(1/4) )*17 /(16*sqrt(Pi*n^3)). - Fung Lam, Apr 01 2014
a(n) = 2*A026569(n) + A026569(n+1)/2 - A026569(n+2)/2. - Mark van Hoeij, Nov 29 2024

A267633 Expansion of (1 - 4t)/(1 - x + t x^2): a Fibonacci-type sequence of polynomials.

Original entry on oeis.org

1, -4, 1, -4, 1, -5, 4, 1, -6, 8, 1, -7, 13, -4, 1, -8, 19, -12, 1, -9, 26, -25, 4, 1, -10, 34, -44, 16, 1, -11, 43, -70, 41, -4, 1, -12, 53, -104, 85, -20, 1, -13, 64, -147, 155, -61, 4, 1, -14, 76, -200, 259, -146, 24

Offset: 0

Tom Copeland, Jan 18 2016

			Row polynomials:
P(0,t) = 1 - 4t
P(1,t) = 1 - 4t = [-t(0) + (1-4t)] = -t(0) + P(0,t)
P(2,t) = 1 - 5t + 4t^2 = [-t(1-4t) + (1-4t)] = -t P(0,t) + P(1,t)
P(3,t) = 1 - 6t + 8t^2 = [-t(1-4t) + (1-5t+4t^2)] = -t P(1,t) + P(2,t)
P(4,t) = 1 - 7t + 13t^2 - 4t^3 = [-t(1-5t+4t^2) + (1-6t+8t^2)]
P(5,t) = 1 - 8t + 19t^2 - 12t^3 = [-t(1-6t+8t^2) + (1-7t+13t^2)]
P(6,t) = 1 - 9t + 26t^2 - 25t^3 + 4t^4
P(7,t) = 1 - 10t + 34t^2 - 44t^3 + 16t^4
P(8,t) = 1 - 11t + 43t^2 - 70t^3 + 41t^4 - 4t^5
P(9,t) = 1 - 12t + 53t^2 - 104t^3 + 85t^4 - 20t^5
P(10,t) = 1 - 13t + 64t^2 - 147t^3 + 155t^4 - 61t^5 + 4t^6
P(11,t) = 1 - 14t + 76t^2 - 200t^3 + 259t^4 - 146t^5 + 24t^6
...
Apparently: The odd rows for n>1 are reversed rows of A140882 (mod signs), and the even rows for n>0, the 9th, 15th, 21st, 27th, etc. rows of A228785 (mod signs). The diagonals are reverse rows of A202241.

Tom Copeland, Addendum to Elliptic Lie Triad

Cf. A000108, A000297, A008574, A008586, A011973, A022088 A034856, A084103, A098474, A124644, A140882, A202241, A228785.

p = (1 - 4 t) / (1 - x + t x^2) + O[x]^12 // CoefficientList[#, x] &;
CoefficientList[#, t] & /@ p // Flatten (* Andrey Zabolotskiy, Mar 07 2024 *)

O.g.f. G(x,t) = (1 - 4t)/(1 - x + t x^2) = a /  [t (x - (1+sqrt(a))/(2t))(x - (1-sqrt(a))/(2t))] with a = 1-4t.
Recursion P(n,t) = -t P(n-2,t) + P(n-1,t) with P(-1,t)=0 and P(0,t) = 1-4t.
Convolution of the Fibonacci polynomials of signed A011973 Fb(n,-t) with coefficients of (1-4t), e.g., (1-4t)Fb(5,-t) = (1-4t)(1-3t+t^2) = 1-7t+13t^2-4t^3, so, for n>=1 and k<=(n-1), T(n,k) = (-1)^k [-4*binomial(n-(k-1),k-1) - binomial(n-k,k)] with the convention that 1/(-m)! = 0 for m>=1, i.e., let binomial(n,k) = nint[n!/((k+c)!(n-k+c)!)] for c sufficiently small in magnitude.
Third column is A034856, and the fourth, A000297. Embedded in the coefficients of the highest order term of the polynomials is A008586 (cf. also A008574).
With P(0,t)=0, the o.g.f. is H(x,t) = (1-4t) x(1-tx)/[1-x(1-tx)] = (1-4t) Linv(Cinv(tx)/t), where Linv(x) = x/(1-x) with inverse L(x) = x/(1+x) and Cinv(x) = x (1-x) is the inverse of the o.g.f. of the shifted Catalan numbers A000108, C(x) = [1-sqrt(1-4x)]/2. Then Hinv(x,t) = C[t L(x/(1-4t))]/t = {1 - sqrt[1-4t(x/(1-4t))/[1+x/(1-4t)]]}/2t = {1-sqrt[1-4tx/(1-4t+x)]}/2t = 1/(1-4t) + (-1+t)/(1-4t)^2 x + (1-2t+2t^2)/(1-4t)^3 x^ + (-1+3t-6t^2+5t^3)/(1-4t)^4 + ..., where the numerators are the signed polynomials of A098474, reverse of A124644.
Row sums (t=1) are periodic -3,-3,0,3,3,0, repeat the six terms ... with o.g.f. -3 - 3x (1-x) / [1-x(1-x)]. Cf. A084103.
Unsigned row sums (t=-1) are shifted A022088 with o.g.f. 5 + 5x(1+x) / [x(1+x)].

Data corrected by Andrey Zabolotskiy, Mar 07 2024

A124644 Triangle read by rows. T(n, k) = binomial(n, k) * CatalanNumber(n - k).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 6, 3, 1, 14, 20, 12, 4, 1, 42, 70, 50, 20, 5, 1, 132, 252, 210, 100, 30, 6, 1, 429, 924, 882, 490, 175, 42, 7, 1, 1430, 3432, 3696, 2352, 980, 280, 56, 8, 1, 4862, 12870, 15444, 11088, 5292, 1764, 420, 72, 9, 1, 16796, 48620, 64350, 51480, 27720

Offset: 0

Farkas Janos Smile (smile_farkasjanos(AT)yahoo.com.au), Dec 21 2006

Equal to A091867*A007318. - Philippe Deléham, Dec 12 2009
Exponential Riordan array [exp(2x)*(Bessel_I(0,2x)-Bessel_I(1,2x)),x]. - Paul Barry, Mar 03 2011
From Tom Copeland, Nov 04 2014: (Start)
O.g.f: G(x,t) = C[Pinv(x,t)] =  {1 - sqrt[1 - 4 *x /(1-x*t)]}/2 where C(x) = [1 - sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108 with inverse Cinv(x) = x*(1-x), and Pinv(x,t)= -P(-x,t) = x/(1-t*x) with inverse P(x,t) = 1/(1+t*x). This puts this array in a family of arrays formed from the composition of C and P and their inverses. -G(-x,t) is the comp. inverse of the o.g.f. of A030528.
This is an Appell sequence with lowering operator d/dt p(n,t) = n*p(n-1,t) and (p(.,t)+a)^n = p(n,t+a). The e.g.f. has the form e^(x*t)/w(t) where 1/w(t) is the e.g.f. of the first column, which is the Catalan sequence A000108. (End)

			From _Paul Barry_, Jan 28 2009: (Start)
Triangle begins
   1,
   1,  1,
   2,  2,  1,
   5,  6,  3,  1,
  14, 20, 12,  4,  1,
  42, 70, 50, 20,  5,  1 (End)

Indranil Ghosh, Rows 0..125, flattened
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.

Cf. A098474 (mirror image), A000108, A091867, A030528, A104597.

Row sums give A007317(n+1).

m:=n->binomial(2*n, n)/(n+1): T:=proc(n, k) if k<=n then binomial(n, k)*m(n-k) else 0 fi end: for n from 0 to 10 do seq(T(n, k), k=0..n) od;

Table[Binomial[n, #] Binomial[2 #, #]/(# + 1) &[n - k], {n, 0, 10}, {k, 0, n}] // Flatten (* or *)
Table[Abs[(-1)^k*CatalanNumber[#] Pochhammer[-n, #]/#!] &[n - k], {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Feb 17 2017 *)

def A124644(n,k):
    return (-1)^(n-k)*catalan_number(n-k)*rising_factorial(-n,n-k)/factorial(n-k)
for n in range(7): [A124644(n,k) for k in (0..n)] # Peter Luschny, Feb 05 2015

T(n,k) = [x^(n-k)]F(-n,n-k+1;1;-1-x). - Paul Barry, Sep 05 2008
G.f.: 1/(1-xy-x/(1-x/(1-xy-x/(1-x/(1-xy-x/(1-x.... (continued fraction). - Paul Barry, Jan 06 2009
G.f.: 1/(1-x-xy-x^2/(1-2x-xy-x^2/(1-2x-xy-x^2/(1-.... (continued fraction). - Paul Barry, Jan 28 2009
T(n,k) = Sum_{i = 0..n} C(n,i)*(-1)^(n-i)*Sum{j = 0..i} C(j,k)*C(i,j)*A000108(i-j). - Paul Barry, Aug 03 2009
Sum_{k = 0..n} T(n,k)*x^k = A126930(n), A005043(n), A000108(n), A007317(n+1), A064613(n), A104455(n) for x = -2, -1, 0, 1, 2, 3 respectively. T(n,k)= A007318(n,k)*A000108(n-k). - Philippe Deléham, Dec 12 2009
E.g.f.: exp(2*x + x*y)*(Bessel_I(0,2*x) - Bessel_I(1,2*x)). - Paul Barry, Mar 10 2010
From Tom Copeland, Nov 08 2014: (Start)
O.g.f.: G(x,t) = C[P(x,t)] = [1 - sqrt(1-4*x / (1-t*x))] / 2 = Sum_{n >= 1} (C. +  t)^(n-1) * x^n] = x + (1 + t) x^2 + (2 + 2t + t^2) x^3 + ... umbrally, where (C.)^n = C_n = (1,1,2,5,8,...) = A000108(x), C(x)= x*A000108(x)= G(x,0), and P(x,t) = x/(1 + t*x), a special linear fractional (Mobius) transformation. P(x,-t)= -P(-x,t) is the inverse of P(x,t).
Inverse o.g.f.: Ginv(x,t) = P[Cinv(x),-t] = x*(1-x) / [1 - t*x(1-x)] = -A030528(-x,t), where Cinv(x) = x*(1-x) is the inverse of C(x).
G(x,t) = x*A091867(x,t+1), and Ginv(x,t) = x*A104597(x,-(t+1)). (End)
T(n, k) = (-1)^(n-k)*Catalan(n-k)*Pochhammer(-n,n-k)/(n-k)!. - Peter Luschny, Feb 05 2015
Recurrence: T(n, 0) = Catalan(n) = 1/(n+1)*binomial(2*n, n) and, for 1 <= k <= n, T(n, k) = (n/k) * T(n-1, k-1). - Peter Bala, Feb 04 2024

Name brought in line with the Maple program by Peter Luschny, Jun 21 2023

Row sums are A098506. Diagonal sums are A098507. Second column is A093527. Third column is A098508. Numerators in the inverse of the signed version of A098474, defined by T(n,k)=(-1)^(n-k)binomial(2k,k)binomial(n,k)/(k+1)

Also, with offset 1, triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and ending at the point (2k,0) (1 <= k <= n). A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps. For example, T(3,2)=4 because we have UDUUDL, UUUDLD, UUDUDL and UUUDDL.

This sequence gives the coefficients of the Jensen polynomials (increasing powers of x) of degree n and shift 1 for the Catalan sequence A000108. See A098474 for a similar comment. - Wolfdieter Lang, Jun 25 2019

Interestingly, the determinant of the n X n array of entries of the form A(i,j) is equal to the (n-1)-th superfactorial number (see A000178).
As indicated in A104455, the k-th binomial transform of A000108 will have:
   o.g.f.: (1-sqrt((1-(k+4)*x)/(1-k*x)))/(2*x),
   e.g.f.: exp((k+2)*x)*(BesselI(0,2x) - BesselI(1,2x)) and
   a(n) = Sum_{i=0..n} binomial(n, i)*CatalanNumber(i)*k^(n-i).
The columns of this array are polynomial integer sequences. The successive polynomials corresponding to the columns of this array are: p0(n) = 1, p1(n) = n + 1, p2(n) = n^2 + 2n + 2, p3(n) = n^3 + 3*n^2 + 6*n + 5, p4(n) = n^4 + 4*n^3 + 12*n^2 + 20*n + 14, and so forth. The coefficients of these successive polynomials form a number triangle, which is given by A098474.

cp's OEIS Frontend

A039599 Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A011973 Irregular triangle read by rows: T(n,k) = binomial(n-k, k), n >= 0, 0 <= k <= floor(n/2); or, coefficients of (one version of) Fibonacci polynomials.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

A090344 Number of Motzkin paths of length n with no level steps at odd level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A267633 Expansion of (1 - 4t)/(1 - x + t x^2): a Fibonacci-type sequence of polynomials.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A124644 Triangle read by rows. T(n, k) = binomial(n, k) * CatalanNumber(n - k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A098505 Numerators in inverse of a Catalan scaled binomial matrix.

Views

Author

Keywords

Comments

Examples

A247493 Triangle read by rows: T(n, k) = C(n, k)C(2k, k)/(k+1) - sum(j = 0..k, (-1)^j(1-j)^nC(k, j)/k!), 0<=k<=n.