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

[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

 

[BvU]

No answers thus far. Let me start with a few considerations:

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

$\$

 

[WWGD]

No answers thus far. Let me start with a few considerations:

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?

 

[Gavran]

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.

 

[haruspex]

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$

Just to be clear, I guess n>r?

No need in (1) since the groups can be empty.

 

[songoku]

I am really really sorry for the late reply

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

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.

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.

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?

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

@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

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.

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?

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

 

[WWGD]

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?

 

[haruspex]

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?

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?

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.

 

[songoku]

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

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

 

[haruspex]

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]

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