Simplest way to count distinct combinations

Question

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

Answer 1

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$.

Answer 2

It is simply $n!$

The first letter can be one of $n$

Once the first letter is in place, the second letter is one of $n-1$

Etc.

Hence, the number of possibilities is $$n \cdot (n-1) \cdot ... \cdot 1=n!$$

Answer 3

Let's say I want to find the number of ways to find the numbers of way for length $m$ with $n$ different letters to choose from(of course $n\ge m$)

First letter in the combination is one of $n$ different options.

Second letter is one of $n-1$(because I can't take the letter that I already used)

Third letter is one of $n-2$

.

.

.

$m$ letter is one of $n-m+1$.

From this we can conclude that the number of ways is $n(n-1)\cdots(n-m+1)$

Using a bit of algebra:$$n(n-1)\cdots(n-m+1)=n(n-1)\cdots(n-m+1)\frac{(n-m)!}{(n-m)!}=\frac{n!}{(n-m)!}$$

The example you gave is a special case where $m=n$ so we get $$\frac{n!}{0!}=n!,\text{ set $n=4$ to get to } n!=4!=24$$

Answer 4

Great, thank you everyone. I did not know about factorial numbers (the problem with self-taught programmers without scientific education).

At first I thought resolving this would help me solve another problem, but it doesn't:

What if I want to produce all combinations, (with the same set ABCD), with a length from 1 to n?

A

B

...

CBA

...

DDDD

Then I can find 340 combinations, and 64 combinations that don't share the same letter.

But again I don't manage to find how to get that number:

• When n = 1, n! = 1

• When n = 2, n! = 2

• When n = 3, n! = 6

• When n = 4, n! = 24

But 1 + 2 + 6 + 24 = 33, not 64... What am I omitting?

Thank you,

Ben