Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 37 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

37
Сочетания без повторений и с повторениями
Сочетаниями без повторений из п элементов по k называются не-
упорядоченные k-выборки из п элементов без повторений. Их число обо-
значается
k
n
C
и вычисляется по формуле
k
n
C
=
k)!-(nk!
!n
, k
£
n. (5)
Сочетания из n по k без повторений образуют k-элементарные под-
множества исходного множества мощности n. Числа
k
n
C
называются би-
номиальными коэффициентами.
Пример 11. Сколькими способами можно выбрать три различные
краски из имеющихся пяти?
Решение. Очевидно, что нужно подсчитать число 3-выборок из
5 элементов, причем по условию задачи понятно, что среди выбранных эле-
ментов не должно быть одинаковых и что порядок расположения выбранных
красок не существенен. Значит, нужно найти число неупорядоченных выбо-
рок, т. е. число сочетаний без повторений из 5 по 3. По формуле (5) имеем:
3
5
С
=
)!35(!3
!5
-
= 5
´
!
2
4
= 10.
Сочетаниями с повторениями из п элементов по k называются не-
упорядоченные k-выборки из п элементов с повторениями. Их число обо-
значается
k
n
H
и вычисляется по формуле
k
n
H
=
k
kn
C
1-+
=
)!1(!
)!1(
-
-
+
nk
kn
, Nkn
Î
, . (6)
Пример 12. В киоске имеются открытки 10 видов. Сколькими спосо-
бами можно купить: а) 5 открыток? б) 5 разных открыток? в) 15 открыток с
повторениями?
Решение. В случаях а) и в) нас интересуют неупорядоченные выбор-
ки из 10 элементов с повторениями длины 5 и 15 соответственно. Их число
определяется по формуле (6):
a)
5
10
H
=
5
1051
C
+-
=
5
14
C
=
)!514(!5
!14
-
=
5!
10 11 12 13 14
´
´
´
´
=2002 (способа);
в)
15
10
H
=
15
10151
C
+-
=
15
24
C
=
)!1524(!15
!24
-
=
!
9
!
15
!24
(способов).
В случае б) нужно подсчитать число неупорядоченных 5-выборок из
10 элементов без повторений (все открытки разные). Их число определяет-
ся по формуле (5) :
5
10
C
=
!
5
!
5
!10
= 252 (способа). 
                Сочетания без повторений и с повторениями

     Сочетаниями без повторений из п элементов по k называются не-
упорядоченные k-выборки из п элементов без повторений. Их число обо-
            k
значается C n и вычисляется по формуле
                                        Cnk =      n!
                                                           , k � n.                          (5)
                                                k!(n - k)!
     Сочетания из n по k без повторений образуют k-элементарные под-
множества исходного множества мощности n. Числа                         Cnk   называются би-
номиальными коэффициентами.
       Пример 11. Сколькими способами можно выбрать три различные
краски из имеющихся пяти?
       Решение. Очевидно, что нужно подсчитать число 3-выборок из
5 элементов, причем по условию задачи понятно, что среди выбранных эле-
ментов не должно быть одинаковых и что порядок расположения выбранных
красок не существенен. Значит, нужно найти число неупорядоченных выбо-
рок, т. е. число сочетаний без повторений из 5 по 3. По формуле (5) имеем:
                               С53 =        5!          4
                                                   = 5 � = 10.
                                        3!(5 � 3)!      2!

     Сочетаниями с повторениями из п элементов по k называются не-
упорядоченные k-выборки из п элементов с повторениями. Их число обо-
значается   Hnk и вычисляется по формуле
                           H nk = Cnk�k�1 = (n � k � 1)! , �n, k � N .                       (6)
                                                        k!(n � 1)!

      Пример 12. В киоске имеются открытки 10 видов. Сколькими спосо-
бами можно купить: а) 5 открыток? б) 5 разных открыток? в) 15 открыток с
повторениями?
      Решение. В случаях а) и в) нас интересуют неупорядоченные выбор-
ки из 10 элементов с повторениями длины 5 и 15 соответственно. Их число
определяется по формуле (6):
     a)   H105 = C105 � 5 �1 = C145 =        14!
                                                     =
                                                       14 � 13 � 12 � 11 � 10
                                                                              =2002 (способа);
                                        5! (14 � 5)!             5!
           15                  15
     в)   H10    15
              = C10 � 15 �1 = C24=
                                              24!
                                                       =
                                                          24!
                                                               (способов).
                                        15! (24 � 15)!   15!9!
      В случае б) нужно подсчитать число неупорядоченных 5-выборок из
10 элементов без повторений (все открытки разные). Их число определяет-
                       5   10!
ся по формуле (5) : C 10 =     = 252 (способа).
                                 5!5!

                                                   37

Страницы