0
$\begingroup$

I have $N$ elements:

$$e_1, e_2, e_3, e_4, ..., e_N$$

and each of them has $M$ possible states:

$$e_i:\, e_{i1}, e_{i2}, ..., e_{iM}$$

I need to find the total number of combinations of these $N$ elements assuming all of their states.

For example if $N=2$ & $M=3$, I have elements $e_{1}, e_{2}$ with states:

$$e_{11}, e_{12}, e_{13} \;\&\; e_{21}, e_{22}, e_{23}$$

for which there are 9 possible combinations in total:

$$e_{11}, e_{21} / e_{11}, e_{22} / e_{11}, e_{23} / e_{12}, e_{21} / e_{12}, e_{22} / e_{12}, e_{23} / e_{13}, e_{21} / e_{13}, e_{22} / e_{13}, e_{23}$$

Notice that the position is irrelevant, which is why I don't count $e_{21}, e_{11}$ as a different permutation from $e_{11}, e_{21}$.

I've tried with small numbers and I believe the answer is $M^N$, but I'm not sure how to prove this.

$\endgroup$
  • 1
    $\begingroup$ Your presumption is right. $\endgroup$ – callculus Aug 4 '15 at 18:01
1
$\begingroup$

Consider the following set: $$S=\{(s_1,s_2,s_3, \ldots , s_{N}) \, | \, s_i \in \{e_{i1}, e_{i2}. \ldots ,e_{iM}\} \quad \text{ where } 1 \leq i \leq N\}.$$ Then the size of $S$ will give you all the possible states. Since each $s_i$ can be chosen in $M$ ways, therefore the number of such $N-$tuple vectors is $M^N$.

$\endgroup$
1
$\begingroup$

For the first object, there are $M$ possible states. For each of these states, we have $M$ possible states for the second object, giving a new total of $M \times M = M^2$ states. For each of these states, the third object has $M$ possible states, giving a new total of $M^2 \times M = M^3$. If we carry on with this process for all $N$ objects, we can easily see that the total number of states is given by $M^N$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.