Solving a 5-Digit Probability Problem Using Combinations

  • Thread starter Thread starter DrAlexMV
  • Start date Start date
  • Tags Tags
    Probability
AI Thread Summary
The discussion focuses on calculating the number of 5-digit numbers that can be formed from the integers 1 to 9, with the restriction that no digit can appear more than twice. The initial approach using the combination formula was criticized for overcounting due to the arrangement of identical digits. A more accurate method involves categorizing the combinations into three cases: no repeated digits, one digit repeated, and two digits repeated, leading to a refined calculation. The final result is derived from these cases, yielding a total of 52,920 valid combinations. This method provides a clearer understanding of how to handle the constraints of the problem effectively.
DrAlexMV
Messages
24
Reaction score
0
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.
 
Physics news on Phys.org
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 95 and remove the disallowed:
- three the same, two different: 9 * 8 * 7 * 5C2
- "full house": 9 * 8 * 5C2
- four the same: 9 * 8 * 5C1
- five the same: 9
Result: 52920
 
Could you elaborate on what you mean by "one or two pairs the same, etc"?
 
DrAlexMV said:
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 (25, 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 = 9C2 * 5 * 4 * 3 * 2 * 14 = 60480.
X + Y + Z = 18!/(18-5)!; X/32 + Y/16 + Z/8 = 52920.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top