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?
Best Answer
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.