|
| |
|
|
A078812
|
|
Triangle read by rows: T(n, k) = binomial(n+k-1, 2*k-1).
|
|
43
|
|
|
|
1, 2, 1, 3, 4, 1, 4, 10, 6, 1, 5, 20, 21, 8, 1, 6, 35, 56, 36, 10, 1, 7, 56, 126, 120, 55, 12, 1, 8, 84, 252, 330, 220, 78, 14, 1, 9, 120, 462, 792, 715, 364, 105, 16, 1, 10, 165, 792, 1716, 2002, 1365, 560, 136, 18, 1, 11, 220, 1287, 3432, 5005, 4368, 2380, 816, 171, 20, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Warning: formulas and programs sometimes refer to offset 0 and sometimes to offset 1.
Apart from signs, identical to A053122.
T(n,k) is the number of compositions of n having k parts when there are q kinds of part q (q=1,2,...). Example: T(4,2) = 10 because we have (1,3),(1,3'),(1,3"), (3,1),(3',1),(3",1),(2,2),(2,2'),(2',2) and (2',2'). - Emeric Deutsch, Apr 09 2005
T(n, k) is also the number of idempotent order-preserving full transformations (of an n-chain) of height k (height(alpha) = |Im(alpha)|). - Abdullahi Umar, Oct 02 2008
This sequence is jointly generated with A085478 as a triangular array of coefficients of polynomials v(n,x): initially, u(1,x) = v(1,x) = 1; for n > 1, u(n,x) = u(n-1,x) + x*v(n-1)x and v(n,x) = u(n-1,x) + (x+1)*v(n-1,x). See the Mathematica section. - Clark Kimberling, Feb 25 2012
Subtriangle of the triangle T(n,k), 0 <= k <= n, read by rows, given by (0, 2, -1/2, 1/2, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Mar 27 2012
With offset [0,0] the triangle with entries R(n,k) = T(n+1,k+1):= binomial(n+k+1, 2*k+1), n >= k >= 0, and zero otherwise, becomes the Riordan lower triangular convolution matrix R = (G(x)/x, G(x)) with G(x):=x/(1-x)^2 (o.g.f. of A000027). This means that the o.g.f. of column number k of R is (G(x)^(k+1))/x. This matrix R is the inverse of the signed Riordan lower triangular matrix A039598, called in a comment there S.
The Riordan matrix with entries R(n,k), just defined, provides the transition matrix between the sequence entry F(4*m*(n+1))/L(2*l), with m >= 0, for n=0,1,... and the sequence entries 5^k*F(2*m)^(2*k+1) for k = 0,1,...,n, with F=A000045 (Fibonacci) and L=A000032 (Lucas). Proof: from the inverse of the signed triangle Riordan matrix S used in a comment on A039598.
For the transition matrix R (T with offset [0,0]) defined above, row n=2: F(12*m) /L(2*m) = 3*5^0*F(2*m)^1 + 4*5^1*F(2*m)^3 + 1*5^2*F(2*m)^5, m >= 0. (End)
From R. Bagula's comment in A053122 (cf. Damianou link p. 10), this array gives the coefficients (mod sign) of the characteristic polynomials for the Cartan matrix of the root system A_n. - Tom Copeland, Oct 11 2014
For 1 <= k <= n, T(n,k) equals the number of (n-1)-length ternary words containing k-1 letters equal 2 and avoiding 01. - Milan Janjic, Dec 20 2016
The infinite sum (Sum_{i >= 0} (T(s+i,1+i) / 2^(s+2*i)) * zeta(s+1+2*i)) = 1 allows any zeta(s+1) to be expressed as a sum of rational multiples of zeta(s+1+2*i) having higher arguments. For example, zeta(3) can be expressed as a sum involving zeta(5), zeta(7), etc. The summation for each s >= 1 uses the s-th diagonal of the triangle. - Robert B Fowler, Feb 23 2022
The convolution triangle of the nonnegative integers. - Peter Luschny, Oct 07 2022
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: x*y / (1 - (2 + y)*x + x^2). To get row n, expand this in powers of x then expand the coefficient of x^n in increasing powers of y.
If indexing begins at 0 we have
T(n,k) = (n+k+1)!/((n-k)!*(2k+1))!.
T(n,k) = Sum_{j>=0} T(n-1-j, k-1)*(j+1) with T(n, 0) = n+1, T(n, k) = 0 if n < k.
T(n,k) = T(n-1, k-1) + T(n-1, k) + Sum_{j>=0} (-1)^j*T(n-1, k+j)*A000108(j) with T(n,k) = 0 if k < 0, T(0, 0)=1 and T(0, k) = 0 for k > 0.
G.f. for the column k: Sum_{n>=0} T(n, k)*x^n = (x^k)/(1-x)^(2k+2).
Row sums: Sum_{k>=0} T(n, k) = A001906(n+1). (End)
Antidiagonal sums are A000079(n) = Sum_{k=0..floor(n/2)} binomial(n+k+1, n-k). - Paul Barry, Jun 21 2004
Riordan array (1/(1-x)^2, x/(1-x)^2). - Paul Barry, Oct 22 2006
T(0,0) = 1, T(n,k) = 0 if k < 0 or if k > n, T(n,k) = T(n-1,k-1) + 2*T(n-1,k) - T(n-2,k). - Philippe Deléham, Jan 26 2010
T(n,m) = Sum_{k=0..n-m} (binomial(2*k,n-m)*binomial(m+k,k)*(-1)^(n-m+k)* binomial(n+1,m+k+1)). - Vladimir Kruchinin, Apr 13 2016
|
|
|
EXAMPLE
|
Triangle begins, 1 <= k <= n:
1
2 1
3 4 1
4 10 6 1
5 20 21 8 1
6 35 56 36 10 1
7 56 126 120 55 12 1
8 84 252 330 220 78 14 1
|
|
|
MAPLE
|
for n from 1 to 11 do seq(binomial(n+k-1, 2*k-1), k=1..n) od; # yields sequence in triangular form; Emeric Deutsch, Apr 09 2005
# Uses function PMatrix from A357368. Adds a row and column above and to the left.
|
|
|
MATHEMATICA
|
(* First program *)
u[1, x_]:= 1; v[1, x_]:= 1; z = 13;
u[n_, x_]:= u[n-1, x] + x*v[n-1, x];
v[n_, x_]:= u[n-1, x] + (x+1)*v[n-1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
(* Second program *)
Table[Binomial[n+k+1, 2*k+1], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Aug 01 2019 *)
|
|
|
PROG
|
(PARI) {T(n, k) = if( n<0, 0, binomial(n+k-1, 2*k-1))};
(PARI) {T(n, k) = polcoeff( polcoeff( x*y / (1 - (2 + y) * x + x^2) + x * O(x^n), n), k)};
(Haskell)
a078812 n k = a078812_tabl !! n !! k
a078812_row n = a078812_tabl !! n
a078812_tabl = [1] : [2, 1] : f [1] [2, 1] where
f us vs = ws : f vs ws where
ws = zipWith (-) (zipWith (+) ([0] ++ vs) (map (* 2) vs ++ [0]))
(us ++ [0, 0])
(Sage)
@cached_function
def T(k, n):
if k==n: return 1
if k==0: return 0
return sum(i*T(k-1, n-i) for i in (1..n-k+1))
(Sage) [[binomial(n+k+1, 2*k+1) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Aug 01 2019
(Maxima)
T(n, m):=sum(binomial(2*k, n-m)*binomial(m+k, k)*(-1)^(n-m+k)*binomial(n+1, m+k+1), k, 0, n-m); /* Vladimir Kruchinin, Apr 13 2016 */
(Magma) /* As triangle */ [[Binomial(n+k-1, 2*k-1): k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Jun 01 2018
(GAP) Flat(List([0..12], n-> List([0..n], k-> Binomial(n+k+1, 2*k+1) ))); # G. C. Greubel, Aug 01 2019
|
|
|
CROSSREFS
|
This triangle is formed from odd-numbered rows of triangle A011973 read in reverse order.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
