Дискретная математика. Азарнова Т.В - 32 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Комбинаторика
32
В общем случае число сочетаний из
n
элементов по
k
элементов
определяется следующей формулой:
()
!!
!
kkn
n
C
k
n
−
=
. (4)
Сначала образуем все возможные упорядоченные подмножества,
содержащие
k
элементов. Их число равно
k
n
C
. Затем из каждого полученного
подмножества перестановкой его элементов получим все упорядоченные
подмножества, которых будет в !
k
раз больше, так как каждое
k
-элементное
множество можно упорядочить !
k
способами. Итак,
k
n
k
n
CkA
!
=
, откуда и
следует формула (4).
Формулу (4) можно записать в другом, более удобном для вычислений
виде. Сократив числитель и знаменатель дроби на
()
!
kn
−
, получим
()( )( )
!
121
k
knnnn
C
k
n
+−−−
=
Κ
т.е.
число сочетаний из n элементов по k элементо в равно
произведению всех натуральных чисел от n до
1
+−
kn включительно,
деленному на
!
k .
Задача 8.
Сколько экзаменационных комиссий, состоящих из 7 членов,
можно образовать из 14 преподавателей?
Решение. Очевидно, столько, сколько существует семиэлементных
подмножеств у четырн адцати элементного множества. По формуле (4)
находим:
()
.3432
1234567
891011121314
!7!714
!14
7
14
=
⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅
=
−
=
C
Задача 9.
В чемпионате страны по футболу (высшая лига) участвуют
18 команд, причем каждые две команды встречаются между собой 2 раза.
Сколько матчей играется в течение сезона?
Решение. В первом круге состоится столько матчей, сколько
существует двухэлементных подмножеств у множества, содержащего 18
элементов, т.е. их число равно
2
18
C
. По формуле (4) получаем
153
!2!16
!18
2
18
=
⋅
=
C
.
Во втором круге играется столько же матчей, поэтому в течение сезона
состоится
3062
2
18
=
C
встреч.
Задача
10.
Решить неравенство
xx
CC
10
1
10
2
>
−
. 
                                      32
Комбинаторика
      В общем случае число сочетаний из n элементов по k элементов
определяется следующей формулой:
                                       n!
                            C nk =             .                        (4)
                                   (n −k )!k !
     Сначала образуем все возможные упорядоченные подмножества,
содержащие k элементов. Их число равно C nk . Затем из каждого полученного
подмножества перестановкой его элементов получим все упорядоченные
подмножества, которых будет в k ! раз больше, так как каждое k -элементное
множество можно упорядочить k ! способами. Итак, Ank =k !C nk , откуда и
следует формула (4).
      Формулу (4) можно записать в другом, более удобном для вычислений
виде. Сократив числитель и знаменатель дроби на (n −k )! , получим
                             n(n −1)(n −2 )Κ (n −k +1)
                      C nk =
                                        k!
      т.е. число сочетаний из n элементов по k элементов равно
произведению всех натуральных чисел от n до n −k +1 включительно,
деленному на k ! .

     Задача 8. Сколько экзаменационных комиссий, состоящих из 7 членов,
можно образовать из 14 преподавателей?
     Решение. Очевидно, столько, сколько существует семиэлементных
подмножеств у четырнадцати элементного множества. По формуле (4)
находим:
  7       14!       14 ⋅13 ⋅12 ⋅11 ⋅10 ⋅ 9 ⋅ 8
C14 =              =                            =3432.
      (14 −7 )!7 !     7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅1


     Задача 9. В чемпионате страны по футболу (высшая лига) участвуют
18 команд, причем каждые две команды встречаются между собой 2 раза.
Сколько матчей играется в течение сезона?
     Решение. В первом круге состоится столько матчей, сколько
существует двухэлементных подмножеств у множества, содержащего 18
элементов, т.е. их число равно C182 . По формуле (4) получаем
                                       18!
                              C182 =           =153 .
                                      16!⋅ 2 !
     Во втором круге играется столько же матчей, поэтому в течение сезона
состоится 2C182 =306 встреч.

      Задача 10. Решить неравенство
                              C10x −1 >2C10x .

Страницы