A134400 M * A007318, where M = triangle with (1, 1, 2, 3, ...) in the main diagonal and the rest zeros.

1, 1, 1, 2, 4, 2, 3, 9, 9, 3, 4, 16, 24, 16, 4, 5, 25, 50, 50, 25, 5, 6, 36, 90, 120, 90, 36, 6, 7, 49, 147, 245, 245, 147, 49, 7, 8, 64, 224, 448, 560, 448, 224, 64, 8, 9, 81, 324, 756, 1134, 1134, 756, 324, 81, 9, 10, 100, 450, 1200, 2100, 2520, 2100, 1200, 450, 100, 10

Offset: 0

Author

Gary W. Adamson, Oct 23 2007

Keywords

• nonn
• tabl

Comments

Row sums = A134401: (1, 2, 8, 24, 64, 160, 384, ...).

Triangle T(n,k), read by rows, given by [1,1,-1,1,0,0,0,0,0,...] DELTA [1,1,-1,1,0,0,0,0,0,...] where DELTA is the operator defined in A084938. A134402*A007318 as infinite lower triangular matrices. - Philippe Deléham, Oct 26 2007

For n > 0, from n athletes, select a team of k players and then choose a coach who is allowed to be on the team or not. - Geoffrey Critzer, Mar 13 2010

Row sums are A036289 if first term changed to zero. Diagonal sums are A023610, starting with the 2nd diagonal. Partial sums of diagonals are A002940 if first term changed to zero. - John Molokach, Jul 06 2013

For n > 0, T(n,k) is the number of states in Sokoban puzzle with n non-obstacles cells and k boxes (see Russell and Norvig at page 157). - Stefano Spezia, Dec 03 2023

Examples

			First few rows of the triangle:
  1;
  1,  1;
  2,  4,   2;
  3,  9,   9,   3;
  4, 16,  24,  16,   4;
  5, 25,  50,  50,  25,   5;
  6, 36,  90, 120,  90,  36,  6;
  7, 49, 147, 245, 245, 147, 49, 7;
  ...
		

References

• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Fourth Edition, Hoboken: Pearson, 2021.

Links

• Wikipedia, Sokoban

Crossrefs

Cf. A002940, A003506, A007318, A036289, A134401, A134402.

T(2n,n) give A002011(n-1) for n>=1.

Programs

Maple

with(combstruct): for n from 0 to 10 do seq(`if`(n=0, 1, n)* count( Combination(n), size=m), m=0..n) od; # Zerinvary Lajos, Apr 09 2008

Mathematica

Join[{1},Table[Table[n*Binomial[n, k], {k,0, n}], {n, 10}]] //Flatten (* Geoffrey Critzer, Mar 13 2010 adapted by Stefano Spezia, Dec 03 2023 *)

Formula

From Geoffrey Critzer, Mar 13 2010: (Start)

T(0,0) = 1 and T(n,k) = n * binomial(n,k) for n > 0.

E.g.f. for column k is: (x^k/k!)*exp(x)*(x+k). (End)

T(n,k) = A003506(n,k) + A003506(n,k-1). - Geoffrey Critzer, Mar 13 2010

G.f.: (1-x-x*y+x^2+x^2*y+x^2*y^2)/(1-2*x-2*x*y+x^2+2*x^2*y+x^2*y^2). - Philippe Deléham, Nov 14 2013

T(n,k) = 2*T(n-1,k) + 2*T(n-1,k-1) - T(n-2,k) - 2*T(n-2,k-1) - T(n-2,k-2), T(0,0)=T(1,0)=T(1,1)=1, T(2,0)=T(2,2)=2, T(2,1)=4, T(n,k)=0 if k < 0 or if k > n. - Philippe Deléham, Nov 14 2013

E.g.f.: 1 + exp(y*x)*exp(x)*(y*x + x). - Geoffrey Critzer, Mar 15 2015

Extensions

a(55)-a(65) from Stefano Spezia, Dec 03 2023