A053538 Triangle: a(n,m) = ways to place p balls in n slots with m in the rightmost p slots, 0<=p<=n, 0<=m<=n, summed over p, a(n,m)= Sum_{k=0..n} binomial(k,m)*binomial(n-k,k-m), (see program line).

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 5, 5, 4, 1, 1, 8, 10, 7, 5, 1, 1, 13, 18, 16, 9, 6, 1, 1, 21, 33, 31, 23, 11, 7, 1, 1, 34, 59, 62, 47, 31, 13, 8, 1, 1, 55, 105, 119, 101, 66, 40, 15, 9, 1, 1, 89, 185, 227, 205, 151, 88, 50, 17, 10, 1, 1, 144, 324, 426, 414, 321, 213, 113, 61, 19, 11, 1, 1

Offset: 0

Author

Wouter Meeussen, May 23 2001

Keywords

• nonn
• tabl

Comments

Riordan array (1/(1-x-x^2), x(1-x)/(1-x-x^2)). Row sums are A000079. Diagonal sums are A006053(n+2). - Paul Barry, Nov 01 2006

Subtriangle of the triangle given by (0, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Mar 05 2012

Mirror image of triangle in A208342. - Philippe Deléham, Mar 05 2012

A053538 is jointly generated with A076791 as an array of coefficients of polynomials u(n,x): initially, u(1,x)=v(1,x)=1, for n>1, u(n,x) = x*u(n-1,x) + v(n-1,x) and v(n,x) = u(n-1,x) + v(n-1,x). See the Mathematica section at A076791. - Clark Kimberling, Mar 08 2012

The matrix inverse starts

1;

-1, 1;

-1, -1, 1;

1, -2, -1, 1;

3, 1, -3, -1, 1;

1, 6, 1, -4, -1, 1;

-7, 4, 10, 1, -5, -1, 1;

-13, -13, 8, 15, 1, -6, -1, 1;

3, -31, -23, 13, 21, 1, -7, -1, 1; - R. J. Mathar, Mar 15 2013

Also appears to be the number of subsets of {1..n} containing n with k maximal anti-runs of consecutive elements increasing by more than 1. For example, the subset {1,3,6,7,11,12} has maximal anti-runs ((1,3,6),(7,11),(12)) so is counted under a(12,3). For runs instead of anti-runs we get A202064. - Gus Wiseman, Jun 26 2025

Examples

			n=4; Table[binomial[k, j]binomial[n-k, k-j], {k, 0, n}, {j, 0, n}] splits {1, 4, 6, 4, 1} into {{1, 0, 0, 0, 0}, {3, 1, 0, 0, 0}, {1, 4, 1, 0, 0}, {0, 0, 3, 1, 0}, {0, 0, 0, 0, 1}} and this gives summed by columns {5, 5, 4, 1, 1}
Triangle begins :
   1;
   1,  1;
   2,  1,  1;
   3,  3,  1, 1;
   5,  5,  4, 1, 1;
   8, 10,  7, 5, 1, 1;
  13, 18, 16, 9, 6, 1, 1;
...
(0, 1, 1, -1, 0, 0, 0, ...) DELTA (1, 0, -1, 1, 0, 0, 0, ...) begins :
  1;
  0,  1;
  0,  1,  1;
  0,  2,  1,  1;
  0,  3,  3,  1, 1;
  0,  5,  5,  4, 1, 1;
  0,  8, 10,  7, 5, 1, 1;
  0, 13, 18, 16, 9, 6, 1, 1;
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• R. P. Grimaldi, Extraordinary subsets: a generalization, Fib. Quart., 55 (No. 3, 2017), 114-122. See Table 1.

Crossrefs

Column k = 1 is A000045.

Row sums are A000079.

Column k = 2 is A010049.

For runs instead of anti-runs we have A202064.

For integer partitions see A268193, strict A384905, runs A116674.

A034839 counts subsets by number of maximal runs.

A384175 counts subsets with all distinct lengths of maximal runs, complement A384176.

A384877 gives lengths of maximal anti-runs in binary indices, firsts A384878.

A384893 counts subsets by number of maximal anti-runs.

Cf. A000071, A001629, A010027, A208342, A384177, A384879, A384889, A384890.

Programs

GAP

Flat(List([0..12], n-> List([0..n], k-> Sum([0..n], j->  Binomial(j,k)*Binomial(n-j,j-k)) ))); # G. C. Greubel, May 16 2019

Magma

[[(&+[Binomial(j,k)*Binomial(n-j,j-k): j in [0..n]]): k in [0..n]]: n in [0..12]]; // G. C. Greubel, May 16 2019

Maple

a:= (n, m)-> add(binomial(k, m)*binomial(n-k, k-m), k=0..n):
seq(seq(a(n,m), m=0..n), n=0..12);  # Alois P. Heinz, Sep 19 2013

Mathematica

Table[Sum[Binomial[k, m]*Binomial[n-k, k-m], {k,0,n}], {n,0,12}, {m,0,n}]

PARI

{T(n,k) = sum(j=0,n, binomial(j,k)*binomial(n-j,j-k))}; \\ G. C. Greubel, May 16 2019

Sage

[[sum(binomial(j,k)*binomial(n-j,j-k) for j in (0..n)) for k in (0..n)] for n in (0..12)] # G. C. Greubel, May 16 2019

Formula

From Philippe Deléham, Mar 05 2012: (Start)

T(n,k) = T(n-1,k) + T(n-1,k-1) + T(n-2,k) - T(n-2,k-1), T(0,0) = T(1,0) = T(1,1) = 1 and T(n,k) = 0 if k<0 or if k>n.

G.f.: 1/(1-(1+y)*x-(1-y)*x^2).

Sum_{k, 0<=k<=n} T(n,k)*x^k = A077957(n), A000045(n+1), A000079(n), A001906(n+1), A007070(n), A116415(n), A084326(n+1), A190974(n+1), A190978(n+1), A190984(n+1), A190990(n+1), A190872(n+1) for x = -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 respectively. (End)