Probability Theory: Multinomial coefficients

[WWCY]

<Moderator's note: Moved from homework.>

Hi all, I have an issue understanding a statement I read in my text.

It first states the following Proposition (Let's call it Proposition A):

The number of unordered samples of $r$ objects selected from $n$ objects without replacement is $n \choose r$. In particular,
$$2^n = \sum_{k = 0}^{n} {n \choose k}$$
is the number of subsets of a set of $n$ objects.

$\textbf{Question 1}$: What does "number of subsets of a set of $n$ objects" mean? Does it mean the number of ways I can split n objects into "2 groups/subsets"?

It later (in a separate section) states another Proposition (B):

The number of ways that $n$ objects can be grouped into $r$ classes with $n_i$ in the $i$th class, $i = 1,..,n$, and $\sum_{i=1}^{r} n_i = n$ is
$${n \choose n_1 n_2 ... n_r} = \frac{n!}{n_1 ! n_2 ! ...n_r !}$$
Proposition A is the special case for $r = 2$

$\textbf{Question 2}$: What does "Proposition A is the special case for $r = 2$" mean?

Many thanks in advance.

 

[Orodruin]

What does "number of subsets of a set of nnn objects" mean? Does it mean the number of ways I can split n objects into "2 groups/subsets"?

Yes. Or more precisely, how many different subsets you can construct. When you are constructing a subset you have 2 options for every element (include/not include) and therefore in total $2^n$ different possible choices.

What does "Proposition A is the special case for r=2r=2r = 2" mean?

That it is the number of ways you can split a set into two parts. In other words, you have the set which is your chosen subset and its complement.

 

[Ray Vickson]

<Moderator's note: Moved from homework.>

Hi all, I have an issue understanding a statement I read in my text.

It first states the following Proposition (Let's call it Proposition A):

The number of unordered samples of $r$ objects selected from $n$ objects without replacement is $n \choose r$. In particular,
$$2^n = \sum_{k = 0}^{n} {n \choose k}$$
is the number of subsets of a set of $n$ objects.

$\textbf{Question 1}$: What does "number of subsets of a set of $n$ objects" mean? Does it mean the number of ways I can split n objects into "2 groups/subsets"?

It later (in a separate section) states another Proposition (B):

The number of ways that $n$ objects can be grouped into $r$ classes with $n_i$ in the $i$th class, $i = 1,..,n$, and $\sum_{i=1}^{r} n_i = n$ is
$${n \choose n_1 n_2 ... n_r} = \frac{n!}{n_1 ! n_2 ! ...n_r !}$$
Proposition A is the special case for $r = 2$

$\textbf{Question 2}$: What does "Proposition A is the special case for $r = 2$" mean?

Many thanks in advance.

Try putting $r=2$ and see what you get.

 

[WWCY]

Thanks very much for the responses.

If i set $r = 2$, I get
$$n \choose n_1 n_2$$
which I assume is telling me the number of ways I can split a group of objects into 2 classes, one class with $n_1$ items and the other with $n_2$. However, the expression
$$2^n = \sum_{k = 0}^{n} {n \choose k}$$
tells me the number of ways I can split a group of objects into any two classes, with any number of objects in each class.

Am I understanding the problem correctly or am I still missing something?

Thanks in advance.

 

[Orodruin]

The point is that
$$
{n \choose k} = {n \choose {k,n-k}}
$$

 

[Stephen Tashi]

Am I understanding the problem correctly or am I still missing something?

You understand the situation. As to whether it is literally correct to say that "proposition B is the special case of proposition A", it is true that proposition B can account for each individual term in the sum given by proposition A, but I think it is misleading to say that proposition B is "the" special case of proposition A.


These propositions concern "distinct objects". There are other combinatorial expressions that apply to the paradoxical notion of n "identical" objects. (If they were truly "identical" they would all be the same and we would have 1 object instead of n>1 objects. "Identical" refers to equality with respect to some particular equivalence relation.)

Notice the importance of the phrase "unordered samples". This allows you to count two samples that are the same set as being the same sample since the equality relation for sets does not depend on listing the elements of the set in a particular order.

There are some areas of mathematics where history and tradition have lead to terminology that seems to ignore elementary mathematical concepts like "equivalence relation" and "function". The introduction to Combinatorics is a good example of this. For example, after diligently learning that a "permutation" is an "ordered arrangement" of objects, we will be taught in more advanced courses that a permutation is a function.

 

[WWCY]

Many thanks for your responses, I see it better now!