Mixing
How i can solve the combinatorial problem, using only the multiplicative and additive principle?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I have a statement:
In a class of 10 students, $3$ prizes will be awarded.
What is the total combination of awards, if:
$i)$ Each player receives a SINGLE prize and the prizes are different.
$ii)$ Each player receives a SINGLE prize and the prizes are the same.
$iii)$ A player can repeat all the prizes, and the prizes are the same.
Well, my development was:
Let the prizes, be called $A, B, C$
$i)$ The price $A$ have 10 players to be distributed, $B$ have 9 players, $C$ have 8 players, so the total cases are: $10*9*8 = 720$
$ii)$ The same argument for $i)$, but now the order doesn't matter, so I can assume that: $ABC = BCA = CBA$, because $A = B = C $....
Therefore, to undo the repeated combinations i need the permutation of $3$, so the total combinations will be: $frac10*9*83! = 120$
$iii)$ Well, with the formula of $C_repetition(n, r) = frac(n+r-1)!(n-1)!r!$
The result will be: $C_rep(10, 3) = frac12!9!3! = 220$
The three results are good, but with the exercise $iii)$ i have some problems of understanding.
$A)$ ¿How i can get the correct result of the third exercise, using only the multiplicative and additive principle, in a intuitive way?
$B)$ ¿What is the intuitive and the formal proof of the formula: $frac(n+r-1)!(n-1)!r!$ ?
combinatorics
asked Jul 31 at 17:10
Mattiu
759316
 |Â
show 4 more comments
up vote
3
down vote
favorite
I have a statement:
In a class of 10 students, $3$ prizes will be awarded.
What is the total combination of awards, if:
$i)$ Each player receives a SINGLE prize and the prizes are different.
$ii)$ Each player receives a SINGLE prize and the prizes are the same.
$iii)$ A player can repeat all the prizes, and the prizes are the same.
Well, my development was:
Let the prizes, be called $A, B, C$
$i)$ The price $A$ have 10 players to be distributed, $B$ have 9 players, $C$ have 8 players, so the total cases are: $10*9*8 = 720$
$ii)$ The same argument for $i)$, but now the order doesn't matter, so I can assume that: $ABC = BCA = CBA$, because $A = B = C $....
Therefore, to undo the repeated combinations i need the permutation of $3$, so the total combinations will be: $frac10*9*83! = 120$
$iii)$ Well, with the formula of $C_repetition(n, r) = frac(n+r-1)!(n-1)!r!$
The result will be: $C_rep(10, 3) = frac12!9!3! = 220$
The three results are good, but with the exercise $iii)$ i have some problems of understanding.
$A)$ ¿How i can get the correct result of the third exercise, using only the multiplicative and additive principle, in a intuitive way?
$B)$ ¿What is the intuitive and the formal proof of the formula: $frac(n+r-1)!(n-1)!r!$ ?
combinatorics
asked Jul 31 at 17:10
Mattiu
759316
1
There is something I don't get for ii)... if a student only receives 1 prize and the prizes are the same, each student will receive one prize and there is only one way to do it...
– RGS
Jul 31 at 17:12
Do we have $3$ or $10$ prizes? According to your calculations the number of prizes is $3$
– Vasya
Jul 31 at 17:16
Yes $3$ prizes and $10$ students
– Mattiu
Jul 31 at 17:17
Sorry, question edited.
– Mattiu
Jul 31 at 17:17
1
look up "stars and bars" method for #3: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) . You need to distribute 3 stars between 10 bins (9 bars).
– Vasya
Jul 31 at 17:21
 |Â
