login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A039599 Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x). 127
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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<=j<=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<=k<=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(T(n, k)*R(N, 2*k+1), k = 0..n), 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)

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

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.

Papoulis, Athanasios. "A new method of inversion of the Laplace transform." Quart. Appl. Math 14.405-414 (1957): 124. [NB: there is a typo]

LINKS

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, 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. - From N. J. A. Sloane, Feb 09 2013

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.

P. Barry, Comparing two matrices of generalized moments defined by continued fraction expansions, arXiv preprint arXiv:1311.7161 [math.CO], 2013.

Jonathan E. Beagley, Paul Drube, Combinatorics of Tableau Inversions, Electron. J. Combin., 22 (2015), #P2.44.

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.

Andrew Lobb, Deriving the n-th Catalan number, Mathematical Gazette 83 (8), March 1999, 109-110.

Pedro J. Miana, Hideyuki Ohtsuka, 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]

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.

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.

FORMULA

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<k; T(n, 0) = T(n-1, 0) + T(n-1, 1); for k>=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_{0<=k<=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<=k<=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_{0<=k<=n} T(n,k)*5^k = A127628(n) .

Sum_{0<=k<=n} T(n,k)*7^k = A115970(n) .

T(n,k) = Sum_{j, 0<=j<=n-k} A106566(n+k,2*k+j).

Sum_{0<=k<=n} T(n,k)*6^k = A126694(n).

Sum_{0<=k<=n} T(n,k)*A000108(k) = A007852(n+1).

Sum_{0<=k<=[n/2]} T(n-k,k) = A000958(n+1).

Sum_{0<=k<=n} T(n,k)*(-1)^k = A000007(n).

Sum_{0<=k<=n} T(n,k)*(-2)^k = (-1)^n*A064310(n).

T(2*n,n) = A126596(n).

Sum_{0<=k<=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_{0<=k<=[n/2]} T(n-k,k)*A000108(k) = A101490(n+1).

T(n,k) = A053121(2*n,2*k).

Sum_{0<=k<=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, 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, j>=0}A110519(n,j)*A038207(j,k) = T(n,k)*3^(n-k).

Sum_{0<=k<=n} T(n,k)*A001045(k) = A049027(n), for n>=1.

Sum_{0<=k<=n} T(n,k)*a(k) = (m+2)^n if Sum_{k, k>=0}a(k)*x^k = (1+x)/(x^2-m*x+1).

Sum_{0<=k<=n} T(n,k)*A040000(k) = A001700(n).

Sum_{0<=k<=n} T(n,k)*A122553(k) = A051924(n+1).

Sum_{0<=k<=n} T(n,k)*A123932(k) = A051944(n).

Sum_{0<=k<=n} T(n,k)*k^2 = A000531(n), for n>=1.

Sum_{0<=k<=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_{0<=k<=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_{0<=k<=n} T(n,k)*A005043(k) = A127632(n).

Sum_{0<=k<=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_{0<=k<=n} T(n,k)*A015518(k) = A076025(n), for n>=1. Also Sum_{k, 0<=k<=n}T(n,k)*A015521(k) = A076026(n), for n>=1.

Sum_{0<=k<=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_{0<=k<=n} T(n,k)*(-1)^(k+1)*A000045(k) = A109262(n), A000045:= Fibonacci numbers.

Sum_{0<=k<=n} T(n,k)*A000035(k)*A016116(k) = A143464(n).

Sum_{0<=k<=n} T(n,k)*A016116(k) = A101850(n).

Sum_{0<=k<=n} T(n,k)*A010684(k) = A100320(n).

Sum_{0<=k<=n} T(n,k)*A000034(k) = A029651(n).

Sum_{0<=k<=n} T(n,k)*A010686(k) = A144706(n).

Sum_{0<=k<=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_{0<=k<=j} T(n,k) = A050157(n,j).

Sum_{0<=k<=2} T(n,k) = A026012(n); Sum_{k, 0<=k<=3}T(n,k)=A026029(n).

Sum_{0<=k<=n} T(n,k)*A000045(k+2) = A026671(n).

Sum_{0<=k<=n} T(n,k)*A000045(k+1) = A026726(n).

Sum_{0<=k<=n} T(n,k)*A057078(k) = A000012(n).

Sum_{0<=k<=n} T(n,k)*A108411(k) = A155084(n).

Sum_{0<=k<=n} T(n,k)*A057077(k) = 2^n = A000079(n).

Sum_{0<=k<=n} T(n,k)*A057079(k) = 3^n = A000244(n).

Sum_{0<=k<=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

EXAMPLE

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

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

- Paul Barry, Feb 17 2011

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)

MAPLE

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

MATHEMATICA

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

PROG

(Sage) # 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

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

CROSSREFS

Diagonals give: A000108 A000245 A000344 A000588 A001392 A000589 A000590, A000012 A005408 A014107(n>1) Row sums: A000984

Cf. A008313 A039598 A084938 A000007

Triangle sums (see the comments): A000958 (Kn11), A001558 (Kn12), A088218 (Fi1, Fi2).

Sequence in context: A055905 A147703 A147747 * A154380 A155083 A011357

Adjacent sequences:  A039596 A039597 A039598 * A039600 A039601 A039602

KEYWORD

nonn,tabl,easy,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Clark Kimberling

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 26 00:53 EDT 2016. Contains 273303 sequences.