A078468 -id:A078468

The OEIS is supported by the many generous donors to the OEIS Foundation.

Search: a078468 -id:a078468

Displaying 1-2 of 2 results found.

page 1

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

+10
5

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

(list; table; graph; refs; listen; history; text; internal format)

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.

KEYWORD

nonn,tabl

AUTHOR

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

STATUS

approved

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

+10
4

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

Triangle begins:

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;

...

MAPLE

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

MATHEMATICA

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

CROSSREFS

Row sums are A000110(n+1).

Column k=0 gives A000110.

Column k=2 gives A078468(n-2) for n>=2.

T(n+j,n) give (for j=0-2): A000012, A000079, A007689.

T(2n,n) gives A367820.

Cf. A040027, A113547, A362924.