show 4 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I have a statement:
In a class of 10 students, $3$ prizes will be awarded.
What is the total combination of awards, if:
$i)$ Each player receives a SINGLE prize and the prizes are different.
$ii)$ Each player receives a SINGLE prize and the prizes are the same.
$iii)$ A player can repeat all the prizes, and the prizes are the same.
Well, my development was:
Let the prizes, be called $A, B, C$
$i)$ The price $A$ have 10 players to be distributed, $B$ have 9 players, $C$ have 8 players, so the total cases are: $10*9*8 = 720$
$ii)$ The same argument for $i)$, but now the order doesn't matter, so I can assume that: $ABC = BCA = CBA$, because $A = B = C $....
Therefore, to undo the repeated combinations i need the permutation of $3$, so the total combinations will be: $frac10*9*83! = 120$
$iii)$ Well, with the formula of $C_repetition(n, r) = frac(n+r-1)!(n-1)!r!$
The result will be: $C_rep(10, 3) = frac12!9!3! = 220$
The three results are good, but with the exercise $iii)$ i have some problems of understanding.
$A)$ ¿How i can get the correct result of the third exercise, using only the multiplicative and additive principle, in a intuitive way?
$B)$ ¿What is the intuitive and the formal proof of the formula: $frac(n+r-1)!(n-1)!r!$ ?
combinatorics
asked Jul 31 at 17:10
Mattiu
759316
I have a statement:
In a class of 10 students, $3$ prizes will be awarded.
What is the total combination of awards, if:
$i)$ Each player receives a SINGLE prize and the prizes are different.
$ii)$ Each player receives a SINGLE prize and the prizes are the same.
$iii)$ A player can repeat all the prizes, and the prizes are the same.
Well, my development was:
Let the prizes, be called $A, B, C$
$i)$ The price $A$ have 10 players to be distributed, $B$ have 9 players, $C$ have 8 players, so the total cases are: $10*9*8 = 720$
$ii)$ The same argument for $i)$, but now the order doesn't matter, so I can assume that: $ABC = BCA = CBA$, because $A = B = C $....
Therefore, to undo the repeated combinations i need the permutation of $3$, so the total combinations will be: $frac10*9*83! = 120$
$iii)$ Well, with the formula of $C_repetition(n, r) = frac(n+r-1)!(n-1)!r!$
The result will be: $C_rep(10, 3) = frac12!9!3! = 220$
The three results are good, but with the exercise $iii)$ i have some problems of understanding.
$A)$ ¿How i can get the correct result of the third exercise, using only the multiplicative and additive principle, in a intuitive way?
$B)$ ¿What is the intuitive and the formal proof of the formula: $frac(n+r-1)!(n-1)!r!$ ?
combinatorics
asked Jul 31 at 17:10
Mattiu
759316
edited Jul 31 at 17:57
asked Jul 31 at 17:10
Mattiu
759316
asked Jul 31 at 17:10
Mattiu
759316
asked Jul 31 at 17:10
Mattiu
759316
759316
1
There is something I don't get for ii)... if a student only receives 1 prize and the prizes are the same, each student will receive one prize and there is only one way to do it...
– RGS
Jul 31 at 17:12
Do we have $3$ or $10$ prizes? According to your calculations the number of prizes is $3$
– Vasya
Jul 31 at 17:16
Yes $3$ prizes and $10$ students
– Mattiu
Jul 31 at 17:17
Sorry, question edited.
– Mattiu
Jul 31 at 17:17
1
look up "stars and bars" method for #3: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) . You need to distribute 3 stars between 10 bins (9 bars).
– Vasya
Jul 31 at 17:21
 |Â
