There are 5 groups, let's say group A, B, C, D E. In each group, you can pick several numbers from 0 to 9. With these 5 groups, we can pick 1 number from each group, and come up to 1 sequence. The order must be ABCDE, and the number can not be duplicated. For example, 12345 is OK, but 11345 is not OK. How many combination of the sequence can you get?
For example:
A := {1, 2, 3, 4, 5, 6, 9}
B := {2, 3, 4, 5, 6, 7}
C := {1, 3, 4, 5, 6, 7, 8}
D := {4, 5, 6, 7, 8, 9}
E := {1, 2, 3, 5, 6, 7, 8, 9}
ABCDE
12345 is Good.
12141 is Bad.
@David Reed
Ya, that is a pain. I use inclusion-exclusion principle, but the answer is wrong.
AB mean the exclusive set of A and B
C(A, 1) * C(B, 1) * C(C, 1) * C(D, 1) * C(E, 1)
- C(AB, 1) * C(C, 1) * C(D, 1) * C(E, 1)
- C(AC, 1) * C(B, 1) * C(D, 1) * C(E, 1)
- ... (10 combination in total)
+ C(ABC, 1) * C(D, 1) * C(E, 1)
+ ... (10 combination in total)
- C(ABCD, 1) * C(E, 1)
- ... (5 combinations in total)
+ C(ABCDE, 1)
If we pick all numbers for each groups, (every group has 10 numbers),
A = B = C = D = E = {0 ... 9}
The total combinations is 30240.
With my equation, I can not come up this answer. I think I miss the coefficients, and I don't what coefficients they are. Or, my equation is just completely wrong...
Let me preface by saying there's probably a more efficient way to do this.When using the inclusion-
exclusion principle one has to figure out what the "forbidden conditions" are.
Let $A_i$ be the set of all sequences containing more than one $i$
For example $A_3$ would be the set of all sequences containing more than one $3$
The total # of possible sequences is $8*7^2*6^2$ by the rule of product.
For $A_1$, $1$ is an available option in groups A,C, and E. So elements of $A_1$
have the form
$$ \begin{align} 1*1*1 \quad - \ & 6*6 \text{ options}\\ 1***1 \quad - \ & 6*7*6 \text{ options}\\ **1*1 \quad - \ & 7*6*6 \text{ options}\\ 1*1** \quad - \ & 6 * 6 * 8 \text{ options} \end{align} $$
$ \\ $
For $A_2$, $2$ is available in groups A,B,E. Possible types are:
$$ \begin{align} 22**2 \quad -& \ 7*6 \text{ options}\\ 2***2 \quad -& \ 6*7*6 \text{ options}\\ 22*** \quad -& \ 7*6*8 \text{ options}\\ *2**2 \quad -& \ 7*7*6 \text{ options} \end{align} $$
Although its a pain, continuing in this way and applying the inclusion-exclusion principle should give you the right result.