6.3 Permutations and Combinations Flashcards
A permutation of a set of n distinct objects is?
A permutation of a set of n distinct objects is an ordered arrangement of these objects.
r-permutation?
We also are interested in ordered arrangements of some of the elements of a set. An ordered arrangement of r elements of a set is called an r-permutation.
The number of r-permutations of a set with n elements is denoted by P(n, r). We can find P(n, r)
using the product rule.
Theorem.
We now use the product rule to find a formula for P(n, r)
If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are
P(n, r) = n(n − 1)(n − 2) ⋯ (n − r + 1)
r-permutations of a set with n distinct elements.
P(n,0) ?
Note that P(n, 0) = 1 whenever n is a nonnegative integer because there is exactly one way to
order zero elements.
That is, there is exactly one list with no elements in it, namely the empty list.
Corollary:
Formula for r permutation:
If n and r are integers with 0 ≤ r ≤ n, then
P(n, r) = n!/(n − r)!
Ex 8: How many different committees of three students can be formed from a group of four students?
An approach to solve this?
Example 8 illustrates that many counting problems can be solved by finding the number of
subsets of a particular size of a set with n elements, where n is a positive integer
r Combination:
definition and denotion
An r-combination of elements of a set is an unordered selection of r elements from the set.
Thus, an r-combination is simply a subset of the set with r elements.
The number of r-combinations of a set with n distinct elements is denoted by C(n, r). Note
that C(n, r) is also denoted by (^n vr)
and is called a binomial coefficient.
Theorem
to calculate r combination.
The number of r-combinations of a set with n elements, where n is a nonnegative integer and
r is an integer with 0 ≤ r ≤ n, equals
C(n, r) = n!/r! (n − r)!
We can determine the number of r-combinations of a set with n elements using the formula
for the number of r-permutations of a set.
Note that the r-permutations of a set can be
obtained by first forming r-combinations and then ordering the elements in these combinations.
Proof of:
C(n, r) = n!/r! (n − r)!
P(n, r) = C(n, r) ⋅ P(r, r).
thats why.
OR division Rule
each of the C(n, r) r-combinations of a set with n elements
corresponds to exactly P(r, r) r-permutations. Hence, by the division rule, C(n, r) = P(n,r)/P(r,r).
Because the
order of elements in a combination does not matter and there are P(r, r) ways to order r elements
in an r-combination of n elements
Computation Of C(n,r):
It’s not helpful with C(n, r) = n!/r! (n − r)!.
Cuz t it is practical to compute exact values of factorials
exactly only for small integer values, and when floating point arithmetic is used, the formula may produce a non int.
So, make it : C(n,r) = n(n − 1) ⋯ (n − r + 1)/r!
Then factor out common factors in
the numerator n(n − 1) ⋯ (n − r + 1) and in the denominator r!.
Corollary 2:
a key identity enjoyed by the numbers C(n, k).
Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r).
combinatorial proof:
A combinatorial proof of an identity is a proof that uses counting arguments to prove that
both sides of the identity count the same objects but in different ways or a proof that is based
on showing that there is a bijection between the sets of objects counted by the two sides of
the identity. These two types of proofs are called double counting proofs and bijective proofs,
respectively
a bijective proof to show that C(n, r) = C(n, n − r)
Suppose that S is a set with n elements. The function that maps a subset A
of S to Abar is a bijection between subsets of S with r elements and subsets with n − r elements
(as the reader should verify). The identity C(n, r) = C(n, n − r) follows because when there is a
bijection between two finite sets, the two sets must have the same number of elements.
Double counting proof for C(n, r) = C(n, n − r)
Alternatively, we can reformulate this argument as a double counting proof. By definition,
the number of subsets of S with r elements equals C(n, r). But each subset A of S is also determined by specifying which elements are not in A, and so are in A. Because the complement of
a subset of S with r elements has n − r elements, there are also C(n, n − r) subsets of S with r
elements. It follows that C(n, r) = C(n, n − r).