show 4 more comments
1
There is something I don't get for ii)... if a student only receives 1 prize and the prizes are the same, each student will receive one prize and there is only one way to do it...
– RGS
Jul 31 at 17:12
Do we have $3$ or $10$ prizes? According to your calculations the number of prizes is $3$
– Vasya
Jul 31 at 17:16
Yes $3$ prizes and $10$ students
– Mattiu
Jul 31 at 17:17
Sorry, question edited.
– Mattiu
Jul 31 at 17:17
1
look up "stars and bars" method for #3: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) . You need to distribute 3 stars between 10 bins (9 bars).
– Vasya
Jul 31 at 17:21
1
1
There is something I don't get for ii)... if a student only receives 1 prize and the prizes are the same, each student will receive one prize and there is only one way to do it...
– RGS
Jul 31 at 17:12
There is something I don't get for ii)... if a student only receives 1 prize and the prizes are the same, each student will receive one prize and there is only one way to do it...
– RGS
Jul 31 at 17:12
Do we have $3$ or $10$ prizes? According to your calculations the number of prizes is $3$
– Vasya
Jul 31 at 17:16
Do we have $3$ or $10$ prizes? According to your calculations the number of prizes is $3$
– Vasya
Jul 31 at 17:16
Yes $3$ prizes and $10$ students
– Mattiu
Jul 31 at 17:17
Yes $3$ prizes and $10$ students
– Mattiu
Jul 31 at 17:17
Sorry, question edited.
– Mattiu
Jul 31 at 17:17
Sorry, question edited.
– Mattiu
Jul 31 at 17:17
1
1
look up "stars and bars" method for #3: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) . You need to distribute 3 stars between 10 bins (9 bars).
– Vasya
Jul 31 at 17:21
look up "stars and bars" method for #3: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) . You need to distribute 3 stars between 10 bins (9 bars).
– Vasya
Jul 31 at 17:21
 |Â
