# Permutations with duplicates

I have a data set $2\; 3\; 3\; 4\; 4\; 4\; 4$

I want to find the number of unique numbers of $3$ digit numbers that can be formed using this.

I was thinking of doing $\large{\frac{^7P_3}{4!\times 2!}}$, but this doesn't seem right.

If you have 2 as the first digit, you can have 3 and 4 as the second and third digits, so this gives 233 234 243 244, four numbers.

If you have 3 as the first digit, you can have 2 and 3 and 4 as second and third digits (but 2 only once), giving 323 332 324 342 334 343 344, seven numbers.

If you have 4 as the first digit, you can have 2, 3 and 4 as second and third digits, giving 424 442 423 432 433 434 443 444, eight numbers.

4 + 7 + 8 = 19 unique 3 digit numbers.

Rather brute force, but it works pretty easily for this problem.

Alternatively, start from all 3-digit permutations of {2,3,4}, with repeats. That's $3^3=27$. Then remove numbers that have too many 2's or 3's.

Take out numbers with exactly 2 2's: 2 choices for the remaining digit and 3 ways to permute the 3 digits is 6.

Take out numbers with exactly 3 2's, of which there's only 1.

Take out numbers with 3 3's, of which there's only 1.

Then what's left is 27-6-1-1 = 19

I answered a similar question here.

Your data set is a multiset that can be written as $$S=(\underbrace{2,\cdots,2 }_{1},\underbrace{3,\cdots,3 }_{2},\underbrace{4,\cdots,4 }_{4})$$ where the number under the brace is the multiplicity of the element above, wich is the number of instances of the element in the multiset. Lets call the number of digit you need $l$ (in this case $l=3$). Lets call the number of distinct elements of the multiset $n$ (in this case $n=3$) and lets call the multiplicity of the $k_{th}$ element $m_k$ (in this case $m_1=1$, $m_2=2$ and $m_3=4$), what you need are all the combinations of $(x_1,x_2,\dots,x_n)$ where $0 \leq x_k \leq m_k$ so that $$\sum_{k=1}^n x_k = l$$ Lets list all the values that any $x_k$ can have: $$x_1=(0,1)$$ $$x_2=(0,1,2)$$ $$x_3=(0,1,2,3,4)$$ and, with those values, lets list all their possible combinations, remembering that their sum must be equal to $l$: $$C_1=(0,0,3)$$ $$C_2=(0,1,2)$$ $$C_3=(0,2,1)$$ $$C_4=(1,0,2)$$ $$C_5=(1,1,1)$$ $$C_6=(1,2,0)$$ Since the sum of the elements of each combination is equal to $l$, you can see each combination as a multiset in wich $l$ is equal to the sum of the multiplicity of each element, so the number of permutations for each combination is $$\frac{l!}{x_1!x_2! \dots x_k!}$$ What remains to do is to sum all the numbers of permutations of each combination to get the final answer, so $$\frac{3!}{0!0!3!}+\frac{3!}{0!1!2!}+\frac{3!}{0!2!1!}+\frac{3!}{1!0!2!}+\frac{3!}{1!1!1!}+\frac{3!}{1!2!0!}=1+3++3+3+6+3=19$$ If you need a deeper explanation of why this works you can check the link above. I came up with this method while working on a project and I'm not a matematician myself, so it could be a bit messy. Sorry in advance.

If you start off with the 7P3 ways of choosing three distinct ordered elements from the multiset {2,3,3,4,4,4,4} then you will need to compensate for the multiply-counted 3-digit numbers in different ways depending on the structure of the number itself. Consequently, you're likely to be stuck using an almost brute-force attack on the problem.

For example, you could generate all the unordered 3-digit numbers:

233, 234, 244, 334, 344, 444


Then consider one-by-one how many ordered 3-digit numbers have those particular digits.

3!/2! + 3! + 3!/2! + 3!/2! + 3!/2! + 3!/3!


Once you're done, you could check your result using GAP by:

Arrangements([2,3,3,4,4,4,4],3);


It seems to me that a general formula for this simple but irregular question would be an overkill. Perhaps it is more efficient to simply count the possibilities:

• for each of the possible 3 locations of 2 there are 4 such numbers, for a total of 12;
• there are a total of 8 different 3-digit numbers which have digits 3 or 4; however exactly one of them, namely 333, is not permissible; thus there are 7 different allowable 3-digit numbers, which have 3 and 4 as their only digits;

We see that all together there are 12+7 = 19 different solutions (3-digit numbers, which satisfy the stated assumptions).