cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 21-30 of 124 results. Next

A001405 a(n) = binomial(n, floor(n/2)).

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520, 300540195, 601080390, 1166803110
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Sperner's theorem says that this is the maximal number of subsets of an n-set such that no one contains another.
When computed from index -1, [seq(binomial(n,floor(n/2)), n = -1..30)]; -> [1,1,1,2,3,6,10,20,35,70,126,...] and convolved with aerated Catalan numbers [seq(((n+1) mod 2)*binomial(n,n/2)/((n/2)+1), n = 0..30)]; -> [1,0,1,0,2,0,5,0,14,0,42,0,132,0,...] shifts left by one: [1,1,2,3,6,10,20,35,70,126,252,...] and if again convolved with aerated Catalan numbers, gives A037952 apart from the initial term. - Antti Karttunen, Jun 05 2001 [This is correct because the g.f.'s satisfy (1+x*g001405(x))*g126120(x) = g001405(x) and g001405(x)*g126120(x) = g037952(x)/x. - R. J. Mathar, Sep 23 2021]
Number of ordered trees with n+1 edges, having nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002
Gives for n >= 1 the maximum absolute column sum norm of the inverse of the Vandermonde matrix (a_ij) i=0..n-1, j=0..n-1 with a_00=1 and a_ij=i^j for (i,j) != (0,0). - Torsten Muetze, Feb 06 2004
Image of Catalan numbers A000108 under the Riordan array (1/(1-2x),-x/(1-2x)) or A065109. - Paul Barry, Jan 27 2005
Number of left factors of Dyck paths, consisting of n steps. Example: a(4)=6 because we have UDUD, UDUU, UUDD, UUDU, UUUD and UUUU, where U=(1,1) and D=(1,-1). - Emeric Deutsch, Apr 23 2005
Number of dispersed Dyck paths of length n; they are defined as concatenations of Dyck paths and (1,0)-steps on the x-axis; equivalently, Motzkin paths with no (1,0)-steps at positive height. Example: a(4)=6 because we have HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD, where U=(1,1), H=(1,0), and D=(1,-1). - Emeric Deutsch, Jun 04 2011
a(n) is odd iff n=2^k-1. - Jon Perry, May 05 2005
An inverse Chebyshev transform of binomial(1,n)=(1,1,0,0,0,...) where g(x)->(1/sqrt(1-4*x^2))*g(x*c(x^2)), with c(x) the g.f. of A000108. - Paul Barry, May 13 2005
In a random walk on the number line, starting at 0 and with 0 absorbing after the first step, number of ways of ending up at a positive integer after n steps. - Joshua Zucker, Jul 31 2005
Maximum number of sums of the form Sum_{i=1..n} e(i)*a(i) that are congruent to 0 mod q, where e_i=0 or 1 and gcd(a_i,q)=1, provided that q > ceiling(n/2). - Ralf Stephan, Apr 27 2003
Also the number of standard tableaux of height <= 2. - Mike Zabrocki, Mar 24 2007
Hankel transform of this sequence forms A000012 = [1,1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
A001263 * [1, -2, 3, -4, 5, ...] = [1, -1, -2, 3, 6, -10, -20, 35, 70, -126, ...]. - Gary W. Adamson, Jan 02 2008
Equals right border of triangle A153585. - Gary W. Adamson, Dec 28 2008
Second binomial transform of A168491. - Philippe Deléham, Nov 27 2009
a(n) is also the number of distinct strings of length n, each of which is a prefix of a string of balanced parentheses; see example. - Lee A. Newberg, Apr 26 2010
Number of symmetric balanced strings of n pairs of parentheses; see example. - Joerg Arndt, Jul 25 2011
a(n) is the number of permutation patterns modulo 2. - Olivier Gérard, Feb 25 2011
For n >= 2, a(n-1) is the number of incongruent two-color bracelets of 2*n-1 beads, n of which are black (A007123), having a diameter of symmetry. - Vladimir Shevelev, May 03 2011
The number of permutations of n elements where p(k-2) < p(k) for all k. - Joerg Arndt, Jul 23 2011
Also size of the equivalence class of S_{n+1} containing the identity permutation under transformations of positionally adjacent elements of the form abc <--> cba where a < b < c, cf. A210668. - Tom Roby, May 15 2012
a(n) is the number of symmetric Dyck paths of length 2n. - Matt Watson, Sep 26 2012
a(n) is divisible by A000108(floor(n/2)) = abs(A129996(n-2)). - Paul Curtz, Oct 23 2012
a(n) is the number of permutations of length n avoiding both 213 and 231 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
Number of symmetric standard Young tableaux of shape (n,n). - Ran Pan, Apr 10 2015
From Luciano Ancora, May 09 2015: (Start)
Also "stepped path" in the array formed by partial sums of the all 1's sequence (or a Pascal's triangle displayed as a square). Example:
[1], [1], 1, 1, 1, 1, 1, ... A000012
1, [2], [3], 4, 5, 6, 7, ...
1, 3, [6], [10], 15, 21, 28, ...
1, 4, 10, [20], [35], 56, 84, ...
1, 5, 15, 35, [70], [126], 210, ...
Sequences in second formula are the mixed diagonals shown in this array. (End)
a(n) = A265848(n,n). - Reinhard Zumkeller, Dec 24 2015
The constant Sum_{n >= 0} a(n)/n! is 1 + A130820. - Peter Bala, Jul 02 2016
Number of meanders (walks starting at the origin and ending at any altitude >= 0 that may touch but never go below the x-axis) with n steps from {-1,1}. - David Nguyen, Dec 20 2016
a(n) is also the number of paths of n steps (either up or down by 1) that end at the maximal value achieved along the path. - Winston Luo, Jun 01 2017
Number of binary n-tuples such that the number of 1's in the even positions is the same as the number of 1's in the odd positions. - Juan A. Olmos, Dec 21 2017
Equivalently, a(n) is the number of subsets of {1,...,n} containing as many even numbers as odd numbers. - Gus Wiseman, Mar 17 2018
a(n) is the number of Dyck paths with semilength = n+1, returns to the x-axis = floor((n+3)/2) and up movements in odd positions = floor((n+3)/2). Example: a(4)=6, U=up movement in odd position, u=up movement in even position, d=down movement, -=return to x-axis: Uududd-Ud-Ud-, Ud-Uudd-Uudd-, Uudd-Uudd-Ud-, Ud-Ud-Uududd-, Uudd-Ud-Uudd-, Ud-Uududd-Ud-. - Roger Ford, Dec 29 2017
Let C_n(R, H) denote the transition matrix from the ribbon basis to the homogeneous basis of the graded component of the algebra of noncommutative symmetric functions of order n. Letting I(2^(n-1)) denote the identity matrix of order 2^(n-1), it has been conjectured that the dimension of the kernel of C_n(R, H) - I(2^(n-1)) is always equal to a(n-1). - John M. Campbell, Mar 30 2018
The number of U-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are U-equivalent iff the positions of pattern U are identical in these paths. - Sergey Kirgizov, Apr 08 2018
All binary self-dual codes of length 2n, for n > 0, must contain at least a(n) codewords of weight n. More to the point, there will always be at least one, perhaps unique, binary self-dual code of length 2n that will contain exactly a(n) codewords that have a hamming weight equal to half the length of the code (n). This code can be constructed by direct summing the unique binary self-dual code of length 2 (up to permutation equivalence) to itself n times. A permutation equivalent code can be constructed by augmenting two identity matrices of length n together. - Nathan J. Russell, Nov 25 2018
Closed under addition. - Torlach Rush, Apr 18 2019
The sequence starting (1, 2, 3, 6, ...) is the invert transform of A097331: (1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...). - Gary W. Adamson, Feb 22 2020
From Gary W. Adamson, Feb 24 2020: (Start)
The sequence is the culminating limit of an infinite set of sequences with convergents of 2*cos(Pi/N), N = (3, 5, 7, 9, ...).
The first few such sequences are:
N = 3: (1, 1, 1, 1, 1, 1, 1, 1, ...)
N = 5: (1, 1, 2, 3, 5, 8, 13, 21, ...) = A000045
N = 7: (1, 1, 2, 3, 6, 10, 19, 33, ...) = A028495, a(n)/a(n-1) tends to 1.801937...
N = 9 (1, 1, 2, 3, 6, 10, 20, 35, ...) = A061551, a(n)/a(n_1) tends to 1.879385...
...
In the limit one gets the current sequence with ratio 2. (End)
a(n) is also the number of monotone lattice paths from (0,0) to (floor(n/2),ceiling(n/2)). These are the number of Grand Dyck paths when n is even. - Nachum Dershowitz, Aug 12 2020
The maximum number of preimages that a permutation of length n+1 can have under the consecutive-132-avoiding stack-sorting map. - Colin Defant, Aug 28 2020
Counts faro permutations of length n. Faro permutations are permutations avoiding the three consecutive patterns 231, 321 and 312. They are obtained by a perfect faro shuffle of two nondecreasing words of lengths differing by at most one. - Sergey Kirgizov, Jan 12 2021
Per "Sperner's Theorem", the largest possible familes of finite sets none of which contain any other sets in the family. - Renzo Benedetti, May 26 2021
a(n-1) are the incomplete, primitive Dyck paths of n steps without a first return: paths of U and D steps starting at the origin, never touching the horizontal axis later on, and ending above the horizontal axis. n=1: {U}, n=2: {UU}, n=3: {UUU, UUD}, n=4: {UUUU, UUUD, UUDU}, n=5: {UUUUU, UUUUD, UUUDD, UUDUU, UUUDU, UUDUD}. For comparison: A037952 counts incomplete Dyck paths with n steps with any number of intermediate returns to the horizontal axis, ending above the horizontal axis. - R. J. Mathar, Sep 24 2021
a(n) is the number of noncrossing partitions of [n] whose nontrivial blocks are of type {a,b}, with a <= n/2, b > n/2. - Francesca Aicardi, May 29 2022
Maximal coefficient of (1+x)^n. - Vaclav Kotesovec, Dec 30 2022
Sums of lower-left-to-upper-right diagonals of the Catalan Triangle A001263. - Howard A. Landman, Sep 16 2024

Examples

			For n = 4, the a(4) = 6 distinct strings of length 4, each of which is a prefix of a string of balanced parentheses, are ((((, (((), (()(, ()((, ()(), and (()). - _Lee A. Newberg_, Apr 26 2010
There are a(5)=10 symmetric balanced strings of 5 pairs of parentheses:
[ 1] ((((()))))
[ 2] (((()())))
[ 3] ((()()()))
[ 4] ((())(()))
[ 5] (()()()())
[ 6] (()(())())
[ 7] (())()(())
[ 8] ()()()()()
[ 9] ()((()))()
[10] ()(()())() - _Joerg Arndt_, Jul 25 2011
G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 35*x^7 + 70*x^8 + ...
The a(4)=6 binary 4-tuples such that the number of 1's in the even positions is the same as the number of 1's in the odd positions are 0000, 1100, 1001, 0110, 0011, 1111. - _Juan A. Olmos_, Dec 21 2017

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. 828.
  • M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 135.
  • K. Engel, Sperner Theory, Camb. Univ. Press, 1997; Theorem 1.1.1.
  • P. Frankl, Extremal sets systems, Chap. 24 of R. L. Graham et al., eds, Handbook of Combinatorics, North-Holland.
  • J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(b), p. 452.

Links

Crossrefs

Row sums of Catalan triangle A053121 and of symmetric Dyck paths A088855.
Enumerates the structures encoded by A061854 and A061855.
First differences are in A037952.
Apparently a(n) = lim_{k->infinity} A094718(k, n).
Partial sums are in A036256. Column k=2 of A182172. Column k=1 of A335570.
Bisections: A000984 (even part), A001700 (odd part).
Cf. A000712, A001006, A001700, A005773, A005817, A007578, A007579, A022916, A022917 (permutation patterns mod k), A049401, A051920, A063886, A130820, A132815, A153585, A239241, A265848.
Cf. A097331.
Cf. A000045, A028495, A061551
Cf. A107373, A340567, A340568, A340569 (popularity of certain patterns in faro permutations).

Programs

  • GAP
    List([0..40],n->Binomial(n,Int(n/2))); # Muniru A Asiru, Apr 08 2018
  • Haskell
    a001405 n = a007318_row n !! (n `div` 2) -- Reinhard Zumkeller, Nov 09 2011
  • Magma
    [Binomial(n, Floor(n/2)): n in [0..40]]; // Vincenzo Librandi, Nov 16 2014
  • Maple
    A001405 := n->binomial(n, floor(n/2)): seq(A001405(n), n=0..33);
  • Mathematica
    Table[Binomial[n, Floor[n/2]], {n, 0, 40}] (* Stefan Steinerberger, Apr 08 2006 *)
Table[DifferenceRoot[Function[{a,n},{-4 n a[n]-2 a[1+n]+(2+n) a[2+n] == 0,a[1] == 1,a[2] == 1}]][n], {n, 30}] (* Luciano Ancora, Jul 08 2015 *)
Array[Binomial[#,Floor[#/2]]&,40,0] (* Harvey P. Dale, Mar 05 2018 *)
  • Maxima
    A001405(n):=binomial(n,floor(n/2))$
makelist(A001405(n),n,0,30); /* Martin Ettl, Nov 01 2012 */
  • PARI
    a(n) = binomial(n, n\2);
  • PARI
    first(n) = x='x+O('x^n); Vec((-1+2*x+sqrt(1-4*x^2))/(2*x-4*x^2)) \\ Iain Fox, Dec 20 2017 (edited by Iain Fox, May 07 2018)
  • Python
    from math import comb
def A001405(n): return comb(n,n//2) # Chai Wah Wu, Jun 07 2022

Formula

a(n) = max_{k=0..n} binomial(n, k).
a(2*n) = A000984(n), a(2*n+1) = A001700(n).
By symmetry, a(n) = binomial(n, ceiling(n/2)). - Labos Elemer, Mar 20 2003
P-recursive with recurrence: a(0) = 1, a(1) = 1, and for n >= 2, (n+1)*a(n) = 2*a(n-1) + 4*(n-1)*a(n-2). - Peter Bala, Feb 28 2011
G.f.: (1+x*c(x^2))/sqrt(1-4*x^2) = 1/(1 - x - x^2*c(x^2)); where c(x) = g.f. for Catalan numbers A000108.
G.f.: (-1 + 2*x + sqrt(1-4*x^2))/(2*x - 4*x^2). - Lee A. Newberg, Apr 26 2010
G.f.: 1/(1 - x - x^2/(1 - x^2/(1 - x^2/(1 - x^2/(1 - ... (continued fraction). - Paul Barry, Aug 12 2009
a(0) = 1; a(2*m+2) = 2*a(2*m+1); a(2*m+1) = Sum_{k = 0..2*m} (-1)^k*a(k)*a(2*m-k). - Len Smiley, Dec 09 2001
G.f.: (sqrt((1+2*x)/(1-2*x)) - 1)/(2*x). - Vladeta Jovovic, Apr 28 2003
The o.g.f. A(x) satisfies A(x) + x*A^2(x) = 1/(1-2*x). - Peter Bala, Feb 28 2011
E.g.f.: BesselI(0, 2*x) + BesselI(1, 2*x). - Vladeta Jovovic, Apr 28 2003
a(0) = 1; a(2*m+2) = 2*a(2*m+1); a(2*m+1) = 2*a(2*m) - c(m), where c(m)=A000108(m) are the Catalan numbers. - Christopher Hanusa (chanusa(AT)washington.edu), Nov 25 2003
a(n) = Sum_{k=0..n} (-1)^k*2^(n-k)*binomial(n, k)*A000108(k). - Paul Barry, Jan 27 2005
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*binomial(1, n-2*k). - Paul Barry, May 13 2005
From Paul Barry, Nov 02 2004: (Start)
a(n) = Sum_{k=0..floor((n+1)/2)} (binomial(n+1, k)*(cos((n-2*k+1)*Pi/2) + sin((n-2*k+1)*Pi/2))).
a(n) = Sum_{k=0..n+1}, (binomial(n+1, (n-k+1)/2)*(1-(-1)^(n-k))*(cos(k*Pi/2) + sin(k*Pi))/2). (End)
a(n) = Sum_{k=floor(n/2)..n} (binomial(n,n-k) - binomial(n,n-k-1)). - Paul Barry, Sep 06 2007
Inverse binomial transform of A005773 starting (1, 2, 5, 13, 35, 96, ...) and double inverse binomial transform of A001700. Row sums of triangle A132815. - Gary W. Adamson, Aug 31 2007
a(n) = Sum_{k=0..n} A120730(n,k). - Philippe Deléham, Oct 16 2008
a(n) = Sum_{k = 0..floor(n/2)} (binomial(n,k) - binomial(n,k-1)). - Nishant Doshi (doshinikki2004(AT)gmail.com), Apr 06 2009
Sum_{n>=0} a(n)/10^(n+1) = 0.1123724... = (sqrt(3)-sqrt(2))/(2*sqrt(2)); Sum_{n>=0} a(n)/100^(n+1) = 0.0101020306102035... = (sqrt(51)-sqrt(49))/(2*sqrt(49)). - Mark Dols, Jul 15 2010
Conjectured: a(n) = 2^n*2F1(1/2,-n;2;2), useful for number of paths in 1-d for which the coordinate is never negative. - Benjamin Phillabaum, Feb 20 2011
a(2*m+1) = (2*m+1)*a(2*m)/(m+1), e.g., a(7) = (7/4)*a(6) = (7/4)*20 = 35. - Jon Perry, Jan 20 2011
From Peter Bala, Feb 28 2011: (Start)
Let F(x) be the logarithmic derivative of the o.g.f. A(x). Then 1+x*F(x) is the o.g.f. for A027306.
Let G(x) be the logarithmic derivative of 1+x*A(x). Then x*G(x) is the o.g.f. for A058622. (End)
Let M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [1,0,0,0,...] in the main diagonal; and V = the vector [1,0,0,0,...]. a(n) = M^n*V, leftmost term. - Gary W. Adamson, Jun 13 2011
Let M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [1,0,0,0,...] in the main diagonal. a(n) = M^n_{1,1}. - Corrected by Gary W. Adamson, Jan 30 2012
a(n) = A007318(n, floor(n/2)). - Reinhard Zumkeller, Nov 09 2011
a(n+1) = Sum_{k=0..n} a(n-k)*A097331(k) = a(n) + Sum_{k=0..(n-1)/2} A000108(k)*a(n-2*k-1). - Philippe Deléham, Nov 27 2011
a(n) = A214282(n) - A214283(n), for n > 0. - Reinhard Zumkeller, Jul 14 2012
a(n) = Sum_{k=0..n} A168511(n,k)*(-1)^(n-k). - Philippe Deléham, Mar 19 2013
a(n+2*p-2) = Sum_{k=0..floor(n/2)} A009766(n-k+p-1, k+p-1) + binomial(n+2*p-2, p-2), for p >= 1. - Johannes W. Meijer, Aug 02 2013
O.g.f.: (1-x*c(x^2))/(1-2*x), with the o.g.f. c(x) of Catalan numbers A000108. See the rewritten formula given by Lee A. Newberg above. This is the o.g.f. for the row sums the Riordan triangle A053121. - Wolfdieter Lang, Sep 22 2013
a(n) ~ 2^n / sqrt(Pi * n/2). - Charles R Greathouse IV, Oct 23 2015
a(n) = 2^n*hypergeom([1/2,-n], [2], 2). - Vladimir Reshetnikov, Nov 02 2015
a(2*k) = Sum_{i=0..k} binomial(k, i)*binomial(k, i), a(2*k+1) = Sum_{i=0..k} binomial(k+1, i)*binomial(k, i). - Juan A. Olmos, Dec 21 2017
a(0) = 1, a(n) = 2 * a(n-1) for even n, a(n) = (2*n/(n+1)) * a(n-1) for odd n. - James East, Sep 25 2019
a(n) = A037952(n) + A000108(n/2) where A(.)=0 for non-integer argument. - R. J. Mathar, Sep 23 2021
From Amiram Eldar, Mar 10 2022: (Start)
Sum_{n>=0} 1/a(n) = 2*Pi/(3*sqrt(3)) + 2.
Sum_{n>=0} (-1)^n/a(n) = 2/3 - 2*Pi/(9*sqrt(3)). (End)
For k>2, Sum_{n>=0} a(n)/k^n = (sqrt((k+2)/(k-2)) - 1)*k/2. - Vaclav Kotesovec, May 13 2022
From Peter Bala, Mar 24 2023: (Start)
a(n) = Sum_{k = 0..n+1} (-1)^(k+binomial(n+2,2)) * k/(n+1) * binomial(n+1,k)^2.
(n + 1)*(2*n - 1)*a(n) = (-1)^(n+1)*2*a(n-1) + 4*(n - 1)*(2*n + 1)*a(n-2) with a(0) = a(1) = 1. (End)
a(n) = Integral_{x=-2..2} x^n*W(x)*dx, n>=0, where W(x) = sqrt((2+x)/(2-x))/(2*Pi) is a positive function on x=(-2,2) and is singular at x = 2. Therefore a(n) is a positive definite sequence. - Karol A. Penson, May 12 2025

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

Original entry on oeis.org

0, 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, 180, 184, 202, 204, 210, 212, 216, 226, 228, 232, 240, 682, 684, 690, 692, 696, 714, 716, 722, 724, 728, 738, 740, 744, 752, 810, 812, 818, 820, 824, 842, 844, 850, 852, 856, 866, 868, 872, 880, 906, 908, 914
Offset: 0

Views

Author

Wouter Meeussen

Keywords

Comments

The binary Dyck-Language (A063171) in decimal representation.
These encode width 2n mountain ranges, rooted planar trees of n+1 vertices and n edges, planar planted trees with n nodes, rooted plane binary trees with n+1 leaves (2n edges, 2n+1 vertices, n internal nodes, the root included), Dyck words, binary bracketings, parenthesizations, non-crossing handshakes and partitions and many other combinatorial structures in Catalan family, enumerated by A000108.
Is Sum_{k=1..n} a(k) / n^(5/2) bounded? - Benoit Cloitre, Aug 18 2002
This list is the intersection of A061854 and A031443. - Jason Kimberley, Jan 18 2013
The sequence does start at n = 0, since in the binary interpretation of the Dyck language (e.g., as parenthesizations where "1" stands for "(" and "0" stands for ")") having a(0) = 0 will do since it would stand for the empty string where the "0"s and "1"s are balanced (hence the parentheses are balanced). - Daniel Forgues, Feb 17 2013
It appears that for n>=1 this sequence can be obtained by concatenating the terms of the irregular array whose n-th row length is A000108(n) and that is defined recursively by B(n,0) = A020988(n) and B(n,k) = B(n, k-1) + D(n, k-1) where D(x,y) = (2^(2*(A089309(B(x,y))-1))-1)*(2/3) + 2^A007814(B(x,y)). - Raúl Mario Torres Silva and Michel Marcus, May 01 2020
This encoding is related to the ranking by standard ordered tree numbers in that (1) the binary encoding of trees ordered by standard ranking is given by A358505, while (2) the standard ranking of trees ordered by binary encoding is given by A358523. - Gus Wiseman, Nov 21 2022

Examples

			a(19) = 226_10 = 11100010_2 = A063171(19) as bracket expression: ( ( ( ) ) )( ) and as a binary tree, proceeding from left to right in depth-first fashion, with 1's in binary expansion standing for internal (branching) nodes and 0's for leaves:
  0   0
   \ /
    1   0 0  (0)
     \ /   \ /
      1     1
       \   /
         1
Note that in this coding scheme the last leaf of the binary trees (here in parentheses) is implicit. This tree can be also converted to a particular S-expression in languages like Lisp, Scheme and Prolog, if we interpret its internal nodes (1's) as cons cells with each leftward leaning branch being the "car" and the rightward leaning branch the "cdr" part of the pair, with the terminal nodes (0's) being ()'s (NILs). Thus we have (cons (cons (cons () ()) ()) (cons () ())) = '( ( ( () . () ) . () ) . ( () . () ) ) = (((())) ()) i.e., the same bracket expression as above, but surrounded by extra parentheses. This mapping is performed by the Scheme function A014486->parenthesization given below.
From _Gus Wiseman_, Nov 21 2022: (Start)
The terms and corresponding ordered rooted trees begin:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))
(End)

References

  • Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 443 (Algorithm P).

Links

Crossrefs

Characteristic function: A080116. Inverse function: A080300.
The terms of binary width 2n are counted by A000108(n). Subset of A036990. Number of peaks in each mountain (number of leaves in rooted plane general trees): A057514. Number of trailing zeros in the binary expansion: A080237. First differences: A085192.
Cf. also A009766, A014137, A071156, A079436, A085184, A213704.
Cf. A020988, A089309, A007814.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
The standard ranking of the ordered tree is A358523.
The depth of the ordered tree is A358550.
Nodes of the ordered tree are counted by A358551.
Cf. A000081, A001263, A358505, A358524.

Programs

  • Maple
    # Maple procedure CatalanUnrank is adapted from the algorithm 3.24 of the CAGES book and the Scheme function CatalanUnrank from Ruskey's thesis. See the a089408.c program for the corresponding C procedures.
CatalanSequences := proc(upto_n) local n,a,r; a := []; for n from 0 to upto_n do for r from 0 to (binomial(2*n,n)/(n+1))-1 do a := [op(a),CatalanUnrank(n,r)]; od; od; return a; end;
CatalanUnrank := proc(n,rr) local r,x,y,lo,m,a; r := (binomial(2*n,n)/(n+1))-(rr+1); y := 0; lo := 0; a := 0; for x from 1 to 2*n do m := Mn(n,x,y+1); if(r <= lo+m-1) then y := y+1; a := 2*a + 1; else lo := lo+m; y := y-1; a := 2*a; fi; od; return a; end;
Mn := (n,x,y) -> binomial(2*n-x,n-((x+y)/2)) - binomial(2*n-x,n-1-((x+y)/2));
# Alternative:
bin := n -> ListTools:-Reverse(convert(n, base, 2)):
isA014486 := proc(n): local B, s, b; s := 0;
    if n > 0 then
      for b in bin(n) do
          s := s + ifelse(b = 1, 1, -1);
           if 0 > s then return false fi;
      od fi;
  s = 0 end:
select(isA014486, [seq(0..240)]);  # Peter Luschny, Mar 13 2024
  • Mathematica
    cat[ n_ ] := (2 n)!/n!/(n+1)!; b2d[li_List] := Fold[2#1+#2&, 0, li]
d2b[n_Integer] := IntegerDigits[n, 2]
tree[n_] := Join[Table[1, {i, 1, n}], Table[0, {i, 1, n}]]
nexttree[t_] := Flatten[Reverse[t]/. {a___, 0, 0, 1, b___}:> Reverse[{Sort[{a, 0}]//Reverse, 1, 0, b}]]
wood[ n_ /; n<8 ] := NestList[ nexttree, tree[ n ], cat[ n ]-1 ]
Table[ Reverse[ b2d/@wood[ j ] ], {j, 0, 6} ]//Flatten
(* Alternative code *)
tbQ[n_]:=Module[{idn2=IntegerDigits[n,2]},Count[idn2,1]==Length[idn2]/2&&Min[Accumulate[idn2/.{0->-1}]]>=0]; Join[{0},Select[Range[900],tbQ]] (* Harvey P. Dale, Jul 04 2013 *)
balancedQ[0] = True; balancedQ[n_] := Module[{s = 0}, Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0] ]; A014486 = FromDigits /@ IntegerDigits[Select[Range[0, 1000], balancedQ ]] (* Jean-François Alcover, Mar 05 2016 *)
A014486Q[0] = True; A014486Q[n_] := Catch[Fold[If[# < 0, Throw[False], If[#2 == 0, # - 1, # + 1]] &, 0, IntegerDigits[n, 2]] == 0]; Select[Range[0, 880], A014486Q] (* JungHwan Min, Dec 11 2016 *)
(* Uses Algorithm P from Knuth's TAOCP section 7.2.1.6 - see References and Links. *)
alist[n_] := Block[{a = Flatten[Table[{1, 0}, n]], m = 2*n - 1, j, k},
    FromDigits[#, 2]& /@ Reap[
    While[True,
        Sow[a]; a[[m]] = 0;
        If[a[[m - 1]] == 0,
            a[[--m]] = 1, j = m - 1; k = 2*n - 1;
            While[j > 1 && a[[j]] == 1, a[[j--]] = 0; a[[k]] = 1; k -= 2];
            If[j == 1, Break[]];
            a[[j]] = 1; m = 2*n - 1]
    ]][[2, 1]]];
Join[{{0}, {2}}, Array[alist, 4, 2]] (* Paolo Xausa, Mar 16 2024 *)
  • PARI
    isA014486(n)=my(v=binary(n),t=0);for(i=1,#v,t+=if(v[i],1,-1);if(t<0,return(0))); t==0 \\ Charles R Greathouse IV, Jun 10 2011
  • PARI
    a_rows(N) = my(a=Vec([[0]], N)); for(r=1, N-1, my(b=a[r], c=List()); foreach(b, t, my(v=if(t, valuation(t, 2), 0)); for(i=0, v, listput(~c, (t<<2)+(2<Ruud H.G. van Tol, May 16 2024
  • Python
    from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A014486_gen(): # generator of terms
    yield 0
    for l in count(1):
        for s in multiset_permutations('0'*l+'1'*(l-1)):
            c, m = 0, (l<<1)-1
            for i in range(m):
                if s[i] == '1':
                    c += 2
                if cA014486_list = list(islice(A014486_gen(),30)) # Chai Wah Wu, Nov 28 2023
  • SageMath
    def is_A014486(n) :
    B = bin(n)[2::] if n != 0 else 0
    s = 0
    for b in B :
        s += 1 if b=='1' else -1
        if 0 > s : return False
    return 0 == s
def A014486_list(n): return [k for k in (1..n) if is_A014486(k) ]
A014486_list(888) # Peter Luschny, Aug 10 2012

Extensions

Additional comments from Antti Karttunen, Aug 11 2000 and May 25 2004
Added a(0)=0 (which had been removed in June 2011), Joerg Arndt, Feb 27 2013

A014138 Partial sums of (Catalan numbers starting 1, 2, 5, ...).

Original entry on oeis.org

0, 1, 3, 8, 22, 64, 196, 625, 2055, 6917, 23713, 82499, 290511, 1033411, 3707851, 13402696, 48760366, 178405156, 656043856, 2423307046, 8987427466, 33453694486, 124936258126, 467995871776, 1757900019100
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of paths starting from the root in all ordered trees with n+1 edges (a path is a nonempty tree with no vertices of outdegree greater than 1). Example: a(2)=8 because the five trees with three edges have altogether 1+0+2+2+3=8 paths hanging from the roots. - Emeric Deutsch, Oct 20 2002
a(n) is the sum of the mean maximal pyramid size over all Dyck (n+1)-paths. Also, a(n) = sum of the mean maximal sawtooth size over all Dyck (n+1)-paths. A pyramid (resp. sawtooth) in a Dyck path is a subpath of the form U^k D^k (resp. (UD)^k) with k>=1 and k is its size. For example, the maximal pyramids in the Dyck path uUUDD|UD|UDdUUDD are indicated by uppercase letters (and separated by a vertical bar). Their sizes are 2,1,1,2 left to right and the mean maximal pyramid size of the path is 6/4 = 3/2. Also, the mean maximal sawtooth size of this path is (1+2+1)/3 = 4/3. - David Callan, Jun 07 2006
p^2 divides a(p-1) for prime p of form p=6k+1 (A002476(k)). - Alexander Adamchuk, Jul 03 2006
p^2 divides a(p^2-1) for prime p>3. p^2 divides a(p^3-1) for prime p=7,13,19,... prime p in the form p=6k+1. - Alexander Adamchuk, Jul 03 2006
Row sums of triangle A137614. - Gary W. Adamson, Jan 30 2008
Equals INVERTi transform of A095930: (1, 4, 15, 57, 220, 859, ...). - Gary W. Adamson, May 15 2009
a(n) < A000108(n+1), therefore A176137(n) <= 1. - Reinhard Zumkeller, Apr 10 2010
a(n) is also the sum of the numbers in Catalan's triangle (A009766) from row 0 to row n. - Patrick Labarque, Jul 27 2010
Equals the Catalan sequence starting (1, 1, 2, ...) convolved with A014137 starting (1, 2, 4, 9, ...). - Gary W. Adamson, May 20 2013
p divides a((p-3)/2) for primes {11,23,47,59,...} = A068231 primes congruent to 11 mod 12. - Alexander Adamchuk, Dec 27 2013
a(n) is the number of parking functions of size n avoiding the patterns 132, 213, and 231. - Lara Pudwell, Apr 10 2023

Links

Crossrefs

Cf. A000108, A002476, A005554, A068231, A095930, A137614, A155587.

Programs

  • Haskell
    a014138 n = a014138_list !! n
a014138_list = scanl1 (+) a000108_list  -- Reinhard Zumkeller, Mar 01 2013
  • Maple
    a:=n->sum((binomial(2*j,j)/(j+1)),j=1..n): seq(a(n), n=0..24); # Zerinvary Lajos, Dec 01 2006
# Second program:
A014138 := series(exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)*(3/2*int(BesselI(0, 2*x)*exp(x), x) - 1/2), x = 0, 26):
seq(n!*coeff(A014138, x, n), n = 0 .. 24); # Mélika Tebni, Aug 31 2024
  • Mathematica
    Table[Sum[(2k)!/k!/(k+1)!,{k,1,n}],{n,1,70}] (* Alexander Adamchuk, Jul 03 2006 *)
Join[{0},Accumulate[CatalanNumber[Range[30]]]] (* Harvey P. Dale, Jan 25 2013 *)
CoefficientList[Series[(1 - 2 x - (1 - 4 x)^(1/2))/(2 x (1 - x)), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 21 2015 *)
a[0] := 0; a[n_] := Sum[CatalanNumber[k], {k, 1, n}]; Table[a[n], {n,0,50}] (* G. C. Greubel, Jan 14 2017 *)
  • PARI
    Vec((1-2*x-(1-4*x)^(1/2))/(2*x*(1-x))) \\ Charles R Greathouse IV, Feb 11 2011
  • Python
    from _future_ import division
A014138_list, b, s = [0], 1, 0
for n in range(1,10**2):
    s += b
    A014138_list.append(s)
    b = b*(4*n+2)//(n+2) # Chai Wah Wu, Jan 28 2016

Formula

a(n) = A014137(n)-1.
G.f.: (1-2*x-sqrt(1-4x))/(2x(1-x)) = (C(x)-1)/(1-x) where C(x) is the generating function for the Catalan numbers. - Rocio Blanco, Apr 02 2007
a(n) = Sum_{k=1..n} A000108(k). - Alexander Adamchuk, Jul 03 2006
Binomial transform of A005554: (1, 2, 3, 6, 13, 30, 72, ...). - Gary W. Adamson, Nov 23 2007
D-finite with recurrence: (n+1)*a(n) + (1-5n)*a(n-1) + 2*(2n-1)*a(n-2) = 0. - R. J. Mathar, Dec 14 2011
Equals the Catalan sequence starting (1, 1, 2, ...) convolved with A014137 starting (1, 2, 4, 9, ...). - Gary W. Adamson, May 20 2013
G.f.: 1/x - G(0)/(1-x)/x, where G(k) = 1 - x/(1 - x/(1 - x/(1 - x/G(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Jul 17 2013
G.f.: 1/x - T(0)/(2*x*(1-x)), where T(k) = 2*x*(2*k+1)+ k+2 - 2*x*(k+2)*(2*k+3)/T(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 27 2013
a(n) ~ 2^(2*n+2)/(3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 10 2013
a(n) = Sum_{i+jA000108. - Yuchun Ji, Jan 10 2019
E.g.f.: exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)*(3/2*Integral_{x=-oo..oo} BesselI(0,2*x)*exp(x) dx - 1/2). - Mélika Tebni, Aug 31 2024

Extensions

Edited by Max Alekseyev, Sep 13 2009 (including adding an initial 0)
Definition edited by N. J. A. Sloane, Oct 03 2009

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

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..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

Examples

			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)

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.

Links

Crossrefs

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.

Programs

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

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=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

Extensions

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

A053121 Catalan triangle (with 0's) read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 2, 0, 3, 0, 1, 0, 5, 0, 4, 0, 1, 5, 0, 9, 0, 5, 0, 1, 0, 14, 0, 14, 0, 6, 0, 1, 14, 0, 28, 0, 20, 0, 7, 0, 1, 0, 42, 0, 48, 0, 27, 0, 8, 0, 1, 42, 0, 90, 0, 75, 0, 35, 0, 9, 0, 1, 0, 132, 0, 165, 0, 110, 0, 44, 0, 10, 0, 1, 132, 0, 297, 0, 275, 0, 154, 0, 54, 0, 11, 0
Offset: 0

Views

Author

Wolfdieter Lang

Keywords

Comments

Inverse lower triangular matrix of A049310(n,m) (coefficients of Chebyshev's S polynomials).
Walks with a wall: triangle of number of n-step walks from (0,0) to (n,m) where each step goes from (a,b) to (a+1,b+1) or (a+1,b-1) and the path stays in the nonnegative quadrant.
T(n,m) is the number of left factors of Dyck paths of length n ending at height m. Example: T(4,2)=3 because we have UDUU, UUDU, and UUUD, where U=(1,1) and D=(1,-1). (This is basically a different formulation of the previous - walks with a wall - property.) - Emeric Deutsch, Jun 16 2011
"The Catalan triangle is formed in the same manner as Pascal's triangle, except that no number may appear on the left of the vertical bar." [Conway and Smith]
G.f. for row polynomials p(n,x) := Sum_{m=0..n} (a(n,m)*x^m): c(z^2)/(1-x*z*c(z^2)). Row sums (x=1): A001405 (central binomial).
In the language of the Shapiro et al. reference such a lower triangular (ordinary) convolution array, considered as a matrix, belongs to the Bell-subgroup of the Riordan-group. The g.f. Ginv(x) of the m=0 column of the inverse of a given Bell-matrix (here A049310) is obtained from its g.f. of the m=0 column (here G(x)=1/(1+x^2)) by Ginv(x)=(f^{(-1)}(x))/x, with f(x) := x*G(x) and f^{(-1)}is the compositional inverse function of f (here one finds, with Ginv(0)=1, c(x^2)). See the Shapiro et al. reference.
Number of involutions of {1,2,...,n} that avoid the patterns 132 and have exactly k fixed points. Example: T(4,2)=3 because we have 2134, 4231 and 3214. Number of involutions of {1,2,...,n} that avoid the patterns 321 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. Number of involutions of {1,2,...,n} that avoid the patterns 213 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1432 and 4231. - Emeric Deutsch, Oct 12 2006
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. - Philippe Deléham, Sep 25 2007
Riordan array (c(x^2),xc(x^2)), where c(x) is the g.f. of Catalan numbers A000108. - Philippe Deléham, Nov 25 2007
A053121^2 = triangle A145973. Convolved with A001405 = triangle A153585. - Gary W. Adamson, Dec 28 2008
By columns without the zeros, n-th row = A000108 convolved with itself n times; equivalent to A = (1 + x + 2x^2 + 5x^3 + 14x^4 + ...), then n-th row = coefficients of A^(n+1). - Gary W. Adamson, May 13 2009
Triangle read by rows,product of A130595 and A064189 considered as infinite lower triangular arrays; A053121 = A130595*A064189 = B^(-1)*A097609*B where B = A007318. - Philippe Deléham, Dec 07 2009
From Mark Dols, Aug 17 2010: (Start)
As an upper right triangle, rows represent powers of 5-sqrt(24):
5 - sqrt(24)^1 = 0.101020514...
5 - sqrt(24)^2 = 0.010205144...
5 - sqrt(24)^3 = 0.001030928...
(Divided by sqrt(96) these powers give a decimal representation of the columns of A007318, with 1/sqrt(96) being the middle column.) (End)
T(n,k) is the number of dispersed Dyck paths of length n (i.e., Motzkin paths of length n with no (1,0) steps at positive heights) having k (1,0)-steps. Example: T(5,3)=4 because, denoting U=(1,1), D=(1,-1), H=(1,0), we have HHHUD, HHUDH, HUDHH, and UDHHH. - Emeric Deutsch, Jun 01 2011
Let S(N,x) denote the N-th Chebyshev S-polynomial in x (see A049310, cf. [W. Lang]). Then x^n = sum_{k=0..n} T(n,k)*S(k,x). - L. Edson Jeffery, Sep 06 2012
This triangle a(n,m) appears also in the (unreduced) formula for the powers rho(N)^n for the algebraic number over the rationals rho(N) = 2*cos(Pi/N) = R(N, 2), the smallest diagonal/side ratio R in the regular N-gon:
rho(N)^n = sum(a(n,m)*R(N,m+1),m=0..n), n>=0, identical in N >= 1. R(N,j) = S(j-1, x=rho(N)) (Chebyshev S (A049310)). See a comment on this under A039599 (even powers) and A039598 (odd powers). Proof: see the Sep 06 2012 comment by L. Edson Jeffery, which follows from T(n,k) (called here a(n,k)) being the inverse of the Riordan triangle A049310. - Wolfdieter Lang, Sep 21 2013
The so-called A-sequence for this Riordan triangle of the Bell type (c(x^2), x*c(x^2)) (see comments above) is A(x) = 1 + x^2. This proves the recurrence given in the formula section by Henry Bottomley for a(n, m) = a(n-1, m-1) + a(n-1, m+1) for n>=1 and m>=1, with inputs. The Z-sequence for this Riordan triangle is Z(x) = x which proves the recurrence a(n,0) = a(n-1,1), n>=1, a(0,0) = 1. For A- and Z-sequences for Riordan triangles see the W. Lang link under A006232. - Wolfdieter Lang, Sep 22 2013
Rows of the triangle describe decompositions of tensor powers of the standard (2-dimensional) representation of the Lie algebra sl(2) into irreducibles. Thus a(n,m) is the multiplicity of the m-th ((m+1)-dimensional) irreducible representation in the n-th tensor power of the standard one. - Mamuka Jibladze, May 26 2015
The Riordan row polynomials p(n, x) belong to the Boas-Buck class (see a comment and references in A046521), hence they satisfy the Boas-Buck identity: (E_x - n*1)*p(n, x) = (E_x + 1)*Sum_{j=0..n-1} (1/2)*(1 - (-1)^j)*binomial(j+1, (j+1)/2)*p(n-1-j, x), for n >= 0, where E_x = x*d/dx (Euler operator). For the triangle a(n, m) this entails a recurrence for the sequence of column m, given in the formula section. - Wolfdieter Lang, Aug 11 2017
From Roger Ford, Jan 22 2018: (Start)
For row n, the nonzero values represent the odd components (loops) formed by n+1 nonintersecting arches above and below the x-axis with the following constraints: The top has floor((n+3)/2) starting arches at position 1 and the next consecutive odd positions. All other starting top arches are in even positions. The bottom arches are a rainbow of arches. If the component=1 then the arch configuration is a semimeander solution.
Examples: For row 3 {0, 2, 0, 1} there are 3 arch configurations: 2 arch configurations have a component=1; 1 has a component=3. c=components, U=top arch starting in odd position, u=top arch starting in an even position, d=ending top arch:
.
top UuUdUddd c=3 top UdUuUddd c=1 top UdUdUudd c=1
/\ /\
//\\ / \
// \\ / /\ \ /\
// \\ / / \ \ / \
///\ /\\\ /\ / / /\ \ \ /\ /\ / /\ \
\\\ \/ /// \ \ \ \/ / / / \ \ \ \/ / / /
\\\ /// \ \ \ / / / \ \ \ / / /
\\\/// \ \ \/ / / \ \ \/ / /
\\// \ \ / / \ \ / /
\/ \ \/ / \ \/ /
\ / \ /
\/ \/
For row 4 {2, 0, 3, 0, 1} there are 6 arch configurations: 2 have a component=1; 3 have a component=3: 1 has a component=1. (End)

Examples

			Triangle a(n,m) begins:
  n\m  0   1   2   3   4   5   6  7  8  9 10 ...
  0:   1
  1:   0   1
  2:   1   0   1
  3:   0   2   0   1
  4:   2   0   3   0   1
  5:   0   5   0   4   0   1
  6:   5   0   9   0   5   0   1
  7:   0  14   0  14   0   6   0  1
  8:  14   0  28   0  20   0   7  0  1
  9:   0  42   0  48   0  27   0  8  0  1
  10: 42   0  90   0  75   0  35  0  9  0  1
  ... (Reformatted by _Wolfdieter Lang_, Sep 20 2013)
E.g., the fourth row corresponds to the polynomial p(3,x)= 2*x + x^3.
From _Paul Barry_, May 29 2009: (Start)
Production matrix is
  0, 1,
  1, 0, 1,
  0, 1, 0, 1,
  0, 0, 1, 0, 1,
  0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 0, 0, 0, 1, 0, 1 (End)
Boas-Buck recurrence for column k = 2, n = 6: a(6, 2) = (3/4)*(0 + 2*a(4 ,2) + 0 + 6*a(2, 2)) = (3/4)*(2*3 + 6) = 9. - _Wolfdieter Lang_, Aug 11 2017

References

  • J. H. Conway and D. A. Smith, On Quaternions and Octonions, A K Peters, Ltd., Natick, MA, 2003. See p. 60. MR1957212 (2004a:17002)
  • A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.

Links

Crossrefs

Cf. A008315, A049310, A000108, A001405 (row sums), A145973, A153585, A108786, A037952. Another version: A008313. A039598 and A039599 without zeros, and odd and even numbered rows.
Variant without zero-diagonals: A033184 and with rows reversed: A009766.

Programs

  • Haskell
    a053121 n k = a053121_tabl !! n !! k
a053121_row n = a053121_tabl !! n
a053121_tabl = iterate
   (\row -> zipWith (+) ([0] ++ row) (tail row ++ [0,0])) [1]
-- Reinhard Zumkeller, Feb 24 2012
  • Maple
    T:=proc(n,k): if n+k mod 2 = 0 then (k+1)*binomial(n+1,(n-k)/2)/(n+1) else 0 fi end: for n from 0 to 13 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form; Emeric Deutsch, Oct 12 2006
F:=proc(l,p) if ((l-p) mod 2) = 1 then 0 else (p+1)*l!/( ( (l-p)/2 )! * ( (l+p)/2 +1)! ); fi; end;
r:=n->[seq( F(n,p),p=0..n)]; [seq(r(n),n=0..15)]; # N. J. A. Sloane, Jan 29 2011
A053121 := proc(n,k) option remember; `if`(k>n or k<0,0,`if`(n=k,1,
procname(n-1,k-1)+procname(n-1,k+1))) end proc:
seq(print(seq(A053121(n,k), k=0..n)),n=0..12); # Peter Luschny, May 01 2011
  • Mathematica
    a[n_, m_] /; n < m || OddQ[n-m] = 0; a[n_, m_] = (m+1) Binomial[n+1, (n-m)/2]/(n+1); Flatten[Table[a[n, m], {n, 0, 12}, {m, 0, n}]] [[1 ;; 90]] (* Jean-François Alcover, May 18 2011 *)
T[0, 0] := 1; T[n_, k_]/;0<=k<=n := T[n, k] = T[n-1, k-1]+T[n-1, k+1]; T[n_, k_] := 0; Flatten@Table[T[n, k], {n, 0, 12}, {k, 0, n}] (* Oliver Seipel, Dec 31 2024 *)
  • PARI
    T(n, m)=if(nCharles R Greathouse IV, Mar 09 2016
  • Sage
    def A053121_triangle(dim):
    M = matrix(ZZ,dim,dim)
    for n in (0..dim-1): M[n,n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            M[n,k] = M[n-1,k-1] + M[n-1,k+1]
    return M
A053121_triangle(13) # Peter Luschny, Sep 19 2012

Formula

a(n, m) := 0 if n
a(n, m) = (4*(n-1)*a(n-2, m) + 2*(m+1)*a(n-1, m-1))/(n+m+2), a(n, m)=0 if n
G.f. for m-th column: c(x^2)*(x*c(x^2))^m, where c(x) = g.f. for Catalan numbers A000108.
G.f.: G(t,z) = c(z^2)/(1 - t*z*c(z^2)), where c(z) = (1 - sqrt(1-4*z))/(2*z) is the g.f. for the Catalan numbers (A000108). - Emeric Deutsch, Jun 16 2011
a(n, m) = a(n-1, m-1) + a(n-1, m+1) if n > 0 and m >= 0, a(0, 0)=1, a(0, m)=0 if m > 0, a(n, m)=0 if m < 0. - Henry Bottomley, Jan 25 2001
Sum_{k>=0} T(m,k)^2 = A000108(m). - Paul D. Hanna, Apr 23 2005
Sum_{k>=0} T(m, k)*T(n, k) = 0 if m+n is odd; Sum_{k>=0} T(m, k)*T(n, k) = A000108((m+n)/2) if m+n is even. - Philippe Deléham, May 26 2005
T(n,k)=sum{i=0..n, (-1)^(n-i)*C(n,i)*sum{j=0..i, C(i,j)*(C(i-j,j+k)-C(i-j,j+k+2))}}; Column k has e.g.f. BesselI(k,2x)-BesselI(k+2,2x). - Paul Barry, Feb 16 2006
Sum_{k=0..n} T(n,k)*(k+1) = 2^n. - Philippe Deléham, Mar 22 2007
Sum_{j>=0} T(n,j)*binomial(j,k) = A054336(n,k). - Philippe Deléham, Mar 30 2007
T(2*n+1,2*k+1) = A039598(n,k), T(2*n,2*k) = A039599(n,k). - Philippe Deléham, Apr 16 2007
Sum_{k=0..n} T(n,k)^x = A000027(n+1), A001405(n), A000108(n), A003161(n), A129123(n) for x = 0,1,2,3,4 respectively. - Philippe Deléham, Nov 22 2009
Sum_{k=0..n} T(n,k)*x^k = A126930(n), A126120(n), A001405(n), A054341(n), A126931(n) for x = -1, 0, 1, 2, 3 respectively. - Philippe Deléham, Nov 28 2009
Sum_{k=0..n} T(n,k)*A000045(k+1) = A098615(n). - Philippe Deléham, Feb 03 2012
Recurrence for row polynomials C(n, x) := Sum_{m=0..n} a(n, m)*x^m = x*Sum_{k=0..n} Chat(k)*C(n-1-k, x), n >= 0, with C(-1, 1/x) = 1/x and Chat(k) = A000108(k/2) if n is even and 0 otherwise. From the o.g.f. of the row polynomials: G(z; x) := Sum_{n >= 0} C(n, x)*z^n = c(z^2)*(1 + x*z*G(z, x)), with the o.g.f. c of A000108. - Ahmet Zahid KÜÇÜK and Wolfdieter Lang, Aug 23 2015
The Boas-Buck recurrence (see a comment above) for the sequence of column m is: a(n, m) = ((m+1)/(n-m))*Sum_{j=0..n-1-m} (1/2)*(1 - (-1)^j)*binomial(j+1, (j+1)/2)* a(n-1-j, k), for n > m >= 0 and input a(m, m) = 1. - Wolfdieter Lang, Aug 11 2017
Sum_{m=1..n} a(n,m) = A037952(n). - R. J. Mathar, Sep 23 2021

Extensions

Edited by N. J. A. Sloane, Jan 29 2011

A000245 a(n) = 3*(2*n)!/((n+2)!*(n-1)!).

Original entry on oeis.org

0, 1, 3, 9, 28, 90, 297, 1001, 3432, 11934, 41990, 149226, 534888, 1931540, 7020405, 25662825, 94287120, 347993910, 1289624490, 4796857230, 17902146600, 67016296620, 251577050010, 946844533674, 3572042254128, 13505406670700, 51166197843852, 194214400834356
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

This sequence represents the expected saturation of a binary search tree (or BST) on n nodes times the number of binary search trees on n nodes, or alternatively, the sum of the saturation of all binary search trees on n nodes. - Marko Riedel, Jan 24 2002
1->12, 2->123, 3->1234 etc. starting with 1, gives A007001: 1, 12, 12123, 12123121231234... summing the digits gives this sequence. - Miklos Kristof, Nov 05 2002
a(n-1) = number of n-th generation vertices in the tree of sequences with unit increase labeled by 2 (cf. Zoran Sunic reference). - Benoit Cloitre, Oct 07 2003
With offset 1, number of permutations beginning with 12 and avoiding 32-1.
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=1. - Herbert Kociemba, May 24 2004
a(n) is the number of Dyck (n+1)-paths that start with UU. For example, a(2)=3 counts UUUDDD, UUDUDD, UUDDUD. - David Callan, Dec 08 2004
a(n) is the number of Dyck (n+2)-paths that start with UUDU. For example, a(2)=3 counts UUDUDDUD, UUDUDUDD, UUDUUDDD. - David Scambler, Feb 14 2011
Hankel transform is (0,-1,-1,0,1,1,0,-1,-1,0,...). Hankel transform of a(n+1) is (1,0,-1,-1,0,1,1,0,-1,-1,0,...). - Paul Barry, Feb 08 2008
Starting with offset 1 = row sums of triangle A154558. - Gary W. Adamson, Jan 11 2009
Starting with offset 1 equals INVERT transform of A014137, partial sums of the Catalan numbers: (1, 2, 4, 9, 23, ...). - Gary W. Adamson, May 15 2009
With offset 1, a(n) is the binomial transform of the shortened Motzkin numbers: 1, 2, 4, 9, 21, 51, 127, 323, ... (A001006). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Sep 07 2009
The Catalan sequence convolved with its shifted variant, e.g. a(5) = 90 = (1, 1, 2, 5, 14) dot (42, 14, 5, 2, 1) = (42 + 14 + 10 + 10 + 14 ) = 90. - Gary W. Adamson, Nov 22 2011
a(n+2) = A214292(2*n+3,n). - Reinhard Zumkeller, Jul 12 2012
With offset 3, a(n) is the number of permutations on {1,2,...,n} that are 123-avoiding, i.e., do not contain a three term monotone subsequence, for which the first ascent is at positions (3,4); see Connolly link. There it is shown in general that the k-th Catalan Convolution is the number of 123-avoiding permutations for which the first ascent is at (k, k+1). (For n=k, the first ascent is defined to be at positions (k,k+1) if the permutation is the decreasing permutation with no ascents.) - Anant Godbole, Jan 17 2014
With offset 3, a(n)=number of permutations on {1,2,...,n} that are 123-avoiding and for which the integer n is in the 3rd spot; see Connolly link. For example, there are 297 123-avoiding permutations on n=9 at which the element 9 is in the third spot. - Anant Godbole, Jan 17 2014
With offset 1, a(n) is the number of North-East paths from (0,0) to (n+1,n+1) that bounce off y = x to the right exactly once but do not cross y = x vertically. Details can be found in Section 4.4 in Pan and Remmel's link. - Ran Pan, Feb 01 2016
The total number of returns (downsteps which end on the line y=0) within the set of all Dyck paths from (0,0) to (2n,0). - Cheyne Homberger, Sep 05 2016
a(n) is the number of intervals of the form [s,w] that are distributive (equivalently, modular) lattices in the weak order on S_n, for a fixed simple reflection s. - Bridget Tenner, Jan 16 2020
a(n+2) is the number of coalescent histories for a pair (G,S) where G is a gene tree with 3-pseudocaterpillar shape and n leaves, S is a species tree with caterpillar shape and n leaves, and G and S have identical leaf labeling. - Noah A Rosenberg, Jun 15 2022
a(n) is the number of parking functions of size n avoiding the patterns 132, 213, and 312. - Lara Pudwell, Apr 10 2023
a(n) is the number of parking functions of size n avoiding the patterns 123 and 213. - Lara Pudwell, Apr 10 2023

References

  • Pierre de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 11, coefficients of P_3(z).
  • Ki Hang Kim, Douglas G. Rogers and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013)
  • C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., Vol. 14 (1922), pp. 55-62, 122-138 and 143-146.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

First differences of Catalan numbers A000108.
T(n, n+3) for n=0, 1, 2, ..., array T as in A047072.
Cf. A099364.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A002057, A000344, A003517, A000588, A003518, A003519, A001392, A001622.
Cf. A154558, A014137.
Column k=1 of A067323.

Programs

  • GAP
    Concatenation([0],List([1..30],n->3*Factorial(2*n)/(Factorial(n+2)*Factorial(n-1)))); # Muniru A Asiru, Aug 09 2018
  • Magma
    [0] cat [3*Factorial(2*n)/(Factorial(n+2)*Factorial(n-1)): n in [1..30]]; // Vincenzo Librandi, Feb 15 2016
  • Maple
    A000245 := n -> 3*binomial(2*n, n-1)/(n+2);
seq(A000245(n), n=0..27);
  • Mathematica
    Table[3(2n)!/((n+2)!(n-1)!),{n,0,30}] (* or *) Table[3*Binomial[2n,n-1]/(n+2),{n,0,30}] (* or *) Differences[CatalanNumber[Range[0,31]]] (* Harvey P. Dale, Jul 13 2011 *)
  • PARI
    a(n)=if(n<1,0,3*(2*n)!/(n+2)!/(n-1)!)
  • Sage
    [catalan_number(i+1) - catalan_number(i) for i in range(28)] # Zerinvary Lajos, May 17 2009
  • Sage
    def A000245_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = False; h = 1; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1; R.append(D[2])
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b
    return R
A000245_list(29) # Peter Luschny, Jun 03 2012

Formula

a(n) = A000108(n+1) - A000108(n).
G.f.: x*(c(x))^3 = (-1+(1-x)*c(x))/x, c(x) = g.f. for Catalan numbers. Also a(n) = 3*n*Catalan(n)/(n+2). - Wolfdieter Lang
For n > 1, a(n) = 3a(n-1) + Sum[a(k)*a(n-k-2), k=1,...,n-3]. - John W. Layman, Dec 13 2002; proved by Michael Somos, Jul 05 2003
G.f. is A(x) = C(x)*(1-x)/x-1/x = x(1+x*C(x)^2)*C(x)^2 where C(x) is g.f. for Catalan numbers, A000108.
G.f. satisfies x^2*A(x)^2 + (3*x-1)*A(x) + x = 0.
Series reversion of g.f. A(x) is -A(-x). - Michael Somos, Jan 21 2004
a(n+1) = Sum_{i+j+k=n} C(i)C(j)C(k) with i, j, k >= 0 and where C(k) denotes the k-th Catalan number. - Benoit Cloitre, Nov 09 2003
An inverse Chebyshev transform of x^2. - Paul Barry, Oct 13 2004
The sequence is 0, 0, 1, 0, 3, 0, 9, 0, ... with zeros restored. Second binomial transform of (-1)^n*A005322(n). The g.f. is transformed to x^2 under the Chebyshev transformation A(x)->(1/(1+x^2))A(x/(1+x^2)). For a sequence b(n), this corresponds to taking Sum_{k=0..floor(n/2)} C(n-k, k)(-1)^k*b(n-2k), or Sum_{k=0..n} C((n+k)/2, k)*b(k)*(-1)^((n-k)/2)*(1+(-1)^(n-k))/2. - Paul Barry, Oct 13 2004
G.f.: (c(x^2)*(1-x^2)-1)/x^2, c(x) the g.f. of A000108; a(n) = Sum_{k=0..n} (k+1)*C(n, (n-k)/2)*(-1)^k*(C(2,k)-2*C(1,k)+C(0, k))*(1+(-1)^(n-k))/(n+k+2). - Paul Barry, Oct 13 2004
a(n) = Sum_{k=0..n} binomial(n,k)*2^(n-k)*(-1)^(k+1)*binomial(k, floor((k-1)/2)). - Paul Barry, Feb 16 2006
E.g.f.: exp(2*x)*(Bessel_I(1,2x) - Bessel_I(2,2*x)). - Paul Barry, Jun 04 2007
a(n) = (1/Pi)*Integral_{x=0..4} x^n*(x-1)*sqrt(x*(4-x))/(2*x). - Paul Barry, Feb 08 2008
D-finite with recurrence: For n > 1, a(n+1) = 2*(2n+1)*(n+1)*a(n)/((n+3)*n). - Sean A. Irvine, Dec 09 2009
Let A be the Toeplitz matrix of order n defined by: A[i,i-1]=-1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n >= 2, a(n-1) = (-1)^(n-2)*coeff(charpoly(A,x),x^2). - Milan Janjic, Jul 08 2010
a(n) = sum of top row terms of M^(n-1), M = an infinite square production matrix as follows:
2, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011
E.g.f.: exp(2*x)*(BesselI(2,2*x)) = Q(0) - 1 where Q(k) = 1 - 2*x/(k + 1 - 3*((k+1)^2)/((k^2) + 8*k + 9 - (k+2)*((k+3)^2)*(2*k+3)/((k+3)*(2*k+3) - 3*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Dec 05 2011
a(n) = -binomial(2*n,n)/(n+1)*hypergeom([-1,n+1/2],[n+2],4). - Peter Luschny, Aug 15 2012
a(n) = Sum_{i=0..n-1} C(i)*C(n-i), where C(i) denotes the i-th Catalan number. - Dmitry Kruchinin, Mar 02 2013
a(n) = binomial(2*n-1, n) - binomial(2*n-1, n-3). - Johannes W. Meijer, Jul 31 2013
a(n) ~ 3*4^n/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Feb 26 2016
a(n) = ((-1)^n/(n+1))*Sum_{i=0..n-1} (-1)^(i+1)*(n+1-i)*binomial(2*n+2,i), n>=0. - Taras Goy, Aug 09 2018
From Amiram Eldar, Jan 02 2022: (Start)
Sum_{n>=1} 1/a(n) = 14*Pi/(27*sqrt(3)) + 5/9.
Sum_{n>=1} (-1)^(n+1)/a(n) = 164*log(phi)/(75*sqrt(5)) + 7/25, where phi is the golden ratio (A001622). (End)
a(n) = 3*Sum_{k = 0..n-2} (-1)^k * binomial(2*n-k-1, n+1)*binomial(n+1, k)/(k + 1) for n >= 2. - Peter Bala, Sep 02 2024
a(n) = (3*n/(n+2))*A000108(n). - Taras Goy, Dec 20 2024

Extensions

I changed the description and added an initial 0, to make this coincide with the first differences of the Catalan numbers A000108. Some of the other lines will need to be changed as a result. - N. J. A. Sloane, Oct 31 2003

A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n nodes having root of even degree.

Original entry on oeis.org

0, 1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, 1174281, 4260282, 15548694, 57048048, 210295326, 778483932, 2892818244, 10786724388, 40347919626, 151355847012, 569274150156, 2146336125648, 8110508473252, 30711521221376
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Row-sum of signed Catalan triangle A009766. - Wouter Meeussen
There are two schools of thought about the best indexing for these numbers. Deutsch and Shapiro have a(4) = 6 whereas here a(5) = 6. The formulas given here use both labelings.
From D. G. Rogers, Oct 18 2005: (Start)
I notice that you have some other zero-one evaluations of binary bracketings (such as A055395). But if you have an operation # with 0#0 = 1#0 = 1, 0#1 = 1#1 = 0, and look at the number of bracketings of a string of n 0's that come out 0, you get another instance of the Fine numbers.
For Z = 1 + x(ZW + WW) = 1 + x CW and W = x(ZZ + ZW) = xZC. Hence Z = 1 + xxCCZ, the functional equational for the g.f. of the Fine numbers. Indeed, C = Z + W = Z + xCZ.
In terms of rooted planar trees with root of even degree, this says that of all rooted planar trees, some have root of even degree (Z) and some have root of odd degree (xCZ). (End)
Hankel transform of a(n+1) = [1,0,1,2,6,18,57,186,...] is A000012 = [1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
Starting with offset 3 = iterates of M * [1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] as the main diagonal and [1,1,1,...] as the super and subdiagonals. - Gary W. Adamson, Jan 09 2009
Starting with 1 and convolved with A068875 = the Catalan numbers with offset 1. - Gary W. Adamson, May 01 2009
For a relation to non-crossing partitions of the root system A_n, see A100754. - Tom Copeland, Oct 19 2014
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x) = [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)] = (x-2x^2)/(1-x)^2, and Fin(Cinv(x)) = P(x).
Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).
Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].
(End)
a(n+1) is the number of Dyck paths of semilength n avoiding UD at Level 0. For n = 3 the a(4) = 2 such Dyck paths are UUUDDD and UUDUDD. - Ran Pan, Sep 23 2015
For n >= 3, a(n) is the number of permutations pi of [n-2] such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - Colin Defant, Sep 16 2018
Named after the American scientist Terrence Leon Fine (1939-2021). - Amiram Eldar, Jun 08 2021

Examples

			G.f. = x + x^3 + 2*x^4 + 6*x^5 + 18*x^6 + 57*x^7 + 186*x^8 + 622*x^9 + 2120*x^10 + ...

References

  • Emeric Deutsch and Louis W. Shapiro, Seventeen Catalan identities, Bull. Instit. Combin. Applic., Vol. 31 (2001), pp. 31-38.
  • Ki Hang Kim, Douglas G. Rogers and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013). - N. J. A. Sloane, Jun 05 2012
  • Louis W. Shapiro and Carol J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

A column of A065600.
Sequence with signs: A064310.
Bisections: A138413, A138414.
Logarithmic derivative: A072547.
Cf. A068875, A000108, A000045, A005043, A057078, A007317, A091867, A104597.
Cf. A000012, A009766, A039598, A055395, A064306, A100754, A126093.

Programs

  • Haskell
    a000957 n = a000957_list !! n
a000957_list = 0 : 1 :
   (map (`div` 2) $ tail $ zipWith (-) a000108_list a000957_list)
-- Reinhard Zumkeller, Nov 12 2011
  • Magma
    [0,1] cat  [n le 1 select n-1 else (Catalan(n)-Self(n-1))/2: n in [1..30]]; // Vincenzo Librandi, Nov 17 2016
  • Maple
    t1 := (1-sqrt(1-4*x))/(3-sqrt(1-4*x)); t2 := series(t1,x,90); A000957 := n- coeff(t2,x,n);
A000957 := proc(n): if n = 0 then 0 else add((-1)^(n+k-1)*binomial(n+k-1, n-1)*(n-k)/n, k=0..n-1) fi: end: seq(A000957(n), n=0..28); # Johannes W. Meijer, Jul 22 2013
# third Maple program:
a:= proc(n) option remember; `if`(n<3, n*(2-n),
      ((7*n-12)*a(n-1)+(4*n-6)*a(n-2))/(2*n))
    end:
seq(a(n), n=0..32);  # Alois P. Heinz, Apr 23 2020
  • Mathematica
    Table[ Plus@@Table[ (-1)^(m+n) (n+m)!/n!/m! (n-m+1)/(n+1), {m, 0, n} ], {n, 0, 36} ] (* Wouter Meeussen *)
a[0] = 0; a[n_] := (1/2)*(-3*(-1/2)^n + 2^(n+1)*(2n-1)!!* Hypergeometric2F1Regularized[2, 2n+1, n+2, -1]); (* Jean-François Alcover, Feb 22 2012 *)
Table[2^n (n-2) (2n-1)!! (3 (n-1) Hypergeometric2F1[1, 3-n, 3+n, 2] - n - 2)/(n+2)! + KroneckerDelta[n], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)
  • Maxima
    C(n):=binomial(2*n,n)/(n+1);
a(n):=if n<=0 then 0 else if n=1 then 1 else  sum(C(n-i-1)*(a(i)+a(i-1)),i,2,n-1);
/* Vladimir Kruchinin, Apr 23 2020 */
  • PARI
    {a(n) = if( n<1, 0, polcoeff( 1 / (1 + 2 / (1 - sqrt(1 - 4*x + x*O(x^n)))), n))}; /* Michael Somos, Sep 17 2006 */
  • PARI
    {a(n) = if( n<1, 0, polcoeff( 1 / (1 + 1 / serreverse(x - x^2 + x*O(x^n))), n))}; /* Michael Somos, Sep 30 2006 */
  • Python
    from itertools import count, islice
def A000957_gen(): # generator of terms
    yield from (0,1,0)
    a, c = 0, 1
    for n in count(1):
        yield (a:=(c:=c*((n<<2)+2)//(n+2))-a>>1)
A000957_list = list(islice(A000957_gen(),20)) # Chai Wah Wu, Apr 26 2023
  • Sage
    def Fine():
    f, c, n = 1, 1, 1
    yield 0
    while True:
        yield f
        n += 1
        c = c * (4*n - 6) // n
        f = (c - f) // 2
a = Fine()
print([next(a) for  in range(29)])  # _Peter Luschny, Nov 30 2016

Formula

Catalan(n) = 2*a(n+1) + a(n), n >= 1. [Corrected by Pontus von Brömssen, Jul 23 2022]
a(n) = (A064306(n-1) + (-1)^(n-1))/2^n, n >= 1.
G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x)) (compare g.f. for Catalan numbers, A000108). - Emeric Deutsch
a(n) ~ 4^n/(9*n*sqrt(n*Pi)). (Corrected by Peter Luschny, Oct 26 2015.)
a(n) = (2/(n-1))*Sum_{j=0..n-3}(-2)^j*(j+1)*binomial(2n-1, n-3-j), n>=2. - Emeric Deutsch, Dec 26 2003
a(n) = 3*Sum_{j=0..floor((n-1)/2)} binomial(2n-2j-2, n-1) - binomial(2n, n) for n>0. - Emeric Deutsch, Jan 28 2004
Reversion of g.f. (x-2x^2)/(1-x)^2. - Ralf Stephan, Mar 22 2004
a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, C(1/2, k)8^k})+0^n; a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, (-1)^(k-1)*2^k*(2k)!/((k!)^2*(2k-1))})+0^n. - Paul Barry, Jun 10 2005
Hankel determinant transform is 1-n. - Michael Somos, Sep 17 2006
a(n+1) = A126093(n,0). - Philippe Deléham, Mar 05 2007
a(n+1) has g.f. 1/(1-0*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(..... (continued fraction). - Paul Barry, Dec 02 2008
From Paul Barry, Jan 17 2009: (Start)
G.f.: x*c(x)/(1+x*c(x)), c(x) the g.f. of A000108;
a(n+1) = Sum_{k=0..n} (-1)^k*C(2n-k,n-k)*(k+1)/(n+1). (End)
a(n) = 3*(-1/2)^(n+1) + Gamma(n+1/2)*4^n*hypergeom([1, n+1/2],[n+2],-8) /(sqrt(Pi)*(n+1)!) (for n>0). - Mark van Hoeij, Nov 11 2009
Let A be the Toeplitz matrix of order n defined by: A[i,i-1] = -1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n>=1, a(n+1) = (-1)^n*charpoly(A,1). - Milan Janjic, Jul 08 2010
a(n) = the upper left term in M^n, n>0; where M = the infinite square production matrix:
0, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011
a(n+1) = Sum_{k=0..n} A039598(n,k)*(-2)^k. - Philippe Deléham, Nov 04 2011
D-finite with recurrence: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - R. J. Mathar, Nov 15 2011
a(n) = sum(sum(2^(s-2n-2k)*(n/n+2k)binomial(n+2k, k)*binomial(s-n-1, s-2n-2k), (k=0, ..., floor((s-2n)/2)), (n=1, ..., s) with s>=2. - José Luis Ramírez Ramírez, Mar 22 2012
0 = a(n)*(16*a(n+1) + 22*a(n+2) - 20*a(n+3)) + a(n+1)*(34*a(n+1) + 53*a(n+2) - 38*a(n+3)) + a(n+2)*(10*a(n+2) + 4*a(n+3)) for all n in Z if we extend by a(0)=-1, a(-n) = -3/4 * (-2)^n if n>0. - Michael Somos, Jan 31 2014 [Corrected by Pontus von Brömssen, Aug 04 2022]
G.f. A(x) satisfies x*A'(x)/A(x) = x + 2*x^3 + 6*x^4 + 22*x^5 + ..., the o.g.f. for A072547. - Peter Bala, Oct 01 2015
a(n) = 2^n*(n-2)*(2*n-1)!!*(3*(n-1)*hypergeom([1,3-n], [3+n], 2)-n-2)/(n+2)! + 0^n. - Vladimir Reshetnikov, Oct 25 2015
a(n) = binomial(2*n,n)*(hypergeom([1,(1-n)/2,1-n/2],[1-n,3/2-n],1)*3/(4-2/n)-1) for n>=2. - Peter Luschny, Oct 26 2015
O.g.f. A(x) satisfies 1 + A(x) = (1 + 3*Sum_{n >= 1} Catalan(n)*x^n)/(1 + 2*Sum_{n >= 1} Catalan(n)*x^n) = (1 + 2*Sum_{n >= 1} binomial(2*n,n)*x^n )/(1 + 3/2*Sum_{n >= 1} binomial(2*n,n)*x^n). - Peter Bala, Sep 01 2016
a(n) = Sum_{i=2..n-1} C(n-i-1)*(a(i)+a(i-1)), a(0)=0, a(1)=1, where C(n) = A000108(n). - Vladimir Kruchinin, Apr 23 2020

A002057 Fourth convolution of Catalan numbers: a(n) = 4*binomial(2*n+3,n)/(n+4).

Original entry on oeis.org

1, 4, 14, 48, 165, 572, 2002, 7072, 25194, 90440, 326876, 1188640, 4345965, 15967980, 58929450, 218349120, 811985790, 3029594040, 11338026180, 42550029600, 160094486370, 603784920024, 2282138106804, 8643460269248, 32798844771700, 124680849918352
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is sum of the (flattened) list obtained by the iteration of: replace each integer k with the list 0,...,k+1 on the starting value 0. Length of this list is Catalan(n) or A000108. - Wouter Meeussen, Nov 11 2001
a(n-2) is the number of n-th generation vertices in the tree of sequences with unit increase labeled by 3 (cf. Zoran Sunic reference). - Benoit Cloitre, Oct 07 2003
Number of standard tableaux of shape (n+2,n-1). - Emeric Deutsch, May 30 2004
a(n) = CatalanNumber(n+3) - 2*CatalanNumber(n+2). Proof. From its definition as a convolution of Catalan numbers, a(n) counts lists of 4 Dyck paths of total size (semilength) = n. Connect the 4 paths by 3 upsteps (U) and append 3 downsteps (D). This is a reversible procedure. So a(n) is also the number of Dyck (n+3)-paths that end DDD (D for downstep). Let C(n) denote CatalanNumber(n) (A000108). Since C(n+3) is the total number of Dyck (n+3)-paths and C(n+2) is the number that end UD, we have (*) C(n+3) - C(n+2) is the number of Dyck (n+3)-paths that end DD. Also, (**) C(n+2) is the number of Dyck (n+3)-paths that end UDD (change the last D in a Dyck (n+2)-path to UDD). Subtracting (**) from (*) yields a(n) = C(n+3) - 2C(n+2) as claimed. - David Callan, Nov 21 2006
Convolution square of the Catalan sequence without one of the initial "1"'s: (1 + 4x + 14x^2 + 48x^3 + ...) = (1/x^2) * square(x + 2x^2 + 5x^3 + 14x^4 + ...)
a(n) is the number of binary trees with n+3 internal nodes in which both subtrees of the root are nonempty. Cf. A068875 [Sedgewick and Flajolet]. - Geoffrey Critzer, Jan 05 2013
With offset 4, a(n) is the number of permutations on {1,2,...,n} that are 123-avoiding, i.e., do not contain a three-term monotone subsequence, for which the first ascent is at positions (4,5); for example, there are 48 123-avoiding permutations on n=7 for which the first ascent is at spots (4,5). See Connolly link. There it is shown in general that the k-th Catalan Convolution is the number of 123-avoiding permutations for which the first ascent is at (k, k+1). (For n=k, the first ascent is defined to be at positions (k,k+1) if the permutation is the decreasing permutation with no ascents.) - Anant Godbole, Jan 17 2014
With offset 4, a(n) is the number of permutations on {1,2,...,n} that are 123-avoiding and for which the integer n is in the 4th spot; see Connolly link. - Anant Godbole, Jan 17 2014
a(n) is the number of North-East lattice paths from (0,0) to (n+2,n+2) that have exactly one east step below the subdiagonal y = x-1. Details can be found in Section 3.1 in Pan and Remmel's link. - Ran Pan, Feb 04 2016
a(n) is the number of North-East lattice paths from (0,0) to (n+2,n+2) that bounce off the diagonal y = x to the right exactly once but do not bounce off y = x to the left. Details can be found in Section 4.2 in Pan and Remmel's link. - Ran Pan, Feb 04 2016
a(n) is the number of North-East lattice paths from (0,0) to (n+2,n+2) that horizontally cross the diagonal y = x exactly once but do not cross the diagonal vertically. Details can be found in Section 4.3 in Pan and Remmel's link. - Ran Pan, Feb 04 2016
Apparently also Young tableaux of (non-partition) shape [n+1, 1, 1, n+1], see example file. - Joerg Arndt, Dec 30 2023

Examples

			From _Peter Bala_, Apr 14 2017: (Start)
This sequence appears on the main diagonal of a generalized Catalan triangle. Construct a lower triangular array (T(n,k)), n,k >= 0 by placing the sequence [0,0,0,1,1,1,1,...] in the first column and then filling in the remaining entries in the array using the rule T(n,k) = T(n,k-1) + T(n-1,k). The resulting array begins
  n\k| 0 1  2  3  4   5   6   7  ...
  ---+-------------------------------
   0 | 0
   1 | 0 0
   2 | 0 0  0
   3 | 1 1  1  1
   4 | 1 2  3  4  4
   5 | 1 3  6 10 14  14
   6 | 1 4 10 20 34  48  48
   7 | 1 5 15 35 69 117 165 165
   ...
(see Tedford 2011; this is essentially the array C_4(n,k) in the notation of Lee and Oh). Compare with A279004. (End)

References

  • Pierre de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 11, coefficients of P_4(z).
  • C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., Vol. 14 (1922), pp. 55-62, 122-138 and 143-146.
  • Robert Sedgewick and Phillipe Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 225.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

T(n, n+4) for n=0, 1, 2, ..., array T as in A047072. Also a diagonal of A059365 and of A009766.
Cf. A001003.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A000108, A000245, A000344, A003517, A000588, A003518, A003519, A001392, A001622.
Cf. A145596 (row sums), A279004.

Programs

  • GAP
    List([0..25],n->4*Binomial(2*n+3,n)/(n+4)); # Muniru A Asiru, Mar 05 2018
  • Magma
    [4*Binomial(2*n+3,n)/(n+4): n in [0..30]]; // Vincenzo Librandi, Feb 04 2016
  • Maple
    a := n -> 32*4^n*GAMMA(5/2+n)*(1+n)/(sqrt(Pi)*GAMMA(5+n)):
seq(a(n),n=0..23); # Peter Luschny, Dec 14 2015
A002057List := proc(m) local A, P, n; A := [1]; P := [1,1,1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-1]]);
A := [op(A), P[-1]] od; A end: A002057List(27); # Peter Luschny, Mar 26 2022
  • Mathematica
    Table[Plus@@Flatten[Nest[ #/.a_Integer:> Range[0, a+1]&, {0}, n]], {n, 0, 10}]
Table[4 Binomial[2n+3,n]/(n+4),{n,0,30}] (* or *) CoefficientList[ Series[ (1-Sqrt[1-4 x]+2 x (-2+Sqrt[1-4 x]+x))/(2 x^4),{x,0,30}],x] (* Harvey P. Dale, May 05 2011 *)
  • PARI
    {a(n) = if( n<0, 0, n+=2; 2*binomial(2*n, n-2) / n)}; /* Michael Somos, Jul 31 2005 */
  • PARI
    x='x+O('x^100); Vec((1-(1-4*x)^(1/2)+2*x*(-2+(1-4*x)^(1/2)+x))/(2*x^4)) \\ Altug Alkan, Dec 14 2015
  • SageMath
    [2*(n+1)*catalan_number(n+2)/(n+4) for n in (0..30)] # G. C. Greubel, May 27 2022

Formula

a(n) = A033184(n+4, 4) = 4*binomial(2*n+3, n)/(n+4) = 2*(n+1)*A000108(n+2)/(n+4).
G.f.: c(x)^4 with c(x) g.f. of A000108 (Catalan).
Row sums of A145596. Column 4 of A033184. By specializing the identities for the row polynomials given in A145596 we obtain the results a(n) = Sum_{k = 0..n} (-1)^k*binomial(n+1,k+1)*a(k)*4^(n-k) and a(n) = Sum_{k = 0..floor(n/2)} binomial(n+1,2*k+1) * Catalan(k+1) * 2^(n-2*k). From the latter identity we can derive the congruences a(2n+1) == 0 (mod 4) and a(2n) == Catalan(n+1) (mod 4). It follows that a(n) is odd if and only if n = (2^m - 4) for some m >= 2. - Peter Bala, Oct 14 2008
Let A be the Toeplitz matrix of order n defined by: A[i,i-1]=-1, A[i,j]=Catalan(j-i), (i<=j), and A[i,j]=0, otherwise. Then, for n>=3, a(n-3) = (-1)^(n-3) * coeff(charpoly(A,x), x^3). - Milan Janjic, Jul 08 2010
G.f.: (1-sqrt(1-4*x) + 2*x*(-2+sqrt(1-4*x) + x))/(2*x^4). - Harvey P. Dale, May 05 2011
a(n+1) = A214292(2*n+4,n). - Reinhard Zumkeller, Jul 12 2012
D-finite with recurrence: (n+4)a(n) = 8*(2*n-1)*a(n-3) - 20*(n+1)*a(n-2) + 4*(2*n+5)*a(n-1). - Fung Lam, Jan 29 2014
D-finite with recurrence: (n+4)*a(n) - 2*(3*n+7)*a(n-1) + 4*(2*n+1)*a(n-2) = 0. - R. J. Mathar, Jun 03 2014
Asymptotics: a(n) ~ 4^(n+3)/sqrt(4*Pi*n^3). - Fung Lam, Mar 31 2014
a(n) = 32*4^n*Gamma(5/2+n)*(1+n)/(sqrt(Pi)*Gamma(5+n)). - Peter Luschny, Dec 14 2015
a(n) = C(n+1) - 2*C(n) where C is Catalan number A000108. Yuchun Ji, Oct 18 2017 [Note: Offset is off by 2]
E.g.f.: d/dx ( 2*exp(2*x)*BesselI(2,2*x)/x ). - Ilya Gutkovskiy, Nov 01 2017
From Bradley Klee, Mar 05 2018: (Start)
With F(x) = 16/(1+sqrt(1-4*x))^4 g.f. of A002057, xi(x) = F(x/4)*(x/4)^2, K(16*x) = 2F1(1/2,1/2;1;16*x) g.f. of A002894, q(x) g.f. of A005797, and q'(x) g.f. of A274344:
K(x) = (1+sqrt(xi(x)))*K(xi(x)).
2*K(1-x) = (1+sqrt(xi(x)))*K(1-xi(x)).
q(x) = sqrt(q(xi(16*x)/16)) = q'(xi(16*x)/16)/sqrt(xi(16*x)/16). (End)
From Amiram Eldar, Jan 02 2022: (Start)
Sum_{n>=0} 1/a(n) = 5/4 + Pi/(18*sqrt(3)).
Sum_{n>=0} (-1)^n/a(n) = 183*log(phi)/(25*sqrt(5)) - 77/100, where phi is the golden ratio (A001622). (End)
a(n) = Integral_{x=0..4} x^n*W(x) dx where W(x) = -x^(3/2)*(1 - x/2)*sqrt(4 - x)/Pi, defined on the open interval (0,4). - Karol A. Penson, Nov 13 2022

A039598 Triangle formed from odd-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x). Sometimes called Catalan's triangle.

Original entry on oeis.org

1, 2, 1, 5, 4, 1, 14, 14, 6, 1, 42, 48, 27, 8, 1, 132, 165, 110, 44, 10, 1, 429, 572, 429, 208, 65, 12, 1, 1430, 2002, 1638, 910, 350, 90, 14, 1, 4862, 7072, 6188, 3808, 1700, 544, 119, 16, 1, 16796, 25194, 23256, 15504, 7752, 2907, 798, 152, 18, 1
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

T(n,k) is the number of leaves at level k+1 in all ordered trees with n+1 edges. - Emeric Deutsch, Jan 15 2005
Riordan array ((1-2x-sqrt(1-4x))/(2x^2),(1-2x-sqrt(1-4x))/(2x)). Inverse array is A053122. - Paul Barry, Mar 17 2005
T(n,k) is the number of walks of n steps, each in direction N, S, W, or E, starting at the origin, remaining in the upper half-plane and ending at height k (see the R. K. Guy reference, p. 5). Example: T(3,2)=6 because we have ENN, WNN, NEN, NWN, NNE and NNW. - Emeric Deutsch, Apr 15 2005
Triangle T(n,k), 0<=k<=n, read by rows given by T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0) = 2*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 2*T(n-1,k) + T(n-1,k+1) for k>=1. - Philippe Deléham, Mar 30 2007
Number of (2n+1)-step walks from (0,0) to (2n+1,2k+1) and consisting of steps u=(1,1) and d=(1,-1) in which the path stays in the nonnegative quadrant. Examples: T(2,0)=5 because we have uuudd, uudud, uuddu, uduud, ududu; T(2,1)=4 because we have uuuud, uuudu, uuduu, uduuu; T(2,2)=1 because we have uuuuu. - Philippe Deléham, Apr 16 2007, Apr 18 2007
Triangle read by rows: T(n,k)=number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and two types of steps H=(1,0); example: T(3,1)=14 because we have UDU, UUD, 4 HHU paths, 4 HUH paths and 4 UHH paths. - Philippe Deléham, Sep 25 2007
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. - Philippe Deléham, Sep 25 2007
With offset [1,1] this is the (ordinary) convolution triangle a(n,m) with o.g.f. of column m given by (c(x)-1)^m, where c(x) is the o.g.f. for Catalan numbers A000108. See the Riordan comment by Paul Barry.
T(n, k) is also the number of order-preserving full transformations (of an n-chain) with exactly k fixed points. - Abdullahi Umar, Oct 02 2008
T(n,k)/2^(2n+1) = coefficients of the maximally flat lowpass digital differentiator of the order N=2n+3. - Pavel Holoborodko (pavel(AT)holoborodko.com), Dec 19 2008
The signed triangle S(n,k) := (-1)^(n-k)*T(n,k) provides the transformation matrix between f(n,l) := L(2*l)*5^n*F(2*l)^(2*n+1) (F=Fibonacci numbers A000045, L=Lucas numbers A000032) and F(4*l*(k+1)), k = 0, ..., n, for each l>=0: f(n,l) = Sum_{k=0..n} S(n,k)*F(4*l*(k+1)), n>=0, l>=0. Proof: the o.g.f. of the l.h.s., G(l;x) := Sum_{n>=0} f(n,l)*x^n = F(4*l)/(1 - 5*F(2*l)^2*x) is shown to match the o.g.f. of the r.h.s.: after an interchange of the n- and k-summation, the Riordan property of S = (C(x)/x,C(x)) (compare with the above comments by Paul Barry), with C(x) := 1 - c(-x), with the o.g.f. c(x) of A000108 (Catalan numbers), is used, to obtain, after an index shift, first Sum_{k>=0} F(4*l*(k))*GS(k;x), with the o.g.f of column k of triangle S which is GS(k;x) := Sum_{n>=k} S(n,k)*x^n = C(x)^(k+1)/x. The result is GF(l;C(x))/x with the o.g.f. GF(l,x) := Sum_{k>=0} F(4*l*k)*x^k = x*F(4*l)/(1-L(4*l)*x+x^2) (see a comment on A049670, and A028412). If one uses then the identity L(4*n) - 5*F(2*n)^2 = 2 (in Koshy's book [reference under A065563] this is No. 15, p. 88, attributed to Lucas, 1876), the proof that one recovers the o.g.f. of the l.h.s. from above boils down to a trivial identity on the Catalan o.g.f., namely 1/c^2(-x) = 1 + 2*x - (x*c(-x))^2. - Wolfdieter Lang, Aug 27 2012
O.g.f. for row polynomials R(x) := Sum_{k=0..n} a(n,k)*x^k:
((1+x) - C(z))/(x - (1+x)^2*z) with C the o.g.f. of A000108 (Catalan numbers). From Riordan ((C(x)-1)/x,C(x)-1), compare with a Paul Barry comment above. This coincides with the o.g.f. given by Emeric Deutsch in the formula section. - Wolfdieter Lang, Nov 13 2012
The A-sequence for this Riordan triangle is [1,2,1] and the Z-sequence is [2,1]. See a W. Lang link under A006232 with details and references. - Wolfdieter Lang, Nov 13 2012
From Wolfdieter Lang, Sep 20 2013: (Start)
T(n, k) = A053121(2*n+1, 2*k+1). T(n, k) appears in the formula for the (2*n+1)-th power of the algebraic number rho(N) := 2*cos(Pi/N) = R(N, 2) in terms of the even-indexed diagonal/side length ratios R(N, 2*(k+1)) = S(2*k+1, 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+1) = 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 even powers of rho(n) see A039599. (End)
The tridiagonal Toeplitz production matrix P in the Example section corresponds to the unsigned Cartan matrix for the simple Lie algebra A_n as n tends to infinity (cf. Damianou ref. in A053122). - Tom Copeland, Dec 11 2015 (revised Dec 28 2015)
T(n,k) is the number of pairs of non-intersecting walks of n steps, each in direction N or E, starting at the origin, and such that the end points of the two paths are separated by a horizontal distance of k. See Shapiro 1976. - Peter Bala, Apr 12 2017
Also the convolution triangle of the Catalan numbers A000108. - Peter Luschny, Oct 07 2022

Examples

			Triangle T(n,k) starts:
n\k     0      1      2      3      4     5    6    7   8  9 10
0:      1
1:      2      1
2:      5      4      1
3:     14     14      6      1
4:     42     48     27      8      1
5:    132    165    110     44     10     1
6:    429    572    429    208     65    12    1
7:   1430   2002   1638    910    350    90   14    1
8:   4862   7072   6188   3808   1700   544  119   16   1
9:  16796  25194  23256  15504   7752  2907  798  152  18  1
10: 58786  90440  87210  62016  33915 14364 4655 1120 189 20  1
... Reformatted and extended by _Wolfdieter Lang_, Nov 13 2012.
Production matrix begins:
2, 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
0, 0, 0, 0, 0, 0, 1, 2, 1
- _Philippe Deléham_, Nov 07 2011
From _Wolfdieter Lang_, Nov 13 2012: (Start)
Recurrence: T(5,1) = 165 = 1*42 + 2*48 +1*27. The Riordan A-sequence is [1,2,1].
Recurrence from Riordan Z-sequence [2,1]: T(5,0) = 132 = 2*42 + 1*48. (End)
From _Wolfdieter Lang_, Sep 20 2013: (Start)
  Example for rho(N) = 2*cos(Pi/N) powers:
  n=2: rho(N)^5 = 5*R(N, 2) + 4*R(N, 4) + 1*R(N, 6) = 5*S(1, rho(N)) + 4*S(3, rho(N)) + 1*S(5, rho(N)), identical in N >= 1. For N=5 (the pentagon with only one distinct diagonal) the degree delta(5) = 2, hence R(5, 4) and R(5, 6) can be reduced, namely to R(5, 1) = 1 and R(5, 6) = -R(5,1) = -1, respectively. Thus rho(5)^5 = 5*R(N, 2) + 4*1  + 1*(-1) = 3 + 5*R(N, 2) = 3 + 5*rho(5), with the golden section rho(5). (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.
  • B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.

Links

Crossrefs

Mirror image of A050166. Row sums are A001700.
Cf. A000108, A008313, A039599, A183134, A094527, A033184, A035324, A053122, A172417.

Programs

  • Magma
    /* As triangle: */ [[Binomial(2*n,n-k) - Binomial(2*n,n-k-2): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jul 22 2015
  • Maple
    T:=(n,k)->binomial(2*n, n-k) - binomial(2*n, n-k-2); # N. J. A. Sloane, Aug 26 2013
# Uses function PMatrix from A357368. Adds row and column above and to the left.
PMatrix(10, n -> binomial(2*n, n) / (n + 1)); # Peter Luschny, Oct 07 2022
  • Mathematica
    Flatten[Table[Binomial[2n, n-k] - Binomial[2n, n-k-2], {n,0,9}, {k,0,n}]] (* Jean-François Alcover, May 03 2011 *)
  • PARI
    T(n,k)=binomial(2*n,n-k) - binomial(2*n,n-k-2) \\ Charles R Greathouse IV, Nov 07 2016
  • Sage
    # Algorithm of L. Seidel (1877)
# Prints the first n rows of the triangle.
def A039598_triangle(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 1
    for i in range(2*n) :
        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]
        b = not b
        if b : print([D[z] for z in (1..h-1) ])
A039598_triangle(10)  # Peter Luschny, May 01 2012

Formula

Row n: C(2n, n-k) - C(2n, n-k-2).
a(n, k) = C(2n+1, n-k)*2*(k+1)/(n+k+2) = A050166(n, n-k) = a(n-1, k-1) + 2*a(n-1, k)+ a (n-1, k+1) [with a(0, 0) = 1 and a(n, k) = 0 if n<0 or nHenry Bottomley, Sep 24 2001
From Philippe Deléham, Feb 14 2004: (Start)
T(n, 0) = A000108(n+1), T(n, k) = 0 if n0, T(n, k) = Sum_{j=1..n} T(n-j, k-1)*A000108(j).
G.f. for column k: Sum_{n>=0} T(n, k)*x^n = x^k*C(x)^(2*k+2) where C(x) = Sum_{n>=0} A000108(n)*x^n is g.f. for Catalan numbers, A000108.
Sum_{k>=0} T(m, k)*T(n, k) = A000108(m+n+1). (End)
T(n, k) = A009766(n+k+1, n-k) = A033184(n+k+2, 2k+2). - Philippe Deléham, Feb 14 2004
Sum_{j>=0} T(k, j)*A039599(n-k, j) = A028364(n, k). - Philippe Deléham, Mar 04 2004
Antidiagonal Sum_{k=0..n} T(n-k, k) = A000957(n+3). - Gerald McGarvey, Jun 05 2005
The triangle may also be generated from M^n * [1,0,0,0,...], where M = an infinite tridiagonal matrix with 1's in the super- and subdiagonals and [2,2,2,...] in the main diagonal. - Gary W. Adamson, Dec 17 2006
G.f.: G(t,x) = C^2/(1-txC^2), where C = (1-sqrt(1-4x))/(2x) is the Catalan function. From here G(-1,x)=C, i.e., the alternating row sums are the Catalan numbers (A000108). - Emeric Deutsch, Jan 20 2007
Sum_{k=0..n} T(n,k)*x^k = A000957(n+1), A000108(n), A000108(n+1), A001700(n), A049027(n+1), A076025(n+1), A076026(n+1) for x=-2,-1,0,1,2,3,4 respectively (see square array in A067345). - Philippe Deléham, Mar 21 2007, Nov 04 2011
Sum_{k=0..n} T(n,k)*(k+1) = 4^n. - Philippe Deléham, Mar 30 2007
Sum_{j>=0} T(n,j)*binomial(j,k) = A035324(n,k), A035324 with offset 0 (0 <= k <= n). - Philippe Deléham, Mar 30 2007
T(n,k) = A053121(2*n+1,2*k+1). - Philippe Deléham, Apr 16 2007, Apr 18 2007
T(n,k) = A039599(n,k) + A039599(n,k+1). - Philippe Deléham, Sep 11 2007
Sum_{k=0..n+1} T(n+1,k)*k^2 = A029760(n). - Philippe Deléham, Dec 16 2007
Sum_{k=0..n} T(n,k)*A059841(k) = A000984(n). - Philippe Deléham, Nov 12 2008
G.f.: 1/(1-xy-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-.... (continued fraction).
Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A001700(n), A194723(n+1), A194724(n+1), A194725(n+1), A194726(n+1), A194727(n+1), A194728(n+1), A194729(n+1), A194730(n+1) for x = 0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Nov 03 2011
From Peter Bala, Dec 21 2014: (Start)
This triangle factorizes in the Riordan group as ( C(x), x*C(x) ) * ( 1/(1 - x), x/(1 - x) ) = A033184 * A007318, where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. for the Catalan numbers A000108.
Let U denote the lower unit triangular array with 1's on or below the main diagonal and zeros elsewhere. For k = 0,1,2,... define U(k) to be the lower unit triangular block array
/I_k 0\
\ 0 U/ having the k X k identity matrix I_k as the upper left block; in particular, U(0) = U. Then this array equals the bi-infinite product (...*U(2)*U(1)*U(0))*(U(0)*U(1)*U(2)*...). (End)
From Peter Bala, Jul 21 2015: (Start)
O.g.f. G(x,t) = (1/x) * series reversion of ( x/f(x,t) ), where f(x,t) = ( 1 + (1 + t)*x )^2/( 1 + t*x ).
1 + x*d/dx(G(x,t))/G(x,t) = 1 + (2 + t)*x + (6 + 4*t + t^2)*x^2 + ... is the o.g.f for A094527. (End)
Conjecture: Sum_{k=0..n} T(n,k)/(k+1)^2 = H(n+1)*A000108(n)*(2*n+1)/(n+1), where H(n+1) = Sum_{k=0..n} 1/(k+1). - Werner Schulte, Jul 23 2015
From Werner Schulte, Jul 25 2015: (Start)
Sum_{k=0..n} T(n,k)*(k+1)^2 = (2*n+1)*binomial(2*n,n). (A002457)
Sum_{k=0..n} T(n,k)*(k+1)^3 = 4^n*(3*n+2)/2.
Sum_{k=0..n} T(n,k)*(k+1)^4 = (2*n+1)^2*binomial(2*n,n).
Sum_{k=0..n} T(n,k)*(k+1)^5 = 4^n*(15*n^2+15*n+4)/4. (End)
The o.g.f. G(x,t) is such that G(x,t+1) is the o.g.f. for A035324, but with an offset of 0, and G(x,t-1) is the o.g.f. for A033184, again with an offset of 0. - Peter Bala, Sep 20 2015
Denote this lower triangular array by L; then L * transpose(L) is the Cholesky factorization of the Hankel matrix ( 1/(i+j)*binomial(2*i+2*j-2, i+j-1) )A172417%20read%20as%20a%20square%20array.%20See%20Chamberland,%20p.%201669.%20-%20_Peter%20Bala">i,j >= 1 = A172417 read as a square array. See Chamberland, p. 1669. - _Peter Bala, Oct 15 2023

Extensions

Typo in one entry corrected by Philippe Deléham, Dec 16 2007

A063007 T(n,k) = binomial(n,k)*binomial(n+k,k), 0 <= k <= n, triangle read by rows.

Original entry on oeis.org

1, 1, 2, 1, 6, 6, 1, 12, 30, 20, 1, 20, 90, 140, 70, 1, 30, 210, 560, 630, 252, 1, 42, 420, 1680, 3150, 2772, 924, 1, 56, 756, 4200, 11550, 16632, 12012, 3432, 1, 72, 1260, 9240, 34650, 72072, 84084, 51480, 12870, 1, 90, 1980, 18480, 90090, 252252, 420420, 411840, 218790, 48620
Offset: 0

Views

Author

Henry Bottomley, Jul 02 2001

Keywords

Comments

T(n,k) is the number of compatible k-sets of cluster variables in Fomin and Zelevinsky's Cluster algebra of finite type B_n. Take a row of this triangle regarded as a polynomial in x and rewrite as a polynomial in y := x+1. The coefficients of the polynomial in y give a row of triangle A008459 (squares of binomial coefficients). For example, x^2+6*x+6 = y^2+4*y+1. - Paul Boddington, Mar 07 2003
T(n,k) is the number of lattice paths from (0,0) to (n,n) using steps E=(1,0), N=(0,1) and D=(1,1) (i.e., bilateral Schroeder paths), having k N=(0,1) steps. E.g. T(2,0)=1 because we have DD; T(2,1) = 6 because we have NED, NDE, EDN, END, DEN and DNE; T(2,2)=6 because we have NNEE, NENE, NEEN, EENN, ENEN and ENNE. - Emeric Deutsch, Apr 20 2004
Another version of [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] DELTA [0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...] = 1; 1, 0; 1, 2, 0; 1, 6, 6, 0; 1, 12, 30, 20, 0; ..., where DELTA is the operator defined in A084938. - Philippe Deléham Apr 15 2005
Terms in row n are the coefficients of the Legendre polynomial P(n,2x+1) with increasing powers of x.
From Peter Bala, Oct 28 2008: (Start)
Row n of this triangle is the f-vector of the simplicial complex dual to an associahedron of type B_n (a cyclohedron) [Fomin & Reading, p.60]. See A008459 for the corresponding h-vectors for associahedra of type B_n and A001263 and A033282 respectively for the h-vectors and f-vectors for associahedra of type A_n.
An alternative description of this triangle in terms of f-vectors is as follows. Let A_n be the root lattice generated as a monoid by {e_i - e_j: 0 <= i,j <= n+1}. Let P(A_n) be the polytope formed by the convex hull of this generating set. Then the rows of this array are the f-vectors of a unimodular triangulation of P(A_n) [Ardila et al.]. A008459 is the corresponding array of h-vectors for these type A_n polytopes. See A127674 (without the signs) for the array of f-vectors for type C_n polytopes and A108556 for the array of f-vectors associated with type D_n polytopes.
The S-transform on the ring of polynomials is the linear transformation of polynomials that is defined on the basis monomials x^k by S(x^k) = binomial(x,k) = x(x-1)...(x-k+1)/k!. Let P_n(x) denote the S-transform of the n-th row polynomial of this array. In the notation of [Hetyei] these are the Stirling polynomials of the type B associahedra. The first few values are P_1(x) = 2*x + 1, P_2(x) = 3*x^2 + 3*x + 1 and P_3(x) = (10*x^3 + 15*x^2 + 11*x + 3)/3. These polynomials have their zeros on the vertical line Re x = -1/2 in the complex plane, that is, the polynomials P_n(-x) satisfy a Riemann hypothesis. See A142995 for further details. The sequence of values P_n(k) for k = 0,1,2,3, ... produces the n-th row of A108625. (End)
This is the row reversed version of triangle A104684. - Wolfdieter Lang, Sep 12 2016
T(n, k) is also the number of (n-k)-dimensional faces of a convex n-dimensional Lipschitz polytope of real functions f defined on the set X = {1, 2, ..., n+1} which satisfy the condition f(n+1) = 0 (see Gordon and Petrov). - Stefano Spezia, Sep 25 2021
The rows seem to give (up to sign) the coefficients in the expansion of the integer-valued polynomial ((x+1)*(x+2)*(x+3)*...*(x+n) / n!)^2 in the basis made of the binomial(x+i,i). - F. Chapoton, Oct 09 2022
Chapoton's observation above is correct: the precise expansion is ((x+1)*(x+2)*(x+3)*...*(x+n)/ n!)^2 = Sum_{k = 0..n} (-1)^k*T(n,n-k)*binomial(x+2*n-k, 2*n-k), as can be verified using the WZ algorithm. For example, n = 3 gives ((x+1)*(x+2)*(x+3)/3!)^2 = 20*binomial(x+6,6) - 30*binomial(x+5,5) + 12*binomial(x+4,4) - binomial(x+3,3). - Peter Bala, Jun 24 2023

Examples

			The triangle T(n, k) starts:
  n\k 0  1    2     3     4      5      6      7      8     9
  0:  1
  1:  1  2
  2:  1  6    6
  3:  1 12   30    20
  4:  1 20   90   140    70
  5:  1 30  210   560   630    252
  6:  1 42  420  1680  3150   2772    924
  7:  1 56  756  4200 11550  16632  12012   3432
  8:  1 72 1260  9240 34650  72072  84084  51480  12870
  9:  1 90 1980 18480 90090 252252 420420 411840 218790 48620
... reformatted by _Wolfdieter Lang_, Sep 12 2016
From _Petros Hadjicostas_, Jul 11 2020: (Start)
Its inverse (from Table II, p. 92, in Ser's book) is
   1;
  -1/2,  1/2;
   1/3, -1/2,    1/6;
  -1/4,  9/20,  -1/4,   1/20;
   1/5, -2/5,    2/7,  -1/10,  1/70;
  -1/6,  5/14, -25/84,  5/36, -1/28,  1/252;
   1/7, -9/28,  25/84, -1/6,   9/154, -1/84, 1/924;
   ... (End)

References

  • J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p. 366.
  • J. Ser, Les Calculs Formels des Séries de Factorielles. Gauthier-Villars, Paris, 1933, Table I, p. 92.
  • D. Zagier, Integral solutions of Apery-like recurrence equations, in: Groups and Symmetries: from Neolithic Scots to John McKay, CRM Proc. Lecture Notes 47, Amer. Math. Soc., Providence, RI, 2009, pp. 349-366.

Links

Crossrefs

See A331430 for an essentially identical triangle, except with signed entries.
Columns include A000012, A002378, A033487 on the left and A000984, A002457, A002544 on the right.
Main diagonal is A006480.
Row sums are A001850. Alternating row sums are A033999.
Cf. A007318, A008459, A009766, A046899, A104684, A109983, A127674.
Cf. A033282 (f-vectors type A associahedra), A108625, A080721 (f-vectors type D associahedra).
The Apéry-like numbers [or Apéry-like sequences, Apery-like numbers, Apery-like sequences] include A000172, A000984, A002893, A002895, A005258, A005259, A005260, A006077, A036917, A063007, A081085, A093388, A125143 (apart from signs), A143003, A143007, A143413, A143414, A143415, A143583, A183204, A214262, A219692,A226535, A227216, A227454, A229111 (apart from signs), A260667, A260832, A262177, A264541, A264542, A279619, A290575, A290576. (The term "Apery-like" is not well-defined.)

Programs

  • Haskell
    a063007 n k = a063007_tabl !! n !! k
a063007_row n = a063007_tabl !! n
a063007_tabl = zipWith (zipWith (*)) a007318_tabl a046899_tabl
-- Reinhard Zumkeller, Nov 18 2014
  • Magma
    /* As triangle: */ [[Binomial(n,k)*Binomial(n+k,k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Sep 03 2015
  • Maple
    p := (n,x) -> orthopoly[P](n,1+2*x): seq(seq(coeff(p(n,x),x,k), k=0..n), n=0..9);
  • Mathematica
    Flatten[Table[Binomial[n, k]Binomial[n + k, k], {n, 0, 10}, {k, 0, n}]] (* Harvey P. Dale, Dec 24 2011 *)
Table[CoefficientList[Hypergeometric2F1[-n, n + 1, 1, -x], x], {n, 0, 9}] // Flatten
(* Peter Luschny, Mar 09 2018 *)
  • PARI
    {T(n, k) = local(t); if( n<0, 0, t = (x + x^2)^n; for( k=1, n, t=t'); polcoeff(t, k) / n!)} /* Michael Somos, Dec 19 2002 */
  • PARI
    {T(n, k) = binomial(n, k) * binomial(n+k, k)} /* Michael Somos, Sep 22 2013 */
  • PARI
    {T(n, k) = if( k<0 || k>n, 0, (n+k)! / (k!^2 * (n-k)!))} /* Michael Somos, Sep 22 2013 */

Formula

T(n, k) = (n+k)!/(k!^2*(n-k)!) = T(n-1, k)*(n+k)/(n-k) = T(n, k-1)*(n+k)*(n-k+1)/k^2 = T(n-1, k-1)*(n+k)*(n+k-1)/k^2.
binomial(x, n)^2 = Sum_{k>=0} T(n,k) * binomial(x, n+k). - Michael Somos, May 11 2012
T(n, k) = A109983(n, k+n). - Michael Somos, Sep 22 2013
G.f.: G(t, z) = 1/sqrt(1-2*z-4*t*z+z^2). Row generating polynomials = P_n(1+2z), i.e., T(n, k) = [z^k] P_n(1+2*z), where P_n are the Legendre polynomials. - Emeric Deutsch, Apr 20 2004
Sum_{k>=0} T(n, k)*A000172(k) = Sum_{k>=0} T(n, k)^2 = A005259(n). - Philippe Deléham, Jun 08 2005
1 + z*d/dz(log(G(t,z))) = 1 + (1 + 2*t)*z + (1 + 8*t + 8*t^2)*z^2 + ... is the o.g.f. for a signed version of A127674. - Peter Bala, Sep 02 2015
If R(n,t) denotes the n-th row polynomial then x^3 * exp( Sum_{n >= 1} R(n,t)*x^n/n ) = x^3 + (1 + 2*t)*x^4 + (1 + 5*t + 5*t^2)*x^5 + (1 + 9*t + 21*t^2 + 14*t^3)*x^6 + ... is an o.g.f for A033282. - Peter Bala, Oct 19 2015
P(n,x) := 1/(1 + x)*Integral_{t = 0..x} R(n,t) dt are (modulo differences of offset) the row polynomials of A033282. - Peter Bala, Jun 23 2016
From Peter Bala, Mar 09 2018: (Start)
R(n,x) = Sum_{k = 0..n} binomial(2*k,k)*binomial(n+k,n-k)*x^k.
R(n,x) = Sum_{k = 0..n} binomial(n,k)^2*x^k*(1 + x)^(n-k).
n*R(n,x) = (1 + 2*x)*(2*n - 1)*R(n-1,x) - (n - 1)*R(n-2,x).
R(n,x) = (-1)^n*R(n,-1 - x).
R(n,x) = 1/n! * (d/dx)^n ((x^2 + x)^n). (End)
The row polynomials are R(n,x) = hypergeom([-n, n + 1], [1], -x). - Peter Luschny, Mar 09 2018
T(n,k) = C(n+1,k)*A009766(n,k). - Bob Selcoe, Jan 18 2020 (Connects this triangle with the Catalan triangle. - N. J. A. Sloane, Jan 18 2020)
If we let A(n,k) = (-1)^(n+k)*(2*k+1)*(n*(n-1)*...*(n-(k-1)))/((n+1)*...*(n+(k+1))) for n >= 0 and k = 0..n, and we consider both T(n,k) and A(n,k) as infinite lower triangular arrays, then they are inverses of one another. (Empty products are by definition 1.) See the example below. The rational numbers |A(n,k)| appear in Table II on p. 92 in Ser's (1933) book. - Petros Hadjicostas, Jul 11 2020
From Peter Bala, Nov 28 2021: (Start)
Row polynomial R(n,x) = Sum_{k >= n} binomial(k,n)^2 * x^(k-n)/(1+x)^(k+1) for x > -1/2.
R(n,x) = 1/(1 + x)^(n+1) * hypergeom([n+1, n+1], [1], x/(1 + x)).
R(n,x) = (1 + x)^n * hypergeom([-n, -n], [1], x/(1 + x)).
R(n,x) = hypergeom([(n+1)/2, -n/2], [1], -4*x*(1 + x)).
If we set R(-1,x) = 1, we can run the recurrence n*R(n,x) = (1 + 2*x)*(2*n - 1)*R(n-1,x) - (n - 1)*R(n-2,x) backwards to give R(-n,x) = R(n-1,x).
R(n,x) = [t^n] ( (1 + t)*(1 + x*(1 + t)) )^n. (End)
n*T(n,k) = (2*n-1)*T(n-1,k) + (4*n-2)*T(n-1,k-1) - (n-1)*T(n-2,k). - Fabián Pereyra, Jun 30 2022
From Peter Bala, Oct 07 2024: (Start)
n-th row polynomial R(n,x) = Sum_{k = 0..n} binomial(n, k) * x^k o (1 + x)^(n-k), where o denotes the black diamond product of power series as defined by Dukes and White (see Bala, Section 4.4, exercise 3).
Denote this triangle by T. Then T * transpose(T) = A143007, the square array of crystal ball sequences for the A_n X A_n lattices.
Let S denote the triangle ((-1)^(n+k)*T(n, k))n,k >= 0, a signed version of this triangle. Then S^(-1) * T = A007318, Pascal's triangle; it appears that T * S^(-1) = A110098.
T = A007318 * A115951. (End)
Previous Showing 21-30 of 124 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.