[Math] Simplest way to count distinct combinations

combinationscombinatorics

Consider the following table:

   | A  | B  | C  | D 
   --------------------
 A | AA | AB | AC | AD
 B | BA | BB | BC | BD
 C | CA | CB | CC | CD
 D | DA | DB | DC | DD

Assume the horizontal axis will always be equal to the vertical axis (this means, if my horizontal axis goes from A to Z, my vertical axis will go from A to Z too). Let's call n the number of letters used on an axis (here, 4).

From here, counting the number of possible combinations is easy: it's just the product of the number of columns by the number of rows, in this case n x n => 4 x 4 = 16.

Now if I want to count the number of combinations which haven't the same letter twice, in this case it's simple too, it's (n x n) – n => (4 x 4) – 4 = 12. No big deal at this point.

Now imagine I want to produce combinations that have a length of n. The combinations will look like this:

AAAA

AAAB

AAAC

…

DDDD

Computing the number of possible combinations is easy too: n^n => 4^4 = 256. Peanuts.

But what if I only want to count the number of combinations that haven't the same letter more than once? In this case, I can find only 24 combinations matching that rule, which are:

  • ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA

But I don't manage to find the formula using n, that comes to that number 24.

Any ideas?

Thank you,

Ben

Best Answer

If you have $n$ symbols and you want to produce a sequence $s$ of length $n$ where no symbol appears more than once, then this means that each symbol appears either $1$ time or $0$ times. If there was a symbol that would appear $0$ times, however, then another symbol would have to appear more than $1$ time; hence every symbol appears in $s$ exactly $1$ time.

So $s$ is an ordered sequence of length $n$, where each of our $n$ symbols appears exactly $1$ time. For the first position in $s$, we have $n$ possible symbols at our disposal. For the second position of $s$, we then have $n-1$ possible symbols in our disposal, since we have already used one of the symbols in the first position and are not allowed to use it again.

Continuing with this reasoning tells us that there are $n*(n-1)(n-2)...3*2*1 = n!$ possibilities for $s$. In your case with $n=4$, we have $4! = 4*3*2 = 24$.

Related Question