cp's OEIS Frontend

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

%I A362924 #26 Jul 09 2025 05:02:03
%S A362924 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 A362924 515,275,64,1,4140,3937,3479,2744,1785,793,128,1,21147,20270,18313,
%U A362924 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 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}.
%C A362924 Also, the maximum number of solutions to an exact cover problem with n items, of which m are secondary.
%D A362924 D. E. Knuth, The Art of Computer Programming, Volume 4B, exercise 7.2.2.1--185, answer on page 468.
%H A362924 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 A362924 T(n, 1) = Bell number (all set partitions) A000110(n);
%F A362924 T(n, n) = 1 when m=n (the only possibility is a single block);
%F A362924 T(n, n-1) = 2^{n-1} when m=n-1 (a single block or two blocks);
%F A362924 T(n, 2) =  A078468(2).
%F A362924 In general, T(n, m) = Sum_{k=0..n-m} Stirling_2(n-m,k)*(k+1)^m.
%e A362924 Triangle begins:
%e A362924   [1],
%e A362924   [2, 1],
%e A362924   [5, 4, 1],
%e A362924   [15, 13, 8, 1],
%e A362924   [52, 47, 35, 16, 1],
%e A362924   [203, 188, 153, 97, 32, 1],
%e A362924   [877, 825, 706, 515, 275, 64, 1],
%e A362924   [4140, 3937, 3479, 2744, 1785, 793, 128, 1],
%e A362924   [21147, 20270, 18313, 15177, 11002, 6347, 2315, 256, 1],
%e A362924   [115975, 111835, 102678, 88033, 68303, 45368, 23073, 6817, 512, 1],
%e A362924   [678570, 657423, 610989, 536882, 436297, 316305, 191866, 85475, 20195, 1024, 1],
%e A362924 ...
%e A362924 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 A362924   {12,3,4},
%e A362924   {13,2,4},
%e A362924   {14,2,3},
%e A362924   {23,1,4},
%e A362924   {24,1,3},
%e A362924   {34,1,2},
%e A362924   {1,2,3,4},
%e A362924   while
%e A362924   {1234},
%e A362924   {123,4},
%e A362924   {124,3}
%e A362924   {134,2}
%e A362924   {234,1},
%e A362924   {12,34}
%e A362924   {13. 24}.
%e A362924   {14, 23}
%e A362924   do not.
%p A362924 with(combinat);
%p A362924 T:=proc(n,m) local k;
%p A362924 add(stirling2(n-m,k)*(k+1)^m, k=0..n-m);
%p A362924 end;
%t A362924 A362924[n_,m_]:=Sum[StirlingS2[n-m,k](k+1)^m,{k,0,n-m}];
%t A362924 Table[A362924[n,m],{n,15},{m,n}] (* _Paolo Xausa_, Dec 02 2023 *)
%Y A362924 See A113547 and A362925 for other versions of this triangle.
%Y A362924 Row sums give A005493.
%Y A362924 Cf. A000110, A008277, A078468, A143494.
%K A362924 nonn,tabl
%O A362924 1,2
%A A362924 _N. J. A. Sloane_, Aug 10 2023, based on an email from _Don Knuth_