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,4

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

References

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

Links

Table of n, a(n) for n=0..65.

Wikipedia, Sokoban

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

Example

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;
  ...

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 *)

Crossrefs

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

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

Sequence in context: A349400 A335678 A368434 * A016095 A298309 A349205

Adjacent sequences: A134397 A134398 A134399 * A134401 A134402 A134403

Keyword

nonn,tabl

Author

Gary W. Adamson, Oct 23 2007

Extensions

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

Status

approved