show 4 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
This is a tricky question to answer in general. Consider the following related problem:
There are $n$ distinct people and $r$ distinct hats. Each hat must be placed on a person. It is allowed to stack multiple hats on a single person; in the case, the order of the stack matters.
How many ways are there to place all the hats?
We can solve this using the multiplication principle. Place the hats one at a time, in the order hat 1, hat 2, ... , hat $r$.
- Hat $1$ can be placed in $n$ ways, on any of the $n$ people.
- Hat $2$ can either be placed directly on top of any of the $n$ heads, or on top of hat $1$. This is $n+1$ choices.
- Hat $3$ can be placed on any of of the $n$ heads, or on hat $1$, or on top of hat $2$. This is $n+2$ choices.
You see the pattern. The $i^textth$ hat has $n+i-1$ choices, so the number of ways is
$$
n(n+1)(n+2)cdots (n+r-1)
$$
Now, back to the problem of giving $r$ identical prizes to $n$ distinct people. This is just like the previous problem, but the $r$ items begin given out are no longer distinct. Therefore, we must divide by $r!$ in order to get rid of this over counting, resulting in
$$
fracn(n+1)(n+2)cdots (n+r-1)r!=binomn+r-1r
$$
Note the analogy between cases (i) and (ii); the result for (ii) was obtained by taking the result for (i) and dividing by $3!$ to account for the fact that we do no care about order.
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
Thank you. I understand why you divide between $ r! $ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations.
– Mattiu
Jul 31 at 20:53
@Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$.
– Mike Earnest
Jul 31 at 21:01
@Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer.
– Mike Earnest
Aug 1 at 16:27
Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $ n ^ r $ is not generally divisible by $ r! $ (It looks interesting)
– Mattiu
Aug 1 at 23:30
(1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation.
– Mike Earnest
Aug 1 at 23:56
add a comment |Â
up vote
0
down vote
One way is to break the $iii)$ into three scenarios: 1) Three players get a prize. 2) Two players get a prize (one gets two). 3) One player gets three prizes. Case one is the same as $ii)$. Case two is $10*9$. Case three is simply $10$.
answered Jul 31 at 17:41
Vasya
2,4701514
Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$
– Mattiu
Jul 31 at 19:59
@Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize.
– N. F. Taussig
Jul 31 at 20:22
@N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most
– Vasya
Jul 31 at 20:25
Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination.
– Mattiu
Jul 31 at 20:36
@Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 cdot 1$.
– Vasya
Jul 31 at 20:51
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
This is a tricky question to answer in general. Consider the following related problem:
There are $n$ distinct people and $r$ distinct hats. Each hat must be placed on a person. It is allowed to stack multiple hats on a single person; in the case, the order of the stack matters.
How many ways are there to place all the hats?
We can solve this using the multiplication principle. Place the hats one at a time, in the order hat 1, hat 2, ... , hat $r$.
- Hat $1$ can be placed in $n$ ways, on any of the $n$ people.
- Hat $2$ can either be placed directly on top of any of the $n$ heads, or on top of hat $1$. This is $n+1$ choices.
- Hat $3$ can be placed on any of of the $n$ heads, or on hat $1$, or on top of hat $2$. This is $n+2$ choices.
You see the pattern. The $i^textth$ hat has $n+i-1$ choices, so the number of ways is
$$
n(n+1)(n+2)cdots (n+r-1)
$$
Now, back to the problem of giving $r$ identical prizes to $n$ distinct people. This is just like the previous problem, but the $r$ items begin given out are no longer distinct. Therefore, we must divide by $r!$ in order to get rid of this over counting, resulting in
$$
fracn(n+1)(n+2)cdots (n+r-1)r!=binomn+r-1r
$$
Note the analogy between cases (i) and (ii); the result for (ii) was obtained by taking the result for (i) and dividing by $3!$ to account for the fact that we do no care about order.
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
Thank you. I understand why you divide between $ r! $ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations.
– Mattiu
Jul 31 at 20:53
@Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$.
– Mike Earnest
Jul 31 at 21:01
@Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer.
– Mike Earnest
Aug 1 at 16:27
Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $ n ^ r $ is not generally divisible by $ r! $ (It looks interesting)
– Mattiu
Aug 1 at 23:30
(1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation.
– Mike Earnest
Aug 1 at 23:56
add a comment |Â
up vote
1
down vote
This is a tricky question to answer in general. Consider the following related problem:
There are $n$ distinct people and $r$ distinct hats. Each hat must be placed on a person. It is allowed to stack multiple hats on a single person; in the case, the order of the stack matters.
How many ways are there to place all the hats?
We can solve this using the multiplication principle. Place the hats one at a time, in the order hat 1, hat 2, ... , hat $r$.
- Hat $1$ can be placed in $n$ ways, on any of the $n$ people.
- Hat $2$ can either be placed directly on top of any of the $n$ heads, or on top of hat $1$. This is $n+1$ choices.
- Hat $3$ can be placed on any of of the $n$ heads, or on hat $1$, or on top of hat $2$. This is $n+2$ choices.
You see the pattern. The $i^textth$ hat has $n+i-1$ choices, so the number of ways is
$$
n(n+1)(n+2)cdots (n+r-1)
$$
Now, back to the problem of giving $r$ identical prizes to $n$ distinct people. This is just like the previous problem, but the $r$ items begin given out are no longer distinct. Therefore, we must divide by $r!$ in order to get rid of this over counting, resulting in
$$
fracn(n+1)(n+2)cdots (n+r-1)r!=binomn+r-1r
$$
Note the analogy between cases (i) and (ii); the result for (ii) was obtained by taking the result for (i) and dividing by $3!$ to account for the fact that we do no care about order.
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
Thank you. I understand why you divide between $ r! $ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations.
– Mattiu
Jul 31 at 20:53
@Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$.
– Mike Earnest
Jul 31 at 21:01
@Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer.
– Mike Earnest
Aug 1 at 16:27
Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $ n ^ r $ is not generally divisible by $ r! $ (It looks interesting)
– Mattiu
Aug 1 at 23:30
(1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation.
– Mike Earnest
Aug 1 at 23:56
add a comment |Â
up vote
1
down vote
up vote
1
down vote
This is a tricky question to answer in general. Consider the following related problem:
There are $n$ distinct people and $r$ distinct hats. Each hat must be placed on a person. It is allowed to stack multiple hats on a single person; in the case, the order of the stack matters.
How many ways are there to place all the hats?
We can solve this using the multiplication principle. Place the hats one at a time, in the order hat 1, hat 2, ... , hat $r$.
- Hat $1$ can be placed in $n$ ways, on any of the $n$ people.
- Hat $2$ can either be placed directly on top of any of the $n$ heads, or on top of hat $1$. This is $n+1$ choices.
- Hat $3$ can be placed on any of of the $n$ heads, or on hat $1$, or on top of hat $2$. This is $n+2$ choices.
You see the pattern. The $i^textth$ hat has $n+i-1$ choices, so the number of ways is
$$
n(n+1)(n+2)cdots (n+r-1)
$$
Now, back to the problem of giving $r$ identical prizes to $n$ distinct people. This is just like the previous problem, but the $r$ items begin given out are no longer distinct. Therefore, we must divide by $r!$ in order to get rid of this over counting, resulting in
$$
fracn(n+1)(n+2)cdots (n+r-1)r!=binomn+r-1r
$$
Note the analogy between cases (i) and (ii); the result for (ii) was obtained by taking the result for (i) and dividing by $3!$ to account for the fact that we do no care about order.
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
This is a tricky question to answer in general. Consider the following related problem:
There are $n$ distinct people and $r$ distinct hats. Each hat must be placed on a person. It is allowed to stack multiple hats on a single person; in the case, the order of the stack matters.
How many ways are there to place all the hats?
We can solve this using the multiplication principle. Place the hats one at a time, in the order hat 1, hat 2, ... , hat $r$.
- Hat $1$ can be placed in $n$ ways, on any of the $n$ people.
- Hat $2$ can either be placed directly on top of any of the $n$ heads, or on top of hat $1$. This is $n+1$ choices.
- Hat $3$ can be placed on any of of the $n$ heads, or on hat $1$, or on top of hat $2$. This is $n+2$ choices.
You see the pattern. The $i^textth$ hat has $n+i-1$ choices, so the number of ways is
$$
n(n+1)(n+2)cdots (n+r-1)
$$
Now, back to the problem of giving $r$ identical prizes to $n$ distinct people. This is just like the previous problem, but the $r$ items begin given out are no longer distinct. Therefore, we must divide by $r!$ in order to get rid of this over counting, resulting in
$$
fracn(n+1)(n+2)cdots (n+r-1)r!=binomn+r-1r
$$
Note the analogy between cases (i) and (ii); the result for (ii) was obtained by taking the result for (i) and dividing by $3!$ to account for the fact that we do no care about order.
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
answered Jul 31 at 18:40
Mike Earnest
14.7k11644
14.7k11644
Thank you. I understand why you divide between $ r! $ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations.
– Mattiu
Jul 31 at 20:53
@Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$.
– Mike Earnest
Jul 31 at 21:01
@Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer.
– Mike Earnest
Aug 1 at 16:27
Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $ n ^ r $ is not generally divisible by $ r! $ (It looks interesting)
– Mattiu
Aug 1 at 23:30
(1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation.
– Mike Earnest
Aug 1 at 23:56
add a comment |Â
Thank you. I understand why you divide between $ r! $ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations.
– Mattiu
Jul 31 at 20:53
@Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$.
– Mike Earnest
Jul 31 at 21:01
@Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer.
– Mike Earnest
Aug 1 at 16:27
Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $ n ^ r $ is not generally divisible by $ r! $ (It looks interesting)
– Mattiu
Aug 1 at 23:30
(1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation.
– Mike Earnest
Aug 1 at 23:56
Thank you. I understand why you divide between $ r! $ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations.
– Mattiu
Jul 31 at 20:53
Thank you. I understand why you divide between $ r! $ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations.
– Mattiu
Jul 31 at 20:53
@Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$.
– Mike Earnest
Jul 31 at 21:01
@Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$.
– Mike Earnest
Jul 31 at 21:01
@Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer.
– Mike Earnest
Aug 1 at 16:27
@Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer.
– Mike Earnest
Aug 1 at 16:27
Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $ n ^ r $ is not generally divisible by $ r! $ (It looks interesting)
– Mattiu
Aug 1 at 23:30
Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $ n ^ r $ is not generally divisible by $ r! $ (It looks interesting)
– Mattiu
Aug 1 at 23:30
(1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation.
– Mike Earnest
Aug 1 at 23:56
(1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation.
– Mike Earnest
Aug 1 at 23:56
add a comment |Â
up vote
0
down vote
One way is to break the $iii)$ into three scenarios: 1) Three players get a prize. 2) Two players get a prize (one gets two). 3) One player gets three prizes. Case one is the same as $ii)$. Case two is $10*9$. Case three is simply $10$.
answered Jul 31 at 17:41
Vasya
2,4701514
Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$
– Mattiu
Jul 31 at 19:59
@Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize.
– N. F. Taussig
Jul 31 at 20:22
@N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most
– Vasya
Jul 31 at 20:25
Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination.
– Mattiu
Jul 31 at 20:36
@Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 cdot 1$.
– Vasya
Jul 31 at 20:51
 |Â
show 1 more comment
up vote
0
down vote
One way is to break the $iii)$ into three scenarios: 1) Three players get a prize. 2) Two players get a prize (one gets two). 3) One player gets three prizes. Case one is the same as $ii)$. Case two is $10*9$. Case three is simply $10$.
answered Jul 31 at 17:41
Vasya
2,4701514
Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$
– Mattiu
Jul 31 at 19:59
@Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize.
– N. F. Taussig
Jul 31 at 20:22
@N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most
– Vasya
Jul 31 at 20:25
Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination.
– Mattiu
Jul 31 at 20:36
@Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 cdot 1$.
– Vasya
Jul 31 at 20:51
 |Â
