k-Permutations
In combinatorics, a k-permutation is an ordered selection of $ k $ elements drawn from a set of $ n $ elements. $$ D(n,k) $$ where $ k \le n $.
In k-permutations the order of the selected elements is essential.
The number of k-permutations corresponds to the total number of ordered k-tuples formed from $ n $ available elements.
There are two main types of k-permutations: those without repetition and those with repetition.
k-Permutations without repetition
The k-permutations of a set are the ordered selections of \( k \) distinct elements chosen from a larger set of \( n \) elements, with no repetitions allowed. The total number of such ordered selections is $$ D(n,k)=n \cdot (n-1) \cdot \ldots \cdot (n-k+1) $$ the product of the first \( k \) descending factors starting from \( n \). This quantity can also be written in factorial form: $$ D(n,k)=\frac{n!}{(n-k)!} $$ Both expressions describe the same count of k-permutations.
For $ n $ distinct elements, the k-permutations of class $ k $ include all possible ordered selections of $ k $ distinct elements.
Each ordered k-tuple is distinct either because the elements differ or because the same elements appear in a different order.
In short, two k-permutations differ if at least one element changes or if the order of the same elements changes.
Example. Consider the set $ \{ A, B, C \} $ with $ n=3 $. The k-permutations of class $ k=2 $ are all ordered selections of two distinct elements. There are six: $$ AB, BA, AC, CA, BC, CB $$ In every k-permutation the order of the elements matters. "AB" and "BA" are distinct. The same applies to "AC" and "CA".
Moreover, any sequence that repeats an element, such as "AA" or "BB", is excluded.
Number of k-permutations of class k
Let a set have $ n $ elements.
The k-permutations of class $ k $ are all possible ordered groups of $ k $ distinct elements drawn from those $ n $ elements. Their number is given by
$$ D(n,k)=n \cdot (n-1) \cdot \cdot \cdot (n-k+1) $$
This product of $ k $ consecutive decreasing factors starting from $ n $ yields the total number of k-permutations.
Note. When $ k=n $, the formula reduces to the factorial expression for the permutations of a set: $$ D(n,k=n)=n! $$ When $ k=1 $, there are $ n $ possible selections: $$ D(n,1)=n $$
Practical example
A race features 10 athletes.
How many possible ways can the first three positions be assigned?
Parameters:
$$ n=10 $$
$$ k =3 $$
The number of k-permutations without repetition is
$$ D(10,3) = 10 \cdot 9 \cdot 8 = 720 $$
Example 2
Consider the set $ \{ A, B, C, D \} $.
We want the k-permutations of class 2, that is, all ordered pairs of two distinct elements.
The possible ordered pairs are:
AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC
The total is
$ D_{4,2} = 4 · 3 = 12 $$
Example 3
Again consider the set $ \{ A, B, C, D \} $.
Now we form the ordered triples, the k-permutations of class 3.
$$ D_{n,3} = n · (n - 1) · (n - 2) $$
$$ D_{4,3} = 4 · 3 · 2 = 24 $$
Thus there are 24 possible ordered triples.
With A as the first element:
ABC, ABD, ACB, ACD, ADB, ADC
With B as the first element:
BAC, BAD, BCA, BCD, BDA, BDC
With C as the first element:
CAB, CAD, CBA, CBD, CDA, CDB
With D as the first element:
DAB, DAC, DBA, DBC, DCA, DCB
All together: 24.
Note. These examples show that order determines distinct k-permutations. "ABC" and "CBA" are different. No element can appear more than once, so sequences like "AAB" or "ABB" are excluded.
k-Permutations with repetition
A k-permutation with repetition allows elements to appear more than once within the same sequence. $$ D'(n,k)=n^k $$
Practical example
With the letters A, B, C, how many distinct two-letter strings can be formed?
Parameters:
$$ n=3 $$
$$ k =2 $$
The number of k-permutations with repetition is
$$ D'(3,2) = 3 ^ 2 = 9 $$
Note. Here are all $ 3^2 $ possible k-permutations with repetition. By contrast, the k-permutations without repetition are 3·2=6. This makes the conceptual distinction clear.
Difference between k-permutations and combinations
In k-permutations, the order of the elements is meaningful.
In combinations, the order is irrelevant.
Example. The strings AB and BA are distinct k-permutations but represent the same combination {A, B}. Combinations treat the elements as an unordered set, whereas k-permutations consider their order.
Difference between k-permutations and permutations
k-Permutations involve ordered selections of $ k $ elements from a total of $ n $.
Permutations involve ordering all $ n $ elements.
Note. When $ k=n $, the number of k-permutations equals the number of permutations. For instance, with $ n=3 $ and $ k=3 $, we have $ D(3,3)=3·2·1=6 $, the same value as $ n!=3·2·1 $.
k-Permutations with Repetition
In combinatorics, k-permutations with repetition count the number of ordered sequences of $ k $ elements drawn from a set of $ n $ elements when each element may be chosen more than once. The formula is $$ D'(n,k)=n^k $$
A k-permutation is an ordered sequence of $ k $ selections from $ n $ available elements. Because the sequence is ordered, any change in position or choice produces a distinct outcome.
For k-permutations with repetition, each position is selected independently from the entire set, so the same element can appear multiple times within the same sequence.
A practical example
Suppose we have three letters A, B and C. How many distinct two-letter strings can we form?
The parameters are:
$$ n=3 $$
$$ k=2 $$
Since repetition is permitted, the number of possible sequences is:
$$ D'(3,2)=3^2=9 $$
The full list of 9 k-permutations with repetition is:
AB, AC, AA, BA, BC, BB, CA, CB, CC
Here, sequences such as AA, BB and CC show that an element may be reused within the same string.
Nota. k-Permutations without repetition would yield only 3·2=6 sequences, since no element may be repeated. The comparison clearly illustrates the effect of allowing repetition.
Example 2
Now consider a set with four elements: A, B, C and D.
The class-2 k-permutations with repetition are all ordered pairs drawn from this set. These are:
AB, AC, AD, AA, BA, BC, BD, BB, CA, CB, CD, CC, DA, DB, DC, DD
The total number of such sequences is:
$$ D'_{4,2}=4^2=16 $$
Nota. As before, repetition is allowed, which is why sequences like "AA", "BB", "CC" and "DD" appear.
Notes
Some additional comments on terminology and related concepts:
- k-Permutations vs. combinations
k-Permutations account for order, which means different arrangements of the same elements are considered distinct. Combinations ignore order entirely. In short:- combinations treat selections as sets, where order is irrelevant
- k-permutations treat selections as ordered sequences, where order is essential
Example. AB and BA represent two different k-permutations, since their order differs. As a combination, however, both correspond to the same set {A,B}.
- k-Permutations vs. permutations k-Permutations involve choosing $ k $ ordered elements from a set of $ n $ elements, where $ k
Further extensions and generalizations follow naturally.
