Permutations with duplicates

Question

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.

Answer 1

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);

Answer 2

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.

Answer 3

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

Answer 4

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).