Solving a 5-Digit Probability Problem Using Combinations

[DrAlexMV]

Problem Statement:
How many 5 digit number can be formed from the integers 1,2, ..., 9 if no digit can appear more than twice?

Approach:
18!/((2!*9)(18-5)!)

Reason:
Using the combination formula, we were able to approach this problem by saying that there are 18 numbers from which only 5 are chosen and the order does not matter for individual groups of two numbers.

Is this approach correct? I would love a very detailed explanation of this problem since many of the ones in class are about this same difficulty level.

 

[haruspex]

That answer (57120) is close, but doesn't allow properly for the different combinations of one or two pairs the same etc.
In general, there's no easy way to solve these. For this one I would start with the full 9⁵ and remove the disallowed:
- three the same, two different: 9 * 8 * 7 * ⁵C₂
- "full house": 9 * 8 * ⁵C₂
- four the same: 9 * 8 * ⁵C₁
- five the same: 9
Result: 52920

 

[DrAlexMV]

Could you elaborate on what you mean by "one or two pairs the same, etc"?

 

[haruspex]

Could you elaborate on what you mean by "one or two pairs the same, etc"?

You set up a model in which each digit is represented twice, as 1a, 1b, 2a, 2b etc. say.
Your 18!/(18-5)! is the number of ways of choosing 5, in order, from 18. That's too many for two reasons: because choosing a single '1' will be counted twice (1a, 1b) and because choosing 1a for a certain position and 1b for another gives the same result as if they were swapped around. You can correct for the first problem by dividing by 32 (2⁵, not 2!*9), but that overcorrects when both the a and b copies are used (divides by 2 for each of the two digit positions instead of just once for the pair).
If we subdivide 18!/(18-5)! into three cases:
X = number with no repeated digits
Y = number with one digit repeated
Z = number with two digits repeated
then the final answer will be X/32 + Y/16 + Z/8
So we can see the answer lies between (18!/(18-5)!)/8 and (18!/(18-5)!)/32. You happened to divide by 18, so got a number that wasn't too far off.
Btw, X = 18 * 16 * 14 * 12 * 10 = 483840, Y = 9 * 5 * 4 * 16 * 14 * 12 = 483840, Z = ⁹C₂ * 5 * 4 * 3 * 2 * 14 = 60480.
X + Y + Z = 18!/(18-5)!; X/32 + Y/16 + Z/8 = 52920.

 

[blue_raver22]

I would approach this problem by first understanding the basic principles of combinations and permutations. Combinations refer to the number of ways in which a selection can be made from a set of objects without regard to the order of the objects. In contrast, permutations refer to the number of ways in which a selection can be made from a set of objects while considering the order of the objects.

In this problem, we are looking for the number of 5-digit numbers that can be formed using the integers 1-9, with the restriction that no digit can appear more than twice. This means that we can only choose two digits from each number (1-9) and we need to consider the order of these digits.

To solve this problem, we can use the combination formula: nCr = n! / (r!(n-r)!), where n is the total number of objects and r is the number of objects being selected. In this case, n=9 (since we have 9 digits) and r=2 (since we are choosing two digits from each number).

However, this formula only gives us the number of combinations for one 2-digit number. To find the total number of combinations for all 5-digit numbers, we need to multiply this by the number of ways we can arrange these 2-digit numbers. This can be done by using the factorial function, denoted by an exclamation mark (!). Factorial denotes the product of all positive integers less than or equal to a given number. For example, 5! = 5*4*3*2*1 = 120.

In this problem, we need to arrange 5 groups of 2-digit numbers, which can be done in 5! ways. Therefore, the total number of combinations for all 5-digit numbers is given by 9C2 * 9C2 * 9C2 * 9C2 * 9C2 * 5! = (9!/((2!*7!)(2!*7!)(2!*7!)(2!*7!)(2!*7!)) * 5! = 18!/((2!*9)(18-5)!) = 18!/((2!*9)(13!)).

In summary, the approach used in the problem statement is correct. We have used the combination formula to find the number of ways we can choose two digits from each number and then multiplied it by the