|
%I #163 Nov 24 2023 08:09:58
%S 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,
%T 462,1,7,28,84,210,462,924,1716,1,8,36,120,330,792,1716,3432,6435,1,9,
%U 45,165,495,1287,3003,6435,12870,24310,1,10,55,220,715,2002,5005,11440,24310,48620,92378
%N Triangle read by rows. T(n, k) = binomial(n+k-1, k) for 0 <= k <= n.
%C T(n,k) is the number of ways to distribute k identical objects in n distinct containers; containers may be left empty.
%C T(n,k) is the number of nondecreasing functions f from {1,...,k} to {1,...,n}. - _Dennis P. Walsh_, Apr 07 2011
%C Coefficients of Faber polynomials for function x^2/(x-1). - _Michael Somos_, Sep 09 2003
%C Consider k-fold Cartesian products CP(n,k) of the vector A(n)=[1,2,3,...,n].
%C 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.
%C 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.
%C 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)).
%C The indicator function which tests on i_j = i_(j+1) generates A158497, which contains further examples of this type of counting.
%C 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
%C 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
%C 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
%C 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
%D R. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley, 4th edition, chapter 1.4.
%H Reinhard Zumkeller, <a href="/A059481/b059481.txt">Rows n = 0..125 of triangle, flattened</a>
%H J. Abate and W. Whitt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Whitt/whitt6.html">Brownian Motion and the Generalized Catalan Numbers</a>, J. Int. Seq. 14 (2011) # 11.2.6, (referring to A158498 before recycling)
%H M. A. A. Obaid, S. K. Nauman, W. M. Fakieh, and C. M. Ringel, <a href="http://www.math.uni-bielefeld.de/~ringel/opus/jeddah.pdf">The numbers of support-tilting modules for a Dynkin algebra</a>, 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Ringel/ringel22.html">J. Int. Seq. 18 (2015) 15.10.6</a>.
%H C. M. Ringel, <a href="http://arxiv.org/abs/1502.06553">The Catalan combinatorics of the hereditary artin algebras</a>, arXiv:1502.06553 [math.RT], 2015.
%H Dennis Walsh, <a href="http://capone.mtsu.edu/dwalsh/MONOFUNC.pdf">Notes on finite monotonic and non-monotonic functions</a>
%F T(n,0) + T(n,1) + . . . + T(n,n-1) = T(n,n). - _Jonathan Sondow_, Jun 28 2014
%F From _Peter Bala_, Jul 21 2015: (Start)
%F 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).
%F 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 + ....
%F n-th row polynomial R(n,t) = [x^n] ( (1 + x)^2/(1 + x(1 - t)) )^n.
%F 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)
%F a(n) = abs(A027555(n)). - _M. F. Hasler_, Mar 05 2017
%F For n >= k > 0, T(n, k) = Sum_{j=1..n} binomial(k + j - 2, k - 1) = Sum_{j=1..n} A007318(k + j - 2, k - 1). - _Stefano Spezia_, Oct 30 2018
%F T(n, k) = RisingFactorial(n, k) / k!. - _Peter Luschny_, Nov 24 2023
%e The triangle T(n,k), n >= 0, 0 <= k <= n, begins
%e 1 A000217
%e 1 1 / A000292
%e 1 2 3 / A000332
%e 1 3 6 10 / A000389
%e 1 4 10 20 35 / A000579
%e 1 5 15 35 70 126 /
%e 1 6 21 56 126 252 462
%e 1 7 28 84 210 462 924 1716
%e 1 8 36 120 330 792 1716 3432 6435
%e .
%e 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).
%e 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.
%e 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).
%e 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
%e 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
%e From _Paul Curtz_, Jun 18 2018: (Start)
%e Consider the array
%e 2, 1, 1, 1, 1, 1, ... = A054977(n)
%e 1, 1/2, 1/3, 1/4, 1/5, 1/6, ... = 1/(n+1) = 1/A000027(n)
%e 1/3, 1/6, 1/10, 1/15, 1/21, 1/28, ... = 2/((n+2)*(n+3)) = 1/A000217(n+2)
%e 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)).
%e Every row is an autosequence of the second kind. (See OEIS Wiki, Autosequence.)
%e By decreasing antidiagonals the denominator of the array is a(n).
%e Successive vertical denominators: A088218(n), A000984(n), A001700(n), A001791(n+1), A002054(n), A002694(n).
%e Successive diagonal denominators: A165817(n), A005809(n), A045721(n), A025174(n+1), A004319(n). (End)
%e Without the first row (2, 1, 1, 1, ... ), the array leads to A165257(n) instead of a(n). - _Paul Curtz_, Jun 19 2018
%p for n from 0 to 10 do for k from 0 to n do print(binomial(n+k-1,k)) ; od: od: # _R. J. Mathar_, Mar 31 2009
%t 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 *)
%t (* The combinatorial objects defined in the first comment can, for n >= 1, be generated by: *) r[n_, k_] := FrobeniusSolve[ConstantArray[1,n],k]; (* _Peter Luschny_, Jan 24 2019 *)
%o (PARI) {T(n, k) = binomial( n+k-1, k)}; \\ _Michael Somos_, Sep 09 2003, edited by _M. F. Hasler_, Mar 05 2017
%o (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 */
%o (Magma) &cat [[&*[ Binomial(n+k-1,k)]: k in [0..n]]: n in [0..30] ]; // _Vincenzo Librandi_, Apr 08 2011
%o (Haskell)
%o a059481 n k = a059481_tabl !! n !! n
%o a059481_row n = a059481_tabl !! n
%o a059481_tabl = map reverse a100100_tabl
%o -- _Reinhard Zumkeller_, Jan 15 2014
%o (GAP) Flat(List([0..10], n->List([0..n], k->Binomial(n+k-1, k)))); # _Stefano Spezia_, Oct 30 2018
%o (Maxima) sjoin(v, j) := apply(sconcat, rest(join(makelist(j, length(v)), v)))$ display_triangle(n) := for i from 0 thru n do disp(sjoin(makelist(binomial(i+j-1, j), j, 0, i), " ")); display_triangle(10); /* triangle output */ /* _Stefano Spezia_, Oct 30 2018 */
%o (Sage) [[binomial(n+k-1,k) for k in range(n+1)] for n in range(11)] # _G. C. Greubel_, Nov 21 2018
%Y 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]
%Y Rows: T(5,k) = A000332(k+4). T(6,k) = A000389(k+5). T(7,k) = A000579(k+6).
%Y Diagonals: T(n,n) = A001700(n-1). T(n,n-1) = A000984(n-1).
%Y T(n,k) = A046899(n-1,k). - _R. J. Mathar_, Mar 26 2009
%Y Take Pascal's triangle A007318, delete entries to the right of a vertical line just right of center, then scan the diagonals.
%Y For a signed version of this triangle see A027555.
%Y Row sums give A000984.
%Y Cf. A007318, A158497, A100100 (mirrored), A009766.
%Y A000984, A001700, A001791, A002054, A002694, A004319, A005809, A025174, A045721, A088218, A165817, A054977, A165257, A000027, A000217, A006134 (trace of the symmetric Pascal matrix).
%K easy,nice,nonn,tabl
%O 0,5
%A _Fabian Rothelius_, Feb 04 2001
%E Offset changed from 1 to 0 by _R. J. Mathar_, Jan 15 2013
%E Edited by _M. F. Hasler_, Mar 05 2017
|
