A362924 Triangle read by rows: T(n,m), n >= 1, 1 <= m <= n, is number of partitions of the set {1,2,...,n} that have at most one block contained in {1,...,m}.

1, 2, 1, 5, 4, 1, 15, 13, 8, 1, 52, 47, 35, 16, 1, 203, 188, 153, 97, 32, 1, 877, 825, 706, 515, 275, 64, 1, 4140, 3937, 3479, 2744, 1785, 793, 128, 1, 21147, 20270, 18313, 15177, 11002, 6347, 2315, 256, 1, 115975, 111835, 102678, 88033, 68303, 45368, 23073, 6817, 512, 1, 678570, 657423, 610989, 536882, 436297, 316305, 191866, 85475, 20195, 1024, 1

Offset

1,2

Comments

Also, the maximum number of solutions to an exact cover problem with n items, of which m are secondary.

References

D. E. Knuth, The Art of Computer Programming, Volume 4B, exercise 7.2.2.1--185, answer on page 468.

Links

Paolo Xausa, Table of n, a(n) for n = 1..11325 (rows 1..150 of the triangle, flattened).

Formula

T(n, 1) = Bell number (all set partitions) A000110(n);

T(n, n) = 1 when m=n (the only possibility is a single block);

T(n, n-1) = 2^{n-1} when m=n-1 (a single block or two blocks);

T(n, 2) = A078468(2).

In general, T(n, m) = Sum_{k=0..n-m} Stirling_2(n-m,k)*(k+1)^m.

Example

Triangle begins:
  [1],
  [2, 1],
  [5, 4, 1],
  [15, 13, 8, 1],
  [52, 47, 35, 16, 1],
  [203, 188, 153, 97, 32, 1],
  [877, 825, 706, 515, 275, 64, 1],
  [4140, 3937, 3479, 2744, 1785, 793, 128, 1],
  [21147, 20270, 18313, 15177, 11002, 6347, 2315, 256, 1],
  [115975, 111835, 102678, 88033, 68303, 45368, 23073, 6817, 512, 1],
  [678570, 657423, 610989, 536882, 436297, 316305, 191866, 85475, 20195, 1024, 1],
...
For example, if n=4, m=3, then T(4,3) = 8, because out of the A000110(4) = 15 set partitions of {1,2,3,4}, those that have 2 or more blocks contained in {1,2,3} are
  {12,3,4},
  {13,2,4},
  {14,2,3},
  {23,1,4},
  {24,1,3},
  {34,1,2},
  {1,2,3,4},
  while
  {1234},
  {123,4},
  {124,3}
  {134,2}
  {234,1},
  {12,34}
  {13. 24}.
  {14, 23}
  do not.

Maple

with(combinat);
T:=proc(n, m) local k;
add(stirling2(n-m, k)*(k+1)^m, k=0..n-m);
end;

Mathematica

A362924[n_, m_]:=Sum[StirlingS2[n-m, k](k+1)^m, {k, 0, n-m}];
Table[A362924[n, m], {n, 15}, {m, n}] (* Paolo Xausa, Dec 02 2023 *)

Crossrefs

See A113547 and A362925 for other versions of this triangle.

Row sums give A005493.

Cf. A000110, A008277, A078468, A143494.

Sequence in context: A128738 A193673 A126181 * A154930 A104259 A137650

Adjacent sequences: A362921 A362922 A362923 * A362925 A362926 A362927

Keyword

nonn,tabl

Author

N. J. A. Sloane, Aug 10 2023, based on an email from Don Knuth.

Status

approved