0

My answer: $$\binom{5}{5}_{R}-75=126-75=51$$

However, I want to try this using inclusion/exclusion

Let U be set $\{1,2,3,4,5\}$ where we want to find the number of 5-digit combination allowing repetition. Find this value using inclusion/exclusion so that: |U|-|$A_{1}\cup A_{2}\cup A_{3}\cup A_{4}$|=|U|-75=51.

What I am completely stuck on is coming up with the correct |U| and |$A_{1}\cup A_{2}\cup A_{3}\cup A_{4}$|. This is what I need help on.

Please help me understand what I need to do. Thank you.

Nixie777
  • 721
  • What is $\binom{5}{5}_R$? – Henno Brandsma Jul 30 '17 at 06:07
  • The formula $\binom{n}{k}_R=\binom{n+k-1}{k}$ is the number of combinations of a given length that use elements from a given set, allowing repetition, where n is number of elements in the given set and k is the length of the combination. – Nixie777 Jul 30 '17 at 06:12

1 Answers1

0

Suppose you want to find the opposite: the number of combinations that have at least one digit that occurs at least three times. Let $p_i$ be the set of 5-digit combinations that satisfy the property that the digit $i$ is repeated at least thrice. You can see that to find the opposite, you need to find $$|p_1 \cup p_2 \cup p_3 \cup p_4 \cup p_5|.$$ You can use the inclusion-exclusion principal on this. It seems intimidating, but notice that it's impossible for two or more distinct properties to occur at the same time (do you see why?) This will cut down on the computations significantly.

Once you find that, the answer you seek will be $$|S| -| p_1 \cup p_2 \cup p_3 \cup p_4 \cup p_5|,$$

where $S$ is the total amount of 5 digit combinations with no restriction.

benguin
  • 3,846
  • Yes I understand that, but how do I get the |S| value using inclusion/exclusion? – Nixie777 Jul 30 '17 at 11:32
  • @Nixie777 You don't. The value of $|S|$, as benguin notes, represents the total number of 5-digit combinations without restriction. You find this using the stars-and-bars formula you commented above. You may find this answer helpful for stars and bars. – Aleksandr Hovhannisyan Jul 30 '17 at 21:56