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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A100100 Triangle T(n,k) = binomial(2*n-k-1, n-k) read by rows. 22
1, 1, 1, 3, 2, 1, 10, 6, 3, 1, 35, 20, 10, 4, 1, 126, 70, 35, 15, 5, 1, 462, 252, 126, 56, 21, 6, 1, 1716, 924, 462, 210, 84, 28, 7, 1, 6435, 3432, 1716, 792, 330, 120, 36, 8, 1, 24310, 12870, 6435, 3003, 1287, 495, 165, 45, 9, 1, 92378, 48620, 24310, 11440, 5005, 2002 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Sometimes called a Catalan triangle, although there are many other triangles that carry that name - see A009766, A008315, A028364, A033184, A053121, A059365, A062103.

Number of nodes of outdegree k in all ordered trees with n edges. Equivalently, number of ascents of length k in all Dyck paths of semilength n. Example: T(3,2) = 3 because the Dyck paths of semilength 3 are UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and UUUDDD, where U = (1,1), D = (1,-1), the ascents of length 2 being shown between parentheses. - Emeric Deutsch, Nov 19 2006

Riordan array (f(x), x*g(x)) where f(x) is the g.f. of A088218 and g(x) is the g.f. of A000108. - Philippe Deléham, Jan 23 2010

T(n,k) = number of nonnegative paths of upsteps U = (1,1) and downsteps D = (1,-1) of length 2*n with k returns to  ground level, the horizontal line through the initial vertex. Example: T(2,1) = 2 counts UDUU, UUDD. Also, T(n,k) = number of these paths whose last descent has length k, that is, k downsteps follow the last upstep. Example: T(2,1) = 2 counts UUUD, UDUD. - David Callan, Nov 21 2011

Belongs to the hitting-time subgroup of the Riordan group. Multiplying this triangle by the square Pascal matrix gives A092392 read as a square array. See the example below. - Peter Bala, Nov 03 2015

LINKS

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened

P. Bala, Notes on logarithmic differentiation, the binomial transform and series reversion

Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.

Gi-Sang Cheon, Hana Kim, Louis W. Shapiro, An algebraic structure for Faber polynomials, Lin. Alg. Applic. 433 (2010) 1170-1179.

He, Tian-Xiao, and Sprugnoli, Renzo; Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), no. 12, 3962-3974.

FORMULA

Columns have g.f. x^k(sqrt(1-4x)+1)/(sqrt(1-4x)(ksqrt(1-4x)-k+2), or (1/(c(x))sqrt(1-4x))x^k/(1-kxc(x)), where c(x) is the g.f. of A001008. As a square read by antidiagonals, this is defined by binomial(2n+k-1, n).

From Peter Bala, Sep 06 2015: (Start)

Matrix product A094527 * P^(-1) = A113955 * P^(-2), where P denotes Pascal's triangle A007318.

Essentially, the logarithmic derivative of A033184. (End)

EXAMPLE

From Paul Barry, Mar 15 2010: (Start)

Triangle begins in row n=0 with columns 0<=k<=n as:

    1;

    1,   1;

    3,   2,   1;

   10,   6,   3,  1;

   35,  20,  10,  4,  1;

  126,  70,  35, 15,  5, 1;

  462, 252, 126, 56, 21, 6, 1;

Production matrix begins

  1, 1;

  2, 1, 1;

  3, 1, 1, 1;

  4, 1, 1, 1, 1;

  5, 1, 1, 1, 1, 1;

  6, 1, 1, 1, 1, 1, 1;

  7, 1, 1, 1, 1, 1, 1, 1;

(End)

A092392 as a square array = A100100 * square Pascal matrix:

/1   1  1  1 ...\   / 1          \/1 1  1  1 ...\

|2   3  4  5 ...|   | 1 1        ||1 2  3  4 ...|

|6  10 15 21 ...| = | 3 2 1      ||1 3  6 10 ...|

|20 35 56 84 ...|   |10 6 3 1    ||1 4 10 20 ...|

|70 ...         |   |35 ...      ||1 ...        |

- Peter Bala, Nov 03 2015

MAPLE

A100100 := proc(n, k)

    binomial(2*n-k-1, n-1) ;

end proc:

seq(seq(A100100(n, k), k=0..n), n=0..10) ; # R. J. Mathar, Feb 06 2015

MATHEMATICA

Flatten[Table[Binomial[2 n - k - 1, n - k], {n, 0, 11}, {k, 0, n}]] (* Vincenzo Librandi, Nov 21 2018 *)

PROG

(PARI) T(n, k)=binomial(2*n-k-1, n-k) \\ Charles R Greathouse IV, Jan 16 2012

(Haskell)

a100100 n k = a100100_tabl !! n !! n

a100100_row n = a100100_tabl !! n

a100100_tabl = [1] : f a092392_tabl where

   f (us : wss'@(vs : wss)) = (vs !! 1 : us) : f wss'

-- Reinhard Zumkeller, Jan 15 2014

(MAGMA) /* As triangle */ [[Binomial(2*n - k - 1, n - k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Nov 21 2018

CROSSREFS

Row sums are A000984. Equivalent to A092392, to which A088218 has been added as a first column. Columns include A088218, A000984, A001700, A001791, A002054, A002694. Diagonal sums are A100217. Matrix inverse is A100218.

Cf. A059481 (mirrored). Cf. A033184, A094527, A113955.

Sequence in context: A267742 A267278 A267019 * A248036 A307214 A185967

Adjacent sequences:  A100097 A100098 A100099 * A100101 A100102 A100103

KEYWORD

easy,nonn,tabl

AUTHOR

Paul Barry, Nov 08 2004

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 22 15:00 EDT 2019. Contains 325224 sequences. (Running on oeis4.)