Wikipedia:Reference desk/Archives/Mathematics/2021 June 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 29

Number of ways to split N people into k groups of at least m

(Inspired by the random number game above.)

The number of ways to partition N elements among exactly k sets is the Stirling number of the second kind. What if I impose that each set must be at least of size m? (For bonus points: what if it must be at least of size m, and at most of size M?)

I thought of the following recursion: denoting that number by $P_{m}(N,k)$, look over all possible sizes j of the group in which the first element is, then we must group j-1 other elements among the rest with it, and we have $P_{m}(N-j,k-1)$ ways to arrange the rest. You need to fix the first element in the group you split off, otherwise different sequences of splits might lead to the same final partition and you would have multiple counting. Hence $P(N,k,m)=\sum _{j=m}^{N-m}C(j-1,N-1)P_{m}(N-j,k-1)$. The initialisation is fairly trivial: $P_{m}(N,1)$ is 0 if N<m, 1 otherwise. Assuming the reasoning is correct, that formula looks like the kind of stuff where one could get a non-recursive formulation... Tigraan^{Click here for my talk page ("private" contact)} 12:48, 29 June 2021 (UTC)

See associated Stirling numbers for your first question.--2406:E003:855:9A01:B15B:27D4:E79:599E (talk) 14:54, 29 June 2021 (UTC)