Mixing
permutations/combinations with repeated symbols
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I've been learning some about counting and basic combinatorics. But some scenarios were not explained in my class...
Example problem: You are given 6 tiles. 1 is labeled "1", 2 are labeled "2", and 3 are labeled "3".
Problem 1: How many different ways can you arrange groups of three tiles (order matters)?
Answer 1: 19, 1,2,2 1,2,3 1,3,2 1,3,3 2,1,2 2,1,3 2,2,1 2,2,3 2,3,1 2,3,2 2,3,3 3,1,2 3,1,3 3,2,1 3,2,2 3,2,3 3,3,1 3,3,2 3,3,3.
Question 1: You can't use the normal $frac5!left(5-3right)!$ because you have repeated symbols. And you can't divide by the factorials of repeated symbols $frac6!left(6-3right)!cdot3!cdot2!$ like you can when n = k and you make different arrangements of all n of symbols $fracn!prod_i=1^mn_i$. What formula would be used to find the answer to a more complex version of this problem?
Problem 2: How many different ways can you make groups of three tiles (order doesn't matter)?
Answer 2: 6, 1,2,2 1,2,3 1,3,3 2,2,3 2,3,3 3,3,3.
Question 2: You can't use the normal $fracn!left(n-kright)!cdot k!$ because you have repeated symbols. What formula would be used to find the answer to a more complex version of this problem?
combinatorics permutations combinations
asked Jul 19 at 1:44
Elliot Trilling
234
add a comment |Â
up vote
2
down vote
favorite
I've been learning some about counting and basic combinatorics. But some scenarios were not explained in my class...
Example problem: You are given 6 tiles. 1 is labeled "1", 2 are labeled "2", and 3 are labeled "3".
Problem 1: How many different ways can you arrange groups of three tiles (order matters)?
Answer 1: 19, 1,2,2 1,2,3 1,3,2 1,3,3 2,1,2 2,1,3 2,2,1 2,2,3 2,3,1 2,3,2 2,3,3 3,1,2 3,1,3 3,2,1 3,2,2 3,2,3 3,3,1 3,3,2 3,3,3.
Question 1: You can't use the normal $frac5!left(5-3right)!$ because you have repeated symbols. And you can't divide by the factorials of repeated symbols $frac6!left(6-3right)!cdot3!cdot2!$ like you can when n = k and you make different arrangements of all n of symbols $fracn!prod_i=1^mn_i$. What formula would be used to find the answer to a more complex version of this problem?
Problem 2: How many different ways can you make groups of three tiles (order doesn't matter)?
Answer 2: 6, 1,2,2 1,2,3 1,3,3 2,2,3 2,3,3 3,3,3.
Question 2: You can't use the normal $fracn!left(n-kright)!cdot k!$ because you have repeated symbols. What formula would be used to find the answer to a more complex version of this problem?
combinatorics permutations combinations
asked Jul 19 at 1:44
Elliot Trilling
234
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I've been learning some about counting and basic combinatorics. But some scenarios were not explained in my class...
Example problem: You are given 6 tiles. 1 is labeled "1", 2 are labeled "2", and 3 are labeled "3".
Problem 1: How many different ways can you arrange groups of three tiles (order matters)?
Answer 1: 19, 1,2,2 1,2,3 1,3,2 1,3,3 2,1,2 2,1,3 2,2,1 2,2,3 2,3,1 2,3,2 2,3,3 3,1,2 3,1,3 3,2,1 3,2,2 3,2,3 3,3,1 3,3,2 3,3,3.
Question 1: You can't use the normal $frac5!left(5-3right)!$ because you have repeated symbols. And you can't divide by the factorials of repeated symbols $frac6!left(6-3right)!cdot3!cdot2!$ like you can when n = k and you make different arrangements of all n of symbols $fracn!prod_i=1^mn_i$. What formula would be used to find the answer to a more complex version of this problem?
Problem 2: How many different ways can you make groups of three tiles (order doesn't matter)?
Answer 2: 6, 1,2,2 1,2,3 1,3,3 2,2,3 2,3,3 3,3,3.
Question 2: You can't use the normal $fracn!left(n-kright)!cdot k!$ because you have repeated symbols. What formula would be used to find the answer to a more complex version of this problem?
combinatorics permutations combinations
asked Jul 19 at 1:44
Elliot Trilling
234
I've been learning some about counting and basic combinatorics. But some scenarios were not explained in my class...
Example problem: You are given 6 tiles. 1 is labeled "1", 2 are labeled "2", and 3 are labeled "3".
Problem 1: How many different ways can you arrange groups of three tiles (order matters)?
Answer 1: 19, 1,2,2 1,2,3 1,3,2 1,3,3 2,1,2 2,1,3 2,2,1 2,2,3 2,3,1 2,3,2 2,3,3 3,1,2 3,1,3 3,2,1 3,2,2 3,2,3 3,3,1 3,3,2 3,3,3.
Question 1: You can't use the normal $frac5!left(5-3right)!$ because you have repeated symbols. And you can't divide by the factorials of repeated symbols $frac6!left(6-3right)!cdot3!cdot2!$ like you can when n = k and you make different arrangements of all n of symbols $fracn!prod_i=1^mn_i$. What formula would be used to find the answer to a more complex version of this problem?
Problem 2: How many different ways can you make groups of three tiles (order doesn't matter)?
Answer 2: 6, 1,2,2 1,2,3 1,3,3 2,2,3 2,3,3 3,3,3.
Question 2: You can't use the normal $fracn!left(n-kright)!cdot k!$ because you have repeated symbols. What formula would be used to find the answer to a more complex version of this problem?
combinatorics permutations combinations
asked Jul 19 at 1:44
Elliot Trilling
234
asked Jul 19 at 1:44
Elliot Trilling
234
asked Jul 19 at 1:44
Elliot Trilling
234
asked Jul 19 at 1:44
Elliot Trilling
234
234
add a comment |Â
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
2
down vote
accepted
Not sure this is the best method, but the way I would actually solve such a set of questions would be the following:
Use generating function methods for the second question.
The explicit collection of submultisets of the six tiles is given by the terms of $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ (the $x$ terms correspond to tile 1, $y$ terms to copies of tile 2, and $z$ terms to copies of tile 3), and the numbers of submultisets of a given size are given ignoring the labels of the tiles and just multiplying the polynomials
$$(1+x)(1+x+x^2)(1+x+x^2+x^3)=(1+2x+2x^2+x^3)(1+x+x^2+x^3)$$
$$= 1+(1+2)x+(1+2+2)x^2+(1+2+2+1)x^3+(2+2+1)x^4+(2+1)x^5+x^6$$
$$=1+3x+5x^2+6x^3+5x^4+3x^5+x^6.$$
Looking at the coefficient of $x^3$ in the product tells us that there are 6 submultisets.
Now the question of ordered triples drawn from the multiset is a little more difficult. I think I'd work out the explicit submultisets of size 3 first. I.e. solve question 2, then compute the number of ways to order each submultiset. There are a couple algorithmic methods to compute the submultisets of size 3. The first would be to multiply out the polynomials $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ and compute the degree 3 terms. The others are essentially equivalent, but drop the mention of polynomials, and I find the polynomials are a helpful computational aide.
Now because I only want the degree three terms, I'll only compute those.
We have $$[(1+x)(1+y+y^2)(1+z+z^2+z^3)]_3$$
$$=1[(1+y+y^2)(1+z+z^2+z^3)]_3 + x[(1+y+y^2)(1+z+z^2+z^3)]_2$$
$$=1(z^3+yz^2+y^2z) + x(z^2+yz+y^2)$$
$$=z^3+yz^2+y^2z+xz^2+xyz+xy^2,$$
corresponding to submultisets
$newcommandmultset[1]#1multset3,3,3,multset2,3,3,multset2,2,3,multset1,3,3,multset1,2,3,$ and $multset1,2,2$.
Now we can work out how many ways there are to order each multiset in the usual manner: the ways to order a multiset of the form $multseta,a,a$ is $3!/3!=1$, $multseta,a,b=3!/2!=3$, and $multseta,b,c=3!=6$. Thus summing the number of ways to order each of our multisets, we get $1+3+3+3+6+3 = 19$ different ordered triples drawn from our multiset.
answered Jul 19 at 3:47
jgon
8,54611435
That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically?
– Elliot Trilling
Jul 19 at 8:06
@Elliot Trilling, I do not know of a simple mathematical formula in either case, so I settle for an algorithm, which at least will let me solve any instance of this problem in a unified way (even if it may not be very fast).
– jgon
Jul 19 at 10:55
add a comment |Â
up vote
1
down vote
Don't try to find a new formula every time you encounter a new counting problem! Counting problems have many variations so it's better if you know how to count rather than knowing the formula. For example, formulas for combinations and permutations are essentially coming from Rule of Product, where you give yourself a procedure to construct the objects that you want to count.
Thus, when facing a counting problem, ask yourself a question:
How do you construct the objects?
Let's take an example as your first problem. Your objects can be divided
into three main cases:
Case $1$: If all three tiles have different labels, i.e. your set contains $1,2,3$ so this is a permutation problem which gives the answer of $3!=6$.
Case $2$: If two of the three tiles have same label. Such tile can either be $3$ or $2$ so there are two ways to choose such tile. After choosing a tile to appear $2$ times, we need to choose the remaining tile with different label. There are $2$ ways to do this. After that, we need to order the three tiles. Since two of the tiles have same label so there are $frac3!2!$ permutation. This case gives $2 cdot 2 cdot frac3!2!=12$.
Case $3$: All three tiles have same label. This is just $(3,3,3)$ so there is one tile in this case.
Summing up, you get $6+12+1=19$.
answered Jul 19 at 3:39
Tengu
2,3391920
add a comment |Â
up vote
0
down vote
Question 1:
This is the same as finding the number of permutations of the 'word' $ABBCCC$. Let us distinguish the same letters by subscripts so that we now have $A_1B_1B_2C_1C_2C_3$. The number of of permutations of this is just $6!$. But for each valid permutation, there are $2!3!$ repeats due to permutations of the $B_i$ and $C_i$. Therefore our answer is $frac6!2!3!=60$.
Question 2:
My best guess is organized casework.
answered Jul 19 at 3:18
Shrey Joshi
1389
Note that the answer to question 1 is given by the OP and is 19, since it only asks for ordered triples of 3 symbols not ways to arrange all the tiles.
– jgon
Jul 19 at 3:28
add a comment |Â
up vote
0
down vote
For the case where order does not matter.
Suppose you have $x$, $y$, and $z$ objects A, B and C respectively. You are choosing $k$ tiles.
If $k-(y+z)>0$, then you need to pick at least $(k-(y+z))$ of object A. Otherwise, at least zero.
For $i$ of object A chosen, you must choose $(k-i)$ of objects B and C combined.
If $(k-i)-z>0$, then you need to pick at least $((k-i)-z)$ of object B. Otherwise, at least zero.
For $j$ of object B chosen, you must choose $(k-(i+j))$ of object C.
In total, you have $i$ of object A, $j$ of object B, and $(k-(i+j))$ of object C.
If order does not matter, you permute the chosen $k$ objects and account for the identical objects.
$$sum_i=max0,k-(y+z)^i=mink,xsum_j=max0,(k-i)-z^i=mink-i,ydfrack!i!j!(k-i-j)!$$
For the case where order matters
We don't really have a formula for this. But an organized method is more crucial.
Check if any of $x,y,z$ is less than $k$. Those that are equal or more than $k$ is in excess supply and we don't worry about them. Those that is less than $k$ introduces cases.
For your case, let me rename some stuff. You have 1 A, 2 B's and 3 C's. The limiting agents are $A$ and $B$.
So we consider all pairs of $(a,b)$ such that $0le a+b le k$. For your case, we have
$$(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)$$
beginarrayc
(a,b) & textnumber of ways \
hline
(0,0) & frac3!3!=1\
(0,1) & frac3!2!=3\
(0,2) & frac3!2!=3\
(1,0) & frac3!2!=3 \
(1,1) & 3!=6\
(1,2) & frac3!2!=3\
endarray
Total: 19 ways.
Of course you can derive a summation from this, but a generalized summation is not very worth deriving unless you have a specific context.
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Not sure this is the best method, but the way I would actually solve such a set of questions would be the following:
Use generating function methods for the second question.
The explicit collection of submultisets of the six tiles is given by the terms of $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ (the $x$ terms correspond to tile 1, $y$ terms to copies of tile 2, and $z$ terms to copies of tile 3), and the numbers of submultisets of a given size are given ignoring the labels of the tiles and just multiplying the polynomials
$$(1+x)(1+x+x^2)(1+x+x^2+x^3)=(1+2x+2x^2+x^3)(1+x+x^2+x^3)$$
$$= 1+(1+2)x+(1+2+2)x^2+(1+2+2+1)x^3+(2+2+1)x^4+(2+1)x^5+x^6$$
$$=1+3x+5x^2+6x^3+5x^4+3x^5+x^6.$$
Looking at the coefficient of $x^3$ in the product tells us that there are 6 submultisets.
Now the question of ordered triples drawn from the multiset is a little more difficult. I think I'd work out the explicit submultisets of size 3 first. I.e. solve question 2, then compute the number of ways to order each submultiset. There are a couple algorithmic methods to compute the submultisets of size 3. The first would be to multiply out the polynomials $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ and compute the degree 3 terms. The others are essentially equivalent, but drop the mention of polynomials, and I find the polynomials are a helpful computational aide.
Now because I only want the degree three terms, I'll only compute those.
We have $$[(1+x)(1+y+y^2)(1+z+z^2+z^3)]_3$$
$$=1[(1+y+y^2)(1+z+z^2+z^3)]_3 + x[(1+y+y^2)(1+z+z^2+z^3)]_2$$
$$=1(z^3+yz^2+y^2z) + x(z^2+yz+y^2)$$
$$=z^3+yz^2+y^2z+xz^2+xyz+xy^2,$$
corresponding to submultisets
$newcommandmultset[1]#1multset3,3,3,multset2,3,3,multset2,2,3,multset1,3,3,multset1,2,3,$ and $multset1,2,2$.
Now we can work out how many ways there are to order each multiset in the usual manner: the ways to order a multiset of the form $multseta,a,a$ is $3!/3!=1$, $multseta,a,b=3!/2!=3$, and $multseta,b,c=3!=6$. Thus summing the number of ways to order each of our multisets, we get $1+3+3+3+6+3 = 19$ different ordered triples drawn from our multiset.
answered Jul 19 at 3:47
jgon
8,54611435
That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically?
– Elliot Trilling
Jul 19 at 8:06
@Elliot Trilling, I do not know of a simple mathematical formula in either case, so I settle for an algorithm, which at least will let me solve any instance of this problem in a unified way (even if it may not be very fast).
– jgon
Jul 19 at 10:55
add a comment |Â
up vote
2
down vote
accepted
Not sure this is the best method, but the way I would actually solve such a set of questions would be the following:
Use generating function methods for the second question.
The explicit collection of submultisets of the six tiles is given by the terms of $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ (the $x$ terms correspond to tile 1, $y$ terms to copies of tile 2, and $z$ terms to copies of tile 3), and the numbers of submultisets of a given size are given ignoring the labels of the tiles and just multiplying the polynomials
$$(1+x)(1+x+x^2)(1+x+x^2+x^3)=(1+2x+2x^2+x^3)(1+x+x^2+x^3)$$
$$= 1+(1+2)x+(1+2+2)x^2+(1+2+2+1)x^3+(2+2+1)x^4+(2+1)x^5+x^6$$
$$=1+3x+5x^2+6x^3+5x^4+3x^5+x^6.$$
Looking at the coefficient of $x^3$ in the product tells us that there are 6 submultisets.
Now the question of ordered triples drawn from the multiset is a little more difficult. I think I'd work out the explicit submultisets of size 3 first. I.e. solve question 2, then compute the number of ways to order each submultiset. There are a couple algorithmic methods to compute the submultisets of size 3. The first would be to multiply out the polynomials $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ and compute the degree 3 terms. The others are essentially equivalent, but drop the mention of polynomials, and I find the polynomials are a helpful computational aide.
Now because I only want the degree three terms, I'll only compute those.
We have $$[(1+x)(1+y+y^2)(1+z+z^2+z^3)]_3$$
$$=1[(1+y+y^2)(1+z+z^2+z^3)]_3 + x[(1+y+y^2)(1+z+z^2+z^3)]_2$$
$$=1(z^3+yz^2+y^2z) + x(z^2+yz+y^2)$$
$$=z^3+yz^2+y^2z+xz^2+xyz+xy^2,$$
corresponding to submultisets
$newcommandmultset[1]#1multset3,3,3,multset2,3,3,multset2,2,3,multset1,3,3,multset1,2,3,$ and $multset1,2,2$.
Now we can work out how many ways there are to order each multiset in the usual manner: the ways to order a multiset of the form $multseta,a,a$ is $3!/3!=1$, $multseta,a,b=3!/2!=3$, and $multseta,b,c=3!=6$. Thus summing the number of ways to order each of our multisets, we get $1+3+3+3+6+3 = 19$ different ordered triples drawn from our multiset.
answered Jul 19 at 3:47
jgon
8,54611435
That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically?
– Elliot Trilling
Jul 19 at 8:06
@Elliot Trilling, I do not know of a simple mathematical formula in either case, so I settle for an algorithm, which at least will let me solve any instance of this problem in a unified way (even if it may not be very fast).
– jgon
Jul 19 at 10:55
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Not sure this is the best method, but the way I would actually solve such a set of questions would be the following:
Use generating function methods for the second question.
The explicit collection of submultisets of the six tiles is given by the terms of $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ (the $x$ terms correspond to tile 1, $y$ terms to copies of tile 2, and $z$ terms to copies of tile 3), and the numbers of submultisets of a given size are given ignoring the labels of the tiles and just multiplying the polynomials
$$(1+x)(1+x+x^2)(1+x+x^2+x^3)=(1+2x+2x^2+x^3)(1+x+x^2+x^3)$$
$$= 1+(1+2)x+(1+2+2)x^2+(1+2+2+1)x^3+(2+2+1)x^4+(2+1)x^5+x^6$$
$$=1+3x+5x^2+6x^3+5x^4+3x^5+x^6.$$
Looking at the coefficient of $x^3$ in the product tells us that there are 6 submultisets.
Now the question of ordered triples drawn from the multiset is a little more difficult. I think I'd work out the explicit submultisets of size 3 first. I.e. solve question 2, then compute the number of ways to order each submultiset. There are a couple algorithmic methods to compute the submultisets of size 3. The first would be to multiply out the polynomials $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ and compute the degree 3 terms. The others are essentially equivalent, but drop the mention of polynomials, and I find the polynomials are a helpful computational aide.
Now because I only want the degree three terms, I'll only compute those.
We have $$[(1+x)(1+y+y^2)(1+z+z^2+z^3)]_3$$
$$=1[(1+y+y^2)(1+z+z^2+z^3)]_3 + x[(1+y+y^2)(1+z+z^2+z^3)]_2$$
$$=1(z^3+yz^2+y^2z) + x(z^2+yz+y^2)$$
$$=z^3+yz^2+y^2z+xz^2+xyz+xy^2,$$
corresponding to submultisets
$newcommandmultset[1]#1multset3,3,3,multset2,3,3,multset2,2,3,multset1,3,3,multset1,2,3,$ and $multset1,2,2$.
Now we can work out how many ways there are to order each multiset in the usual manner: the ways to order a multiset of the form $multseta,a,a$ is $3!/3!=1$, $multseta,a,b=3!/2!=3$, and $multseta,b,c=3!=6$. Thus summing the number of ways to order each of our multisets, we get $1+3+3+3+6+3 = 19$ different ordered triples drawn from our multiset.
answered Jul 19 at 3:47
jgon
8,54611435
Not sure this is the best method, but the way I would actually solve such a set of questions would be the following:
Use generating function methods for the second question.
The explicit collection of submultisets of the six tiles is given by the terms of $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ (the $x$ terms correspond to tile 1, $y$ terms to copies of tile 2, and $z$ terms to copies of tile 3), and the numbers of submultisets of a given size are given ignoring the labels of the tiles and just multiplying the polynomials
$$(1+x)(1+x+x^2)(1+x+x^2+x^3)=(1+2x+2x^2+x^3)(1+x+x^2+x^3)$$
$$= 1+(1+2)x+(1+2+2)x^2+(1+2+2+1)x^3+(2+2+1)x^4+(2+1)x^5+x^6$$
$$=1+3x+5x^2+6x^3+5x^4+3x^5+x^6.$$
Looking at the coefficient of $x^3$ in the product tells us that there are 6 submultisets.
Now the question of ordered triples drawn from the multiset is a little more difficult. I think I'd work out the explicit submultisets of size 3 first. I.e. solve question 2, then compute the number of ways to order each submultiset. There are a couple algorithmic methods to compute the submultisets of size 3. The first would be to multiply out the polynomials $(1+x)(1+y+y^2)(1+z+z^2+z^3)$ and compute the degree 3 terms. The others are essentially equivalent, but drop the mention of polynomials, and I find the polynomials are a helpful computational aide.
Now because I only want the degree three terms, I'll only compute those.
We have $$[(1+x)(1+y+y^2)(1+z+z^2+z^3)]_3$$
$$=1[(1+y+y^2)(1+z+z^2+z^3)]_3 + x[(1+y+y^2)(1+z+z^2+z^3)]_2$$
$$=1(z^3+yz^2+y^2z) + x(z^2+yz+y^2)$$
$$=z^3+yz^2+y^2z+xz^2+xyz+xy^2,$$
corresponding to submultisets
$newcommandmultset[1]#1multset3,3,3,multset2,3,3,multset2,2,3,multset1,3,3,multset1,2,3,$ and $multset1,2,2$.
Now we can work out how many ways there are to order each multiset in the usual manner: the ways to order a multiset of the form $multseta,a,a$ is $3!/3!=1$, $multseta,a,b=3!/2!=3$, and $multseta,b,c=3!=6$. Thus summing the number of ways to order each of our multisets, we get $1+3+3+3+6+3 = 19$ different ordered triples drawn from our multiset.
answered Jul 19 at 3:47
jgon
8,54611435
answered Jul 19 at 3:47
jgon
8,54611435
answered Jul 19 at 3:47
jgon
8,54611435
answered Jul 19 at 3:47
jgon
8,54611435
8,54611435
That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically?
– Elliot Trilling
Jul 19 at 8:06
@Elliot Trilling, I do not know of a simple mathematical formula in either case, so I settle for an algorithm, which at least will let me solve any instance of this problem in a unified way (even if it may not be very fast).
– jgon
Jul 19 at 10:55
add a comment |Â
That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically?
– Elliot Trilling
Jul 19 at 8:06
@Elliot Trilling, I do not know of a simple mathematical formula in either case, so I settle for an algorithm, which at least will let me solve any instance of this problem in a unified way (even if it may not be very fast).
– jgon
Jul 19 at 10:55
That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically?
– Elliot Trilling
Jul 19 at 8:06
That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically?
– Elliot Trilling
Jul 19 at 8:06
@Elliot Trilling, I do not know of a simple mathematical formula in either case, so I settle for an algorithm, which at least will let me solve any instance of this problem in a unified way (even if it may not be very fast).
– jgon
Jul 19 at 10:55
@Elliot Trilling, I do not know of a simple mathematical formula in either case, so I settle for an algorithm, which at least will let me solve any instance of this problem in a unified way (even if it may not be very fast).
– jgon
Jul 19 at 10:55
add a comment |Â
up vote
1
down vote
Don't try to find a new formula every time you encounter a new counting problem! Counting problems have many variations so it's better if you know how to count rather than knowing the formula. For example, formulas for combinations and permutations are essentially coming from Rule of Product, where you give yourself a procedure to construct the objects that you want to count.
Thus, when facing a counting problem, ask yourself a question:
How do you construct the objects?
Let's take an example as your first problem. Your objects can be divided
into three main cases:
Case $1$: If all three tiles have different labels, i.e. your set contains $1,2,3$ so this is a permutation problem which gives the answer of $3!=6$.
Case $2$: If two of the three tiles have same label. Such tile can either be $3$ or $2$ so there are two ways to choose such tile. After choosing a tile to appear $2$ times, we need to choose the remaining tile with different label. There are $2$ ways to do this. After that, we need to order the three tiles. Since two of the tiles have same label so there are $frac3!2!$ permutation. This case gives $2 cdot 2 cdot frac3!2!=12$.
Case $3$: All three tiles have same label. This is just $(3,3,3)$ so there is one tile in this case.
Summing up, you get $6+12+1=19$.
answered Jul 19 at 3:39
Tengu
2,3391920
add a comment |Â
up vote
1
down vote
Don't try to find a new formula every time you encounter a new counting problem! Counting problems have many variations so it's better if you know how to count rather than knowing the formula. For example, formulas for combinations and permutations are essentially coming from Rule of Product, where you give yourself a procedure to construct the objects that you want to count.
Thus, when facing a counting problem, ask yourself a question:
How do you construct the objects?
Let's take an example as your first problem. Your objects can be divided
into three main cases:
Case $1$: If all three tiles have different labels, i.e. your set contains $1,2,3$ so this is a permutation problem which gives the answer of $3!=6$.
Case $2$: If two of the three tiles have same label. Such tile can either be $3$ or $2$ so there are two ways to choose such tile. After choosing a tile to appear $2$ times, we need to choose the remaining tile with different label. There are $2$ ways to do this. After that, we need to order the three tiles. Since two of the tiles have same label so there are $frac3!2!$ permutation. This case gives $2 cdot 2 cdot frac3!2!=12$.
Case $3$: All three tiles have same label. This is just $(3,3,3)$ so there is one tile in this case.
Summing up, you get $6+12+1=19$.
answered Jul 19 at 3:39
Tengu
2,3391920
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Don't try to find a new formula every time you encounter a new counting problem! Counting problems have many variations so it's better if you know how to count rather than knowing the formula. For example, formulas for combinations and permutations are essentially coming from Rule of Product, where you give yourself a procedure to construct the objects that you want to count.
Thus, when facing a counting problem, ask yourself a question:
How do you construct the objects?
Let's take an example as your first problem. Your objects can be divided
into three main cases:
Case $1$: If all three tiles have different labels, i.e. your set contains $1,2,3$ so this is a permutation problem which gives the answer of $3!=6$.
Case $2$: If two of the three tiles have same label. Such tile can either be $3$ or $2$ so there are two ways to choose such tile. After choosing a tile to appear $2$ times, we need to choose the remaining tile with different label. There are $2$ ways to do this. After that, we need to order the three tiles. Since two of the tiles have same label so there are $frac3!2!$ permutation. This case gives $2 cdot 2 cdot frac3!2!=12$.
Case $3$: All three tiles have same label. This is just $(3,3,3)$ so there is one tile in this case.
Summing up, you get $6+12+1=19$.
answered Jul 19 at 3:39
Tengu
2,3391920
Don't try to find a new formula every time you encounter a new counting problem! Counting problems have many variations so it's better if you know how to count rather than knowing the formula. For example, formulas for combinations and permutations are essentially coming from Rule of Product, where you give yourself a procedure to construct the objects that you want to count.
Thus, when facing a counting problem, ask yourself a question:
How do you construct the objects?
Let's take an example as your first problem. Your objects can be divided
into three main cases:
Case $1$: If all three tiles have different labels, i.e. your set contains $1,2,3$ so this is a permutation problem which gives the answer of $3!=6$.
Case $2$: If two of the three tiles have same label. Such tile can either be $3$ or $2$ so there are two ways to choose such tile. After choosing a tile to appear $2$ times, we need to choose the remaining tile with different label. There are $2$ ways to do this. After that, we need to order the three tiles. Since two of the tiles have same label so there are $frac3!2!$ permutation. This case gives $2 cdot 2 cdot frac3!2!=12$.
Case $3$: All three tiles have same label. This is just $(3,3,3)$ so there is one tile in this case.
Summing up, you get $6+12+1=19$.
answered Jul 19 at 3:39
Tengu
2,3391920
answered Jul 19 at 3:39
Tengu
2,3391920
answered Jul 19 at 3:39
Tengu
2,3391920
answered Jul 19 at 3:39
Tengu
2,3391920
2,3391920
add a comment |Â
add a comment |Â
up vote
0
down vote
Question 1:
This is the same as finding the number of permutations of the 'word' $ABBCCC$. Let us distinguish the same letters by subscripts so that we now have $A_1B_1B_2C_1C_2C_3$. The number of of permutations of this is just $6!$. But for each valid permutation, there are $2!3!$ repeats due to permutations of the $B_i$ and $C_i$. Therefore our answer is $frac6!2!3!=60$.
Question 2:
My best guess is organized casework.
answered Jul 19 at 3:18
Shrey Joshi
1389
Note that the answer to question 1 is given by the OP and is 19, since it only asks for ordered triples of 3 symbols not ways to arrange all the tiles.
– jgon
Jul 19 at 3:28
add a comment |Â
up vote
0
down vote
Question 1:
This is the same as finding the number of permutations of the 'word' $ABBCCC$. Let us distinguish the same letters by subscripts so that we now have $A_1B_1B_2C_1C_2C_3$. The number of of permutations of this is just $6!$. But for each valid permutation, there are $2!3!$ repeats due to permutations of the $B_i$ and $C_i$. Therefore our answer is $frac6!2!3!=60$.
Question 2:
My best guess is organized casework.
answered Jul 19 at 3:18
Shrey Joshi
1389
Note that the answer to question 1 is given by the OP and is 19, since it only asks for ordered triples of 3 symbols not ways to arrange all the tiles.
– jgon
Jul 19 at 3:28
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Question 1:
This is the same as finding the number of permutations of the 'word' $ABBCCC$. Let us distinguish the same letters by subscripts so that we now have $A_1B_1B_2C_1C_2C_3$. The number of of permutations of this is just $6!$. But for each valid permutation, there are $2!3!$ repeats due to permutations of the $B_i$ and $C_i$. Therefore our answer is $frac6!2!3!=60$.
Question 2:
My best guess is organized casework.
answered Jul 19 at 3:18
Shrey Joshi
1389
Question 1:
This is the same as finding the number of permutations of the 'word' $ABBCCC$. Let us distinguish the same letters by subscripts so that we now have $A_1B_1B_2C_1C_2C_3$. The number of of permutations of this is just $6!$. But for each valid permutation, there are $2!3!$ repeats due to permutations of the $B_i$ and $C_i$. Therefore our answer is $frac6!2!3!=60$.
Question 2:
My best guess is organized casework.
answered Jul 19 at 3:18
Shrey Joshi
1389
edited Jul 19 at 3:25
answered Jul 19 at 3:18
Shrey Joshi
1389
answered Jul 19 at 3:18
Shrey Joshi
1389
answered Jul 19 at 3:18
Shrey Joshi
1389
1389
Note that the answer to question 1 is given by the OP and is 19, since it only asks for ordered triples of 3 symbols not ways to arrange all the tiles.
– jgon
Jul 19 at 3:28
add a comment |Â
Note that the answer to question 1 is given by the OP and is 19, since it only asks for ordered triples of 3 symbols not ways to arrange all the tiles.
– jgon
Jul 19 at 3:28
Note that the answer to question 1 is given by the OP and is 19, since it only asks for ordered triples of 3 symbols not ways to arrange all the tiles.
– jgon
Jul 19 at 3:28
Note that the answer to question 1 is given by the OP and is 19, since it only asks for ordered triples of 3 symbols not ways to arrange all the tiles.
– jgon
Jul 19 at 3:28
add a comment |Â
up vote
0
down vote
For the case where order does not matter.
Suppose you have $x$, $y$, and $z$ objects A, B and C respectively. You are choosing $k$ tiles.
If $k-(y+z)>0$, then you need to pick at least $(k-(y+z))$ of object A. Otherwise, at least zero.
For $i$ of object A chosen, you must choose $(k-i)$ of objects B and C combined.
If $(k-i)-z>0$, then you need to pick at least $((k-i)-z)$ of object B. Otherwise, at least zero.
For $j$ of object B chosen, you must choose $(k-(i+j))$ of object C.
In total, you have $i$ of object A, $j$ of object B, and $(k-(i+j))$ of object C.
If order does not matter, you permute the chosen $k$ objects and account for the identical objects.
$$sum_i=max0,k-(y+z)^i=mink,xsum_j=max0,(k-i)-z^i=mink-i,ydfrack!i!j!(k-i-j)!$$
For the case where order matters
We don't really have a formula for this. But an organized method is more crucial.
Check if any of $x,y,z$ is less than $k$. Those that are equal or more than $k$ is in excess supply and we don't worry about them. Those that is less than $k$ introduces cases.
For your case, let me rename some stuff. You have 1 A, 2 B's and 3 C's. The limiting agents are $A$ and $B$.
So we consider all pairs of $(a,b)$ such that $0le a+b le k$. For your case, we have
$$(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)$$
beginarrayc
(a,b) & textnumber of ways \
hline
(0,0) & frac3!3!=1\
(0,1) & frac3!2!=3\
(0,2) & frac3!2!=3\
(1,0) & frac3!2!=3 \
(1,1) & 3!=6\
(1,2) & frac3!2!=3\
endarray
Total: 19 ways.
Of course you can derive a summation from this, but a generalized summation is not very worth deriving unless you have a specific context.
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
add a comment |Â
up vote
0
down vote
For the case where order does not matter.
Suppose you have $x$, $y$, and $z$ objects A, B and C respectively. You are choosing $k$ tiles.
If $k-(y+z)>0$, then you need to pick at least $(k-(y+z))$ of object A. Otherwise, at least zero.
For $i$ of object A chosen, you must choose $(k-i)$ of objects B and C combined.
If $(k-i)-z>0$, then you need to pick at least $((k-i)-z)$ of object B. Otherwise, at least zero.
For $j$ of object B chosen, you must choose $(k-(i+j))$ of object C.
In total, you have $i$ of object A, $j$ of object B, and $(k-(i+j))$ of object C.
If order does not matter, you permute the chosen $k$ objects and account for the identical objects.
$$sum_i=max0,k-(y+z)^i=mink,xsum_j=max0,(k-i)-z^i=mink-i,ydfrack!i!j!(k-i-j)!$$
For the case where order matters
We don't really have a formula for this. But an organized method is more crucial.
Check if any of $x,y,z$ is less than $k$. Those that are equal or more than $k$ is in excess supply and we don't worry about them. Those that is less than $k$ introduces cases.
For your case, let me rename some stuff. You have 1 A, 2 B's and 3 C's. The limiting agents are $A$ and $B$.
So we consider all pairs of $(a,b)$ such that $0le a+b le k$. For your case, we have
$$(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)$$
beginarrayc
(a,b) & textnumber of ways \
hline
(0,0) & frac3!3!=1\
(0,1) & frac3!2!=3\
(0,2) & frac3!2!=3\
(1,0) & frac3!2!=3 \
(1,1) & 3!=6\
(1,2) & frac3!2!=3\
endarray
Total: 19 ways.
Of course you can derive a summation from this, but a generalized summation is not very worth deriving unless you have a specific context.
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
add a comment |Â
up vote
0
down vote
up vote
0
down vote
For the case where order does not matter.
Suppose you have $x$, $y$, and $z$ objects A, B and C respectively. You are choosing $k$ tiles.
If $k-(y+z)>0$, then you need to pick at least $(k-(y+z))$ of object A. Otherwise, at least zero.
For $i$ of object A chosen, you must choose $(k-i)$ of objects B and C combined.
If $(k-i)-z>0$, then you need to pick at least $((k-i)-z)$ of object B. Otherwise, at least zero.
For $j$ of object B chosen, you must choose $(k-(i+j))$ of object C.
In total, you have $i$ of object A, $j$ of object B, and $(k-(i+j))$ of object C.
If order does not matter, you permute the chosen $k$ objects and account for the identical objects.
$$sum_i=max0,k-(y+z)^i=mink,xsum_j=max0,(k-i)-z^i=mink-i,ydfrack!i!j!(k-i-j)!$$
For the case where order matters
We don't really have a formula for this. But an organized method is more crucial.
Check if any of $x,y,z$ is less than $k$. Those that are equal or more than $k$ is in excess supply and we don't worry about them. Those that is less than $k$ introduces cases.
For your case, let me rename some stuff. You have 1 A, 2 B's and 3 C's. The limiting agents are $A$ and $B$.
So we consider all pairs of $(a,b)$ such that $0le a+b le k$. For your case, we have
$$(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)$$
beginarrayc
(a,b) & textnumber of ways \
hline
(0,0) & frac3!3!=1\
(0,1) & frac3!2!=3\
(0,2) & frac3!2!=3\
(1,0) & frac3!2!=3 \
(1,1) & 3!=6\
(1,2) & frac3!2!=3\
endarray
Total: 19 ways.
Of course you can derive a summation from this, but a generalized summation is not very worth deriving unless you have a specific context.
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
For the case where order does not matter.
Suppose you have $x$, $y$, and $z$ objects A, B and C respectively. You are choosing $k$ tiles.
If $k-(y+z)>0$, then you need to pick at least $(k-(y+z))$ of object A. Otherwise, at least zero.
For $i$ of object A chosen, you must choose $(k-i)$ of objects B and C combined.
If $(k-i)-z>0$, then you need to pick at least $((k-i)-z)$ of object B. Otherwise, at least zero.
For $j$ of object B chosen, you must choose $(k-(i+j))$ of object C.
In total, you have $i$ of object A, $j$ of object B, and $(k-(i+j))$ of object C.
If order does not matter, you permute the chosen $k$ objects and account for the identical objects.
$$sum_i=max0,k-(y+z)^i=mink,xsum_j=max0,(k-i)-z^i=mink-i,ydfrack!i!j!(k-i-j)!$$
For the case where order matters
We don't really have a formula for this. But an organized method is more crucial.
Check if any of $x,y,z$ is less than $k$. Those that are equal or more than $k$ is in excess supply and we don't worry about them. Those that is less than $k$ introduces cases.
For your case, let me rename some stuff. You have 1 A, 2 B's and 3 C's. The limiting agents are $A$ and $B$.
So we consider all pairs of $(a,b)$ such that $0le a+b le k$. For your case, we have
$$(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)$$
beginarrayc
(a,b) & textnumber of ways \
hline
(0,0) & frac3!3!=1\
(0,1) & frac3!2!=3\
(0,2) & frac3!2!=3\
(1,0) & frac3!2!=3 \
(1,1) & 3!=6\
(1,2) & frac3!2!=3\
endarray
Total: 19 ways.
Of course you can derive a summation from this, but a generalized summation is not very worth deriving unless you have a specific context.
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
edited Jul 19 at 3:39
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
answered Jul 19 at 3:29
Karn Watcharasupat
3,8192426
3,8192426
add a comment |Â
add a 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%2f2856180%2fpermutations-combinations-with-repeated-symbols%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