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

 

Logo


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

0,5

COMMENTS

T(n,k) is the number of ways to distribute k identical objects in n distinct containers; containers may be left empty.

T(n,k) is the number of nondecreasing functions f from {1,...,k} to {1,...,n}. - Dennis P. Walsh, Apr 07 2011

Coefficients of Faber polynomials for function x^2/(x-1). - Michael Somos, Sep 09 2003

Consider k-fold Cartesian products CP(n,k) of the vector A(n)=[1,2,3,...,n].

An element of CP(n,k) is a n-tuple T_t of the form T_t=[i_1,i_2,i_3,...,i_k] with t=1,...,n^k.

We count members T of CP(n,k) which satisfy some condition delta(T_t), so delta(.) is an indicator function which attains values of 1 or 0 depending on whether T_t is to be counted or not; the summation sum_{CP(n,k)} delta(T_t) over all elements T_t of CP produces the count.

For the triangle here we have delta(T_t) = 0 if for any two i_j, i_(j+1) in T_t one has i_j > i_(j+1), T(n,k) = Sum_{CP(n,k)} delta(T_t) = Sum_{CP(n,k)} delta(i_j > i_(j+1)).

The indicator function which tests on i_j = i_(j+1) generates A158497, which contains further examples of this type of counting.

Triangle of the numbers of combinations of k elements with repetitions from n elements {1,2,...,n} (when every element i, i=1,...,n, appears in a k-combination either 0, or 1, or 2, ..., or k times). - Vladimir Shevelev, Jun 19 2012

G.f. for Faber polynomials is -log(-t*x-(1-sqrt(1-4*t))/2+1)=sum(n>0, T(n,k)*t^k/n). - Vladimir Kruchinin, Jul 04 2013

Values of complete homogeneous symmetric polynomials with all arguments equal to 1, or, equivalently, the number of monomials of degree k in n variables. - Tom Copeland, Apr 07 2014

Row k >= 0 of the infinite square array A[k,n] = C(n,k), n >= 0, would start with k zeros in front of the first nonzero element C(k,k) = 1; this here is the triangle obtained by taking the first k+1 nonzero terms C(k .. 2k, k) of rows k = 0, 1, 2, ... of that array. - M. F. Hasler, Mar 05 2017

REFERENCES

R. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley, 4th edition, chapter 1.4.

LINKS

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

J. Abate, W. Whitt, Brownian Motion and the Generalized Catalan Numbers, J. Int. Seq. 14 (2011) # 11.2.6, (referring to A158498 before recycling)

M. A. A. Obaid, S. K. Nauman, W. M. Fakieh, C. M. Ringel, The numbers of support-tilting modules for a Dynkin algebra, 2014  and J. Int. Seq. 18 (2015) 15.10.6.

C. M. Ringel, The Catalan combinatorics of the hereditary artin algebras, arXiv preprint arXiv:1502.06553 [math.RT], 2015.

Dennis Walsh, Notes on finite monotonic and non-monotonic functions

FORMULA

Columns: T(n,1) = A000027(n), n >= 1. T(n,2) = A000217(n) = A161680(n+1), n >= 2. T(n,3) = A000292(n), n >= 3. T(n,4) = A000332(n+3), n >= 4. T(n,5) = A000389(n+4), n >= 5. T(n,6) = A000579(n+5), n >=6. T(n,k) = A001405(n+k-1) for k <= n <= k+2. [Corrected and extended by M. F. Hasler, Mar 05 2017]

Rows: T(5,k) = A000332(k+4). T(6,k) = A000389(k+5). T(7,k) = A000579(k+6).

Diagonals: T(n,n) = A001700(n-1). T(n,n-1) = A000984(n-1).

T(n,k) = A046899(n-1,k). - R. J. Mathar, Mar 26 2009

T(n,0) + T(n,1) + . . . + T(n,n-1) = T(n,n). - Jonathan Sondow, Jun 28 2014

From Peter Bala, Jul 21 2015: (Start)

T(n,k) = Sum_{j = k..n} (-1)^(k+j)*binomial(2*n,n+j) *binomial(n+j-1,j)*binomial(j,k) (gives the correct value T(n,k) = 0 for k > n).

O.g.f.: 1/2*( x*(2*x - 1)/(sqrt(1 - 4*t*x)*(1 - x - t)) + (1 + 2*x)/sqrt(1 - 4*t*x) + (1 - t)/(1 - x - t) ) = 1 + (1 + t)*x + (1 + 2*t + 3*t^2)*x^2 + (1 + 3*t + 6*t^2 + 10*t^3)*x^3 + ....

n-th row polynomial R(n,t) = [x^n] ( (1 + x)^2/(1 + x(1 - t)) )^n.

exp( Sum_{n >= 1} R(n,t)*x^n/n ) = 1 + (1 + t)*x + (1 + 2*t + 2*t^2)*x^2 + (1 + 3*t + 5*t^2 + 5*t^3)*x^3 + ... is the o.g.f for A009766. (End)

