Permutations, k-Permutations and Combinations
Permutations, k-Permutations and Combinations
Number of Permutations
The number of ways to arrange different objects in a row is . The exclamation mark "!" is read as "factorial". Of course, the product is the same in reverse order: . Each such arrangement is called a permutation. For consistency, it is assumed that .
n
n!=1×2×3×⋯×
n
n!=n×(n-1)×(n-2)×…3×2×1
0!=1
Number of k-Permutations
If only of the objects are to be arranged in a row, the formula is
k
n
P(n,k)==n×(n-1)×…(n-k+1)
n!
(n-k)!
with factors. If , . Such an arrangement is called a partial permutation, or a -permutation. Clearly , because all objects are being arranged; the formula reduces to because the denominator is .
k
k>n
P(n,k)=0
k
P(n,n)=n!
n
n!
(n-n)!=0!=1
Number of Combinations
The number of ways to choose a subset of objects from objects is
k
n
C(n,k)=
n!
k!(n-k)!
Therefore, . Each choice of a subset is called a combination. Another notation for is . Again, if , . A special case is .
C(n,k)=P(n,k)/k!
C(n,k)
n |
k |
k>n
C(n,k)=0
C(n,n)=1