2
$\begingroup$

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 $\frac{5!}{\left(5-3\right)!}$ because you have repeated symbols. And you can't divide by the factorials of repeated symbols $\frac{6!}{\left(6-3\right)!\cdot3!\cdot2!}$ like you can when n = k and you make different arrangements of all n of symbols $\frac{n!}{\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 $\frac{n!}{\left(n-k\right)!\cdot k!}$ because you have repeated symbols. What formula would be used to find the answer to a more complex version of this problem?

$\endgroup$
2
$\begingroup$

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 $\newcommand{\multset}[1]{\{\{{#1}\}\}}\multset{3,3,3},\multset{2,3,3},\multset{2,2,3},\multset{1,3,3},\multset{1,2,3},$ and $\multset{1,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 $\multset{a,a,a}$ is $3!/3!=1$, $\multset{a,a,b}=3!/2!=3$, and $\multset{a,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.

$\endgroup$
  • $\begingroup$ That seems to work... I'm fairly nieve here, but do you know of a way to accomplish this mathematically instead of algorithmically? $\endgroup$ – etrilling Jul 19 '18 at 8:06
  • $\begingroup$ @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). $\endgroup$ – jgon Jul 19 '18 at 10:55
1
$\begingroup$

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 $\frac{3!}{2!}$ permutation. This case gives $2 \cdot 2 \cdot \frac{3!}{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$.

$\endgroup$
0
$\begingroup$

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 $\frac{6!}{2!3!}=60$.

Question 2: My best guess is organized casework.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jgon Jul 19 '18 at 3:28
0
$\begingroup$

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=\max\{0,k-(y+z)\}}^{i=\min\{k,x\}}\sum_{j=\max\{0,(k-i)-z\}}^{i=\min\{k-i,y\}}\dfrac{k!}{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 $0\le a+b \le k$. For your case, we have $$(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)$$

\begin{array}{c|c} (a,b) & \text{number of ways} \\ \hline (0,0) & \frac{3!}{3!}=1\\ (0,1) & \frac{3!}{2!}=3\\ (0,2) & \frac{3!}{2!}=3\\ (1,0) & \frac{3!}{2!}=3 \\ (1,1) & 3!=6\\ (1,2) & \frac{3!}{2!}=3\\ \end{array}

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.