a(n) = abs(A027555(n)). - M. F. Hasler, Mar 05 2017

EXAMPLE

The triangle T(n,k), n >= 0, 0 <= k <= n, begins

  1      A000217

  1 1   /     A000292

  1 2  3    /    A000332

  1 3  6  10    /    A000389

  1 4 10  20  35    /     A000579

  1 5 15  35  70 126     /

  1 6 21  56 126 252  462

  1 7 28  84 210 462  924 1716

  1 8 36 120 330 792 1716 3432 6435

T(3,2)=6 considers the CP with the 3^2=9 elements (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3), and does not count the 3 of them which are (2,1),(3,1) and (3,2).

T(3,3) = 10 because the ways to distribute the 3 objects into the three containers are: (3,0,0) (0,3,0) (0,0,3) (2,1,0) (1,2,0) (2,0,1) (1,0,2) (0,1,2) (0,2,1) (1,1,1), for a total of 10 possibilities.

T(3,3)=10 since (x^2/(x-1))^3 = (x+1+1/x+O(1/x^2))^3 = x^3+3x^2+6x+10+O(x).

T(4,2)=10 since there are 10 nondecreasing functions f from {1,2} to {1,2,3,4}. Using <f(1),f(2)> to denote such a function, the ten functions are <1,1>, <1,2>, <1,3>, <1,4>, <2,2>, <2,3>, <2,4>, <3,3>, <3,4>, and <4,4>. - Dennis P. Walsh, Apr 07 2011

T(4,0) + T(4,1) + T(4,2) + T(4,3) = 1 + 4 + 10 + 20 = 35 = T(4,4). - Jonathan Sondow, Jun 28 2014

From Paul Curtz, Jun 18 2018: (Start)

Consider the array

2,    1,    1,    1,    1,    1,     ... = A054977(n)

1,    1/2,  1/3,  1/4,  1/5,  1/6,   ... = 1/(n+1) = 1/A000027(n)

1/3,  1/6,  1/10, 1/15, 1/21, 1/28,  ... = 2/((n+2)*(n+3)) = 1/A000217(n+2)

1/10, 1/20, 1/35, 1/56, 1/84, 1/120, ... = 6/((n+3)*(n+4)*(n+5)) =1/A000292(n+2)

(see the triangle T(n,k)).

Every row is an autosequence of the second kind.

See OEIS Wiki, Autosequence

By decreasing antidiagonals the denominator of the array is a(n).

Successive vertical denominators: A088218(n), A000984(n), A001700(n), A001791(n+1), A002054(n), A002694(n).

Successive diagonal denominators: A165817(n), A005809(n), A045721(n), A025174(n+1), A004319(n). (End)

From Paul Curtz, Jun 19 2018: (Start)

Without the first row (2, 1, 1, 1, ... ), the array leads to A165257(n) instead of a(n). (End)

MAPLE

for n from 0 to 10 do for k from 0 to n do printf("%d, ", binomial(n+k-1, k)) ; od: od: # R. J. Mathar, Mar 31 2009

MATHEMATICA

t[n_, k_] := Binomial[n+k-1, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Sep 09 2013 *)

PROG

(PARI) {T(n, k) = binomial( n+k-1, k)}; \\ Michael Somos, Sep 09 2003, edited by M. F. Hasler, Mar 05 2017

(PARI) {T(n, k) = if( n<0, 0, polcoeff( Pol(((1 / (x - x^2) + x * O(x^n))^n + O(x)) * x^n), k))}; /* Michael Somos, Sep 09 2003 */

(MAGMA) &cat [[&*[ Binomial(n+k-1, k)]: k in [0..n]]: n in [0..30] ]; // Vincenzo Librandi, Apr 08 2011

(Haskell)

a059481 n k = a059481_tabl !! n !! n

a059481_row n = a059481_tabl !! n

a059481_tabl = map reverse a100100_tabl

-- Reinhard Zumkeller, Jan 15 2014

CROSSREFS

Take Pascal's triangle A007318, delete entries to the right of a vertical line just right of center, then scan the diagonals.

For a signed version of this triangle see A027555.

Row sums give A000984. Cf. A007318, A158497, A100100 (mirrored), A009766.

A000984, A001700, A001791, A002054, A002694, A004319, A005809, A025174, A045721, A088218, A165817. A054977, A165257.

Sequence in context: A213744 A213745 A213808 * A027555 A113592 A271702

Adjacent sequences:  A059478 A059479 A059480 * A059482 A059483 A059484

KEYWORD

easy,nice,nonn,tabl

AUTHOR

Fabian Rothelius, Feb 04 2001

EXTENSIONS

Offset changed from 1 to 0 by R. J. Mathar, Jan 15 2013

Edited by M. F. Hasler, Mar 05 2017

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 19:12 EST 2018. Contains 317214 sequences. (Running on oeis4.)