Probability Theory: Multinomial coefficients

  • #1
477
12

Main Question or Discussion Point

<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.
 
Last edited by a moderator:

Answers and Replies

  • #2
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,667
6,450
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.
 
  • #3
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
<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.
 
  • #4
477
12
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.
 
  • #5
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,667
6,450
The point is that
$$
{n \choose k} = {n \choose {k,n-k}}
$$
 
  • #6
Stephen Tashi
Science Advisor
7,016
1,237
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.
 
  • #7
477
12
Many thanks for your responses, I see it better now!
 

Related Threads on Probability Theory: Multinomial coefficients

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
4K
Replies
4
Views
2K
Replies
3
Views
392
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
982
Replies
2
Views
2K
Replies
2
Views
3K
Replies
4
Views
1K
Top