Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 57 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

57
Примечание. Если объединить все размещения из n элементов по k, состоящие из
одних и тех же элементов (не учитывая расположения) в классы эквивалентности, то ка-
ждому классу будет соответствовать ровно одно сочетание C
n
k
и наоборот:
n!
C
n
k
=
k!(n - k)!
Пример. Для множества S = {a, b, c, d} из предыдущего примера число
различных двухэлементных сочетаний C
4
2
= 4!/(2! 2!) = 6.
S
c
= {(a ,b)(a, c)(a, d)(b, c)(b, d)(c, d)}.
Задача. Сколько различных комбинаций может выпасть в спортлото
«5 из 36»:
C
36
5
= 36! / 5!(36 – 5)! = 36! / 5! 31! = 6992,
а в спортлото «6 из 45» – C
45
6
= 568260.
3.4.1. Сочетания с повторениями
Сочетаниями из n элементов по k элементов с повторениями на-
зываются группы, содержащие k элементов, причем каждый элемент
принадлежит к одному из n типов.
Например. Для множества S = {a, b, c, d} двухэлементные сочетания с
повторениями
S
~
c
= {(a, a)(a, b)(a, c)(a, d)(b, b)(b, c)
(b, d)(c, c)(c, d)(d, d)}.
Число различных сочетаний из n элементов по k c повторениями рав-
но
C
~
k
=C
n-1
n+k-1
= C
k
n+k-1
Пример. Кости домино можно рассматривать как цифры 0, 1, 2, 3, 4, 5,
6. Число сочетаний по два элемента равно
С
7
2
=(n+k–1)! / (k!(n–1)!) = 8! / (2!6!) = 7×8/2 = 28.
Упражнения 3.4
1. Сколькими способами можно выбрать 3 различные краски из
имеющихся 5?
Решение. Сочетание трех различных красок из имеющихся пяти можно
выбрать
3
5
С
способами, т. е. всего вариантов . . . . .
2. Сколькими способами можно выбрать три пирожных из 6 различ-
ных сортов. Сколькими способами можно выбрать 8 пирожных из имею-
щихся в наличии 6 различных сортов? 
      Примечание. Если объединить все размещения из n элементов по k, состоящие из
одних и тех же элементов (не учитывая расположения) в классы эквивалентности, то ка-
ждому классу будет соответствовать ровно одно сочетание Cnk и наоборот:
                                         n!
                                Cnk =
                                       k!(n - k)!
      Пример. Для множества S = {a, b, c, d} из предыдущего примера число
различных двухэлементных сочетаний C42 = 4!/(2! 2!) = 6.
                       Sc = {(a ,b)(a, c)(a, d)(b, c)(b, d)(c, d)}.
      Задача. Сколько различных комбинаций может выпасть в спортлото
«5 из 36»:
                    C365 = 36! / 5!(36 – 5)! = 36! / 5! 31! = 6992,
а в спортлото «6 из 45» – C456 = 568260.

                        3.4.1. Сочетания с повторениями

       Сочетаниями из n элементов по k элементов с повторениями на-
зываются группы, содержащие k элементов, причем каждый элемент
принадлежит к одному из n типов.
       Например. Для множества S = {a, b, c, d} двухэлементные сочетания с
повторениями          ~
                      S c = {(a, a)(a, b)(a, c)(a, d)(b, b)(b, c)
(b, d)(c, c)(c, d)(d, d)}.
       Число различных сочетаний из n элементов по k c повторениями рав-
но
                                ~ k =Cn-1n+k-1 = Ckn+k-1
                                C
      Пример. Кости домино можно рассматривать как цифры 0, 1, 2, 3, 4, 5,
6. Число сочетаний по два элемента равно
                С72 =(n+k–1)! / (k!(n–1)!) = 8! / (2!6!) = 7×8/2 = 28.
Упражнения 3.4
      1. Сколькими способами можно выбрать 3 различные краски из
имеющихся 5?
      Решение. Сочетание трех различных красок из имеющихся пяти можно
выбрать С 53 способами, т. е. всего вариантов . . . . .
     2. Сколькими способами можно выбрать три пирожных из 6 различ-
ных сортов. Сколькими способами можно выбрать 8 пирожных из имею-
щихся в наличии 6 различных сортов?




                                       57

Страницы