A362924 - OEIS

%I #24 Dec 02 2023 17:19:43

%S 1,2,1,5,4,1,15,13,8,1,52,47,35,16,1,203,188,153,97,32,1,877,825,706,

%T 515,275,64,1,4140,3937,3479,2744,1785,793,128,1,21147,20270,18313,

%U 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

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

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

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

%H Paolo Xausa, <a href="/A362924/b362924.txt">Table of n, a(n) for n = 1..11325</a> (rows 1..150 of the triangle, flattened).

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

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

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

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

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

%e Triangle begins:

%e   [1],

%e   [2, 1],

%e   [5, 4, 1],

%e   [15, 13, 8, 1],

%e   [52, 47, 35, 16, 1],

%e   [203, 188, 153, 97, 32, 1],

%e   [877, 825, 706, 515, 275, 64, 1],

%e   [4140, 3937, 3479, 2744, 1785, 793, 128, 1],

%e   [21147, 20270, 18313, 15177, 11002, 6347, 2315, 256, 1],

%e   [115975, 111835, 102678, 88033, 68303, 45368, 23073, 6817, 512, 1],

%e   [678570, 657423, 610989, 536882, 436297, 316305, 191866, 85475, 20195, 1024, 1],

%e ...

%e 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

%e   {12,3,4},

%e   {13,2,4},

%e   {14,2,3},

%e   {23,1,4},

%e   {24,1,3},

%e   {34,1,2},

%e   {1,2,3,4},

%e   while

%e   {1234},

%e   {123,4},

%e   {124,3}

%e   {134,2}

%e   {234,1},

%e   {12,34}

%e   {13. 24}.

%e   {14, 23}

%e   do not.

%p with(combinat);

%p T:=proc(n,m) local k;

%p add(stirling2(n-m,k)*(k+1)^m, k=0..n-m);

%p end;

%t A362924[n_,m_]:=Sum[StirlingS2[n-m,k](k+1)^m,{k,0,n-m}];

%t Table[A362924[n,m],{n,15},{m,n}] (* _Paolo Xausa_, Dec 02 2023 *)

%Y See A113547 and A362925 for other versions of this triangle.

%Y Row sums give A005493.

%Y Cf. A000110, A008277, A078468, A143494.

%K nonn,tabl

%O 1,2

%A _N. J. A. Sloane_, Aug 10 2023, based on an email from _Don Knuth_.