show 1 more comment
up vote
0
down vote
up vote
0
down vote
One way is to break the $iii)$ into three scenarios: 1) Three players get a prize. 2) Two players get a prize (one gets two). 3) One player gets three prizes. Case one is the same as $ii)$. Case two is $10*9$. Case three is simply $10$.
answered Jul 31 at 17:41
Vasya
2,4701514
One way is to break the $iii)$ into three scenarios: 1) Three players get a prize. 2) Two players get a prize (one gets two). 3) One player gets three prizes. Case one is the same as $ii)$. Case two is $10*9$. Case three is simply $10$.
answered Jul 31 at 17:41
Vasya
2,4701514
answered Jul 31 at 17:41
Vasya
2,4701514
answered Jul 31 at 17:41
Vasya
2,4701514
answered Jul 31 at 17:41
Vasya
2,4701514
2,4701514
Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$
– Mattiu
Jul 31 at 19:59
@Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize.
– N. F. Taussig
Jul 31 at 20:22
@N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most
– Vasya
Jul 31 at 20:25
Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination.
– Mattiu
Jul 31 at 20:36
@Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 cdot 1$.
– Vasya
Jul 31 at 20:51
 |Â
show 1 more comment
Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$
– Mattiu
Jul 31 at 19:59
@Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize.
– N. F. Taussig
Jul 31 at 20:22
@N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most
– Vasya
Jul 31 at 20:25
Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination.
– Mattiu
Jul 31 at 20:36
@Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 cdot 1$.
– Vasya
Jul 31 at 20:51
Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$
– Mattiu
Jul 31 at 19:59
Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$
– Mattiu
Jul 31 at 19:59
@Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize.
– N. F. Taussig
Jul 31 at 20:22
@Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize.
– N. F. Taussig
Jul 31 at 20:22
@N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most
– Vasya
Jul 31 at 20:25
@N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most
– Vasya
Jul 31 at 20:25
Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination.
– Mattiu
Jul 31 at 20:36
Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination.
– Mattiu
Jul 31 at 20:36
@Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 cdot 1$.
– Vasya
Jul 31 at 20:51
@Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 cdot 1$.
– Vasya
Jul 31 at 20:51
 |Â
show 1 more comment
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868260%2fhow-i-can-solve-the-combinatorial-problem-using-only-the-multiplicative-and-add%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
There is something I don't get for ii)... if a student only receives 1 prize and the prizes are the same, each student will receive one prize and there is only one way to do it...
– RGS
Jul 31 at 17:12
Do we have $3$ or $10$ prizes? According to your calculations the number of prizes is $3$
– Vasya
Jul 31 at 17:16
Yes $3$ prizes and $10$ students
– Mattiu
Jul 31 at 17:17
Sorry, question edited.
– Mattiu
Jul 31 at 17:17
1
look up "stars and bars" method for #3: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) . You need to distribute 3 stars between 10 bins (9 bars).
– Vasya
Jul 31 at 17:21