# Number of ways to partition n persons and probability to form n groups

• songoku
Thanks for the clarification on the meaning of "may be empty". I think I understand now. I'll try to work on a solution.In summary, the conversation discusses two problems related to partitioning a group of people into distinct groups. In the first problem, the goal is to find the number of ways to partition n persons into at most r groups, where the groups can be empty. The second problem is similar, but each person can only enroll in one group. The conversation introduces different approaches, including using multinomial coefficients and Stirling numbers, and discusses the challenges of finding a closed form solution for the second problem.
songoku
Homework Statement
1) How many different ways are there to partition n persons into at most r distinct (may be empty) groups?

2) k students can choose (randomly) for themselves which one of the n tutorial groups they want to attend. What is the probability that all tutorial groups have at least one student?
Relevant Equations
Probability

Permutation and Combination
1) At first my answer was ##n!
\begin{pmatrix}
n+r-1 \\
r - 1
\end{pmatrix}
##

But I think that's not correct because let say first group consists of person A and B, by multiplying with n!, I also consider first group to be B and A which is just the same as A and B so there is double counting.

So I am thinking maybe ##
\begin{pmatrix}
~ & ~ n \\
n_1, & n_2, & ... & , n_r
\end{pmatrix}
##

is the answer since it is actually dividing n persons into r groups and eliminating the order inside each group. Is that correct?

2) I feel the question is similar to (1). My answer was
$$\frac {\begin{pmatrix} n -1 \\ k - 1 \end{pmatrix}} { \begin{pmatrix} n +k -1 \\ k - 1 \end{pmatrix} }$$

But I think this has not considered the case where group 1 consists of person A or group 1 consists of person B. I don't think multiplying with n! works. How to get the correct answer?

Thanks

It is unclear to me what you mean with $$\begin{pmatrix} ~ & n \\ n_1, & n_2, & ... & , n_r \end{pmatrix}$$

All I know is ##
\begin{pmatrix}
n \\ k
\end{pmatrix} = \displaystyle {n!\over (n-k)!\; k!}## is the number of ways to pick an unordered subset of ##k## elements out of a set of ##n## (with ## n\ge k\ge 0##).

I had difficulty with understanding "may be empty" -- but the idea is as in 2), I suppose. It means you allow ##r>n##.

The "at most" can be omitted ? And the ##n## persons are distinct, of course ?

I don't think there is a simple expression to answer 1).
You have ##n^r## possibilities before starting to weed out the double counting, which seems a herculean job to me.
Your problem statement for 2) is incomplete. It would be complete if you add that each student can enroll in only one group. Was that the intention? If so, you have a check that the probability should be zero for ##n>k##.
You also want to explicitly state that all groups are equally popular (since that is something that never happens).

An approach to answering could then be coming from the other end: what is the probability that a group stays empty ?And are you intentionally adding to possible confusion by using symbols ##n## and ##r## in 1) for the roles of ##k## and ##n## in 2) ?

##\ ##

Last edited by a moderator:
songoku
BvU said:

It is unclear to me what you mean with $$\begin{pmatrix} ~ & n \\ n_1, & n_2, & ... & , n_r \end{pmatrix}$$

All I know is ##
\begin{pmatrix}
n \\ k
\end{pmatrix} = \displaystyle {n!\over (n-k)!\; k!}## is the number of ways to pick an unordered subset of ##k## elements out of a set of ##n## (with n\ge k\ge 0).

I had difficulty with understanding "may be empty" -- but the idea is as in 2), I suppose. It means you allow ##r>n##.

The "at most" can be omitted ? And the ##n## persons are distinct, of course ?

I don't think there is a simple expression to answer 1).
You have ##n^r## possibilities before starting to weed out the double counting, which seems a herculean job to me.
Your problem statement for 2) is incomplete. It would be complete if you add that each student can enroll in only one group. Was that the intention? If so, you have a check that the probability should be zero for ##n>k##.
You also want to explicitly state that all groups are equally popular (since that is something that never happens).

An approach to answering could then be coming from the other end: what is the probability that a group stays empty ?And are you intentionally adding to possible confusion by using symbols ##n## and ##r## in 1) for the roles of ##k## and ##n## in 2) ?

##\ ##
It's the /a multinomial coefficient, equal to

## \frac {n!}{n_1!n_2!...n_k!}##

Standard example in my experience is the number of words you can form with the letters of " Mississippi ", which is

## \frac {11!}{4!4!2!}##

Given the 4 copies each of the 's', 'i', and the 2 'p's'.
@songoku : Just to be clear, I guess n>r?

songoku and BvU
What confused in this problem statement are words permutation and combination. The problem can be solved by the partitions of a set thinking way. In this case Stirling number can be very useful.

songoku
songoku said:
1) How many different ways are there to partition n persons into at most r distinct (may be empty) groups?

So I am thinking maybe ##
\begin{pmatrix}
~ & ~ n \\
n_1, & n_2, & ... & , n_r
\end{pmatrix}
##
That cannot be the answer since ##n_1, .., n_r## are not givens.
You are overthinking it. It really is very easy.
Try two groups as a start.

For (2), I can get a series sum using the principle of inclusion- exclusion, but don't see how to get it into closed form.
##\Sigma_{s=0}^r{^r}C_s(r-s)^n(-1)^s##

WWGD said:
Just to be clear, I guess n>r?
No need in (1) since the groups can be empty.

Last edited:
songoku and BvU
I am really really sorry for the late reply
BvU said:
I had difficulty with understanding "may be empty" -- but the idea is as in 2), I suppose. It means you allow ##r>n##.
I interpret it as one or several groups can be empty so let say n = 5 and r = 3, I think it is possible that group 1 = 5 persons, group 2 and 3 = 0 or group 1 = 4 persons, group 2 = 1, group 3 = 0
BvU said:
The "at most" can be omitted ? And the ##n## persons are distinct, of course ?
I actually miss the word "at most". Thinking about it now, I am not sure whether I need to consider the several possibility numbers of group, like r , r - 1, r - 2, .... , 1 but I will assume the word "at most" can be omitted.

And ##n## persons should be distinct.

BvU said:
Your problem statement for 2) is incomplete. It would be complete if you add that each student can enroll in only one group. Was that the intention? If so, you have a check that the probability should be zero for ##n>k##.
You also want to explicitly state that all groups are equally popular (since that is something that never happens).
I posted the exact question statement. Maybe that was the intention and while thinking about the solution, that is my assumption: each student can enroll in only one group.

BvU said:
An approach to answering could then be coming from the other end: what is the probability that a group stays empty ?
Do I also need to consider there are 2 groups empty, 3 groups empty up until n - 1 groups empty?

BvU said:
And are you intentionally adding to possible confusion by using symbols ##n## and ##r## in 1) for the roles of ##k## and ##n## in 2) ?
Of course not, that's the original question

WWGD said:
@songoku : Just to be clear, I guess n>r?
Well, the question does not specify this so I am also not sure whether I need to consider separate cases where n > r, n = r, and n < r

Gavran said:
What confused in this problem statement are words permutation and combination. The problem can be solved by the partitions of a set thinking way. In this case Stirling number can be very useful.
The words "Permutation and Combination" is not part of the question. It should be in part "Relevant Equations". I wrote that because this is the question from that chapter.

haruspex said:
That cannot be the answer since ##n_1, .., n_r## are not givens.
You are overthinking it. It really is very easy.
Try two groups as a start.
Let r = 2
1) If n = 1 ---> no. of ways = 2C1 = 2

2) If n = 2
a) one of the groups is empty ---> 2C1 = 2
b) no groups are empty ----> 2! = 2
So total ways = 4

3) If n = 3
a) of the groups is empty ---> 2C1 = 2
b) no groups are empty ---> 3C2 x 2! = 6
So total ways = 8

I think whether n > r or n = r or n < r affects the answer?

haruspex said:
For (2), I can get a series sum using the principle of inclusion- exclusion, but don't see how to get it into closed form.
##\Sigma_{s=0}^r{^r}C_s(r-s)^n(-1)^s##
For (2), do you assume the ##n## tutorial groups to be identical or distinct?

Thanks

haruspex said:
That cannot be the answer since ##n_1, .., n_r## are not givens.
You are overthinking it. It really is very easy.
Try two groups as a start.

For (2), I can get a series sum using the principle of inclusion- exclusion, but don't see how to get it into closed form.
##\Sigma_{s=0}^r{^r}C_s(r-s)^n(-1)^s##

No need in (1) since the groups can be empty.
There's a combinatorial expression involved in the OP, which includes n-1. How should it be addressed when n<1?

songoku said:
I think whether n > r or n = r or n < r affects the answer?
It is one simple formula for all cases. What do your results in post #6 suggest?
songoku said:
For (2), do you assume the n tutorial groups to be identical or distinct?
Distinct, as required. Are you familiar with the inclusion-exclusion principle?
WWGD said:
There's a combinatorial expression involved in the OP, which includes n-1. How should it be addressed when n<1?
Why do you ask me? I have not suggested that expression is correct. There is no ##n-1## in my solution.

PeroK and songoku
haruspex said:
It is one simple formula for all cases. What do your results in post #6 suggest?
From the pattern, I would guess ##r^n##.

Is the logic behind the answer like this: for each person, there are ##r## possibilities to choose the groups

haruspex said:
Distinct, as required. Are you familiar with the inclusion-exclusion principle?
Sorry but no. I will look it up first to get some idea about inclusion-exclusion principle

Thanks

songoku said:
From the pattern, I would guess ##r^n##.

Is the logic behind the answer like this: for each person, there are ##r## possibilities to choose the groups
Yes. And each combination of choices by the different students leads to a different result.

songoku
haruspex said:
For (2), I can get a series sum using the principle of inclusion- exclusion, but don't see how to get it into closed form.
##\Sigma_{s=0}^r{^r}C_s(r-s)^n(-1)^s##
I think I get this.

Thank you very much for the help and explanation BvU, WWGD, Gavran, haruspex

## What is the number of ways to partition n persons into k groups?

The number of ways to partition n persons into k groups is given by the Stirling number of the second kind, denoted as S(n, k). It represents the number of ways to divide a set of n objects into k non-empty subsets.

## How do you calculate the Stirling number of the second kind?

The Stirling number of the second kind, S(n, k), can be calculated using the recursive formula: S(n, k) = k * S(n-1, k) + S(n-1, k-1), with the base cases S(0, 0) = 1, and S(n, 0) = S(0, k) = 0 for n, k > 0.

## What is the probability of forming exactly k groups from n persons?

The probability of forming exactly k groups from n persons, assuming each partition is equally likely, is given by the ratio of the Stirling number of the second kind S(n, k) to the total number of partitions of n, which is the nth Bell number B(n). Therefore, the probability P is P = S(n, k) / B(n).

## What is a Bell number and how is it related to partitions?

A Bell number, denoted as B(n), represents the total number of ways to partition a set of n elements into non-empty subsets. It is the sum of the Stirling numbers of the second kind for all possible k, i.e., B(n) = Σ S(n, k) for k = 1 to n.

## Can you provide an example calculation for a small n and k?

Sure! Let's calculate the number of ways to partition 4 persons into 2 groups. Using the Stirling number of the second kind, S(4, 2) = 7. There are 7 ways to partition 4 persons into 2 groups. If we want to find the probability of forming exactly 2 groups from 4 persons, we use the Bell number B(4) = 15. Therefore, the probability is P = S(4, 2) / B(4) = 7 / 15 ≈ 0.467.

• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
5
Views
3K
• Precalculus Mathematics Homework Help
Replies
5
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
724
• Precalculus Mathematics Homework Help
Replies
13
Views
842
• Precalculus Mathematics Homework Help
Replies
3
Views
804
• Precalculus Mathematics Homework Help
Replies
2
Views
988
• Linear and Abstract Algebra
Replies
2
Views
880