In how many ways can you arrange a group of 4 items? Most people (well, programmers at least) know the answer for that is 24, which is 4!.

But what about the more generic case where you have n items and want to permutate only k of them at a time, how many permutations are there in total?

General Permutations

For instance, suppose you have {a,b,c,d} and want to permutate it two letters at a time.

For the first letter you have 4 choices, for the second letter 3 choices, and that is it. So 4×3 = 12 total permutations.

Generalizing the equations, for a set with n elements where we want to permutate k at a time the total number of permutations P will be:

P = n * (n – 1) * (n – 2) * … * (n – k + 1)

As you can see, this is very similar to the factorial of a number, which is:

n! = n * (n – 1) * (n – 2) * … * 2 * 1

The only different is that we want to stop at step (n – k + 1). In other words, we want n! but eliminating all the multiplications after the number (n – k + 1), and those multiplications are equal to (n – k)!, so we just need to divide n! by (n – k)!. The final formula is:

P = n! / (n – k)!

K-ary Sequences

A binary sequence is a sequence of numbers where each digit can only be 0 or 1. A ternary sequence is one where digits can only be 0,1 and 2. So on and so for, so let’s call them k-are sequences.

How many different k-ary sequences are there of length n?

For instance, how many ternary sequences of length 2 are there? They are:

00
01
02
10
11
12
20
21
22

So 9, which not coincidentally is also 3^2.

In fact the general formula is k^n.