A078468 -id:A078468 - cp's OEIS frontend

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

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

Offset: 0

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

A variant of A113547 and A362924. See those entries for further information.

			Triangle begins:
       1;
       1,      1;
       2,      2,      1;
       5,      5,      4,      1;
      15,     15,     13,      8,     1;
      52,     52,     47,     35,    16,     1;
     203,    203,    188,    153,    97,    32,     1;
     877,    877,    825,    706,   515,   275,    64,     1;
    4140,   4140,   3937,   3479,  2744,  1785,   793,   128,    1;
   21147,  21147,  20270,  18313, 15177, 11002,  6347,  2315,  256,   1;
  115975, 115975, 111835, 102678, 88033, 68303, 45368, 23073, 6817, 512, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Row sums are A000110(n+1).
Columns k=0+1,2-5 give A000110, A078468(n-2) (for n>=2), A383052(n-3) (for n>=3), A383053(n-4) (for n>=4), A383054(n-5) (for n>=5).
T(n+j,n) give (for j=0-2): A000012, A000079, A007689.
T(2n,n) gives A367820.
Cf. A040027, A113547, A362924.

T:= (n, k)-> add(Stirling2(n-k, j)*(j+1)^k, j=0..n-k):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Dec 01 2023

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

Sum_{k=0..n} (k+1) * T(n,k) = A040027(n+1). - Alois P. Heinz, Dec 02 2023

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

Original entry on oeis.org

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

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

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

			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.

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

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

See A113547 and A362925 for other versions of this triangle.
Row sums give A005493.
Cf. A000110, A008277, A078468, A143494.

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

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

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.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula