Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Combinations

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.

Example. Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S.

The number of r -combinations of a set with n distinct elements is denoted by C(n, r).

Example. We see that C (4, 2) = 6, since the 2-combinations of { a, b, c, d } are the six subsets { a, b }, { a, c }, { a, d }, { b, c }, { b, d }, and { c, d }.

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. To do this, note that the r -permutations of a set can be obtained by first forming r -combinations and then ordering the elements in these combinations.

Theorem 2. The number of r -combinations of a set with n elements, where n is a positive integer and r is an integer with , equals .

Proof: The r -permutations of the set can be obtained by forming the C(n, r) r -combinations of the set, and then ordering the elements in each r -combination, which can be done in P(r, r) ways. Consequently, This implies that .

Corollary 1. Let n and r be nonnegative integers with . Then .

There is another common notation for the number of r -combinations from a set with n elements, namely, , i.e. . This number is also called a binomial coefficient. The name “binomial coefficient” is used because these numbers occur as coefficients in the expansion of powers of binomial expressions such as .

Example. How many ways are there to select 5 players from a 10-member tennis team to make a trip to a match at another school?

Solution: The answer is given by the number of 5-combinations of a set with 10 elements:

Example. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of 3 faculty members from the mathematics department and 4 from the computer science department, if there are 9 faculty members of the mathematics department and 11 of the computer science department?

Solution: By the product rule, the answer is the product of the number of 3-combinations of a set with 9 elements, and the number of 4-combinations of a set with 11 elements.