Counting the number of partitions

[Tolja]

Hi,

I am interested in counting the number of partitions of a set of size
n (http://en.wikipedia.org/wiki/Partition_of_a_set) while restricting
the maximum subset size to k.

Example:a 3-element set {a, b, c} can be partitioned in 4 distinct
ways when k=2
{ {a}, {b}, {c} }
{ {a}, {b, c} }
{ {b}, {a, c} }
{ {c}, {a, b} }

The solution { {a, b, c} }.is not possible.

Thanks,
Tolja

[Dr. Wolfgang Hintze]

S2(n,k) enumerates partitions of an n-set into k non-empty subsets
(where S2 are called Stirling numbers of the second kind).
See http://oeis.org/ A008277

The first few numbers are

1;

1, 1;

1, 3, 1;

1, 7, 6, 1;

1, 15, 25, 10, 1;

1, 31, 90, 65, 15, 1;

1, 63, 301, 350, 140, 21, 1;

1, 127, 966, 1701, 1050, 266, 28, 1;

1, 255, 3025, 7770, 6951, 2646, 462, 36, 1;

1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1;



You are probably looking for the sum of each row up to m<=k. These are
not contained in OEIS for k<n.

If m=n the numbers are called Bell numbers (OEIS A000110).



Hope this helps.



--- Wolfgang



"Tolja" <tzu...@gmail.com> schrieb im Newsbeitrag
news:3fbcd58b-8d18-46ce...@i19g2000yqa.googlegroups.com...