Математика. Раздел 1. Дискретная математика. Тетрадь 1. Казанцев Э.Ф. - 47 стр.

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

то есть чис ло (3, 30) — со че та ний с по вто ре ния ми. Ис поль зуя ут вер жде -
ние 4 по лу ча ем, что ис ко мое чис ло рав но:
C C C
3
30
3 30 1
30
32
30
496= = =
+ -
.
1.2.3 Раз бие ния
Под счи та ем чис ло раз бие ний ко неч но го мно же ст ва X, где
X n=
,
на k под мно жеств X
1
, X
2
, ..., X
k
(k ³ 1) та ких, что ка ж дое X
i
со дер жит n
i
эле -
мен тов, то есть
X X
i
i
k
=
=
1
U
;
X X
i j
Ç = Æ
; при i ¹ j; |X
i
| = |n
i
|, i = 1, 2, ..., k.
Оче вид но, что при этом
n n
i
k
!
=
å
=
1
. От ме тим, что для не ко то рых но -
ме ров i воз мож но X
i
= Æ. Чис ло ука зан ных раз бие ний при фик си ро ван -
ных n
i
обо зна чим че рез
C
n
n n
k1
K
.
Ут вер жде ние 7:
C
n
n n
n
n n
k
k1
1
K
K
=
!
!
.
Как от ме ча лось ра нее, ка ж дое из мно жеств X
i
мож но рас смат ри -
вать как со че та ние без по вто ре ний. Пред ва ри тель но до ка жем спра вед -
ли вость фор му лы
C C C C
n
n n
n
n
n n
n
n n n
n
k
k
k1 1
1
2
1 1
K
K
K=
- - - -
-
.
Дей ст ви тель но, для об ра зо ва ния со че та ния, со от вет ст вую ще го
мно же ст ву X
1
, мо гут быть ис поль зо ва ны все эле мен ты мно же ст ва X, то
есть мно же ст во X
1
мо жет быть вы бра но
C
n
n
1
спо со ба ми. По сле вы бо ра X
1
мно же ст во X
2
мо жет быть вы бра но
C
n n
n
-
1
2
спо со ба ми (так как X
2
яв ля ет ся
под мно же ст вом мно же ст ва X \ X
1
и |X \ X
1
| = n – n
1
), и для лю бо го i, где 2 £ i
£ k, по сле вы бо ра мно жеств X
1
, ..., X
i–1
мно же ст во X
i
мо жет быть вы бра но
C
n n n
n
i
i
- - -
-1 1
K
спо со ба ми. Но то гда по пра ви лу про из ве де ния вы бор упо ря до -
чен ной по сле до ва тель но сти мно жеств X
1
, ...,X
k
мож но осу ще ст вить
C C C
n
n
n n
n
n n n
n
k
k1
1
2
1 1
- - - -
-
K
K
спо со ба ми, то есть фор му ла до ка за на. Ис поль зуя те -
перь эту фор му лу, а так же ут вер жде ние 3 и про из во дя не об хо ди мые со -
кра ще ния, по лу ча ем, что до ка зы вае мое ут вер жде ние спра вед ли во.
При мер 1. В сту ден че ской груп пе, со стоя щей из 25 че ло век, при
вы бо ре про фор га за вы дви ну тую кан ди да ту ру про го ло со ва ли 12 че ло -
век, про тив — 10, воз дер жа лись — 3. Сколь ки ми спо со ба ми мог ло быть
про ве де но та кое го ло со ва ние?
47
то есть число (3, 30) — сочетаний с повторениями. Используя утвержде-
ние 4 получаем, что искомое число равно: C 330 = C 330+ 30 -1 = C 3230 = 496.

       1.2.3 Разбиения
      Подсчитаем число разбиений конечного множества X, где X = n,
на k подмножеств X1, X2, ..., Xk (k ³ 1) таких, что каждое Xi содержит ni эле-
                    k
ментов, то есть U X i = X ; X i Ç X j = Æ; при i ¹ j; |Xi| = |ni|, i = 1, 2, ..., k.
                   i =1
                                          k
       Очевидно, что при этом å n ! = n. Отметим, что для некоторых но-
                                         i =1

меров i возможно Xi = Æ. Число указанных разбиений при фиксирован-
ных ni обозначим через C nn 1 Kn k .
       Утверждение 7:
                                     n Kn k              n!
                                  Cn 1          =              .
                                                    n1 ! K n k

      Как отмечалось ранее, каждое из множеств Xi можно рассматри-
вать как сочетание без повторений. Предварительно докажем справед-
ливость формулы C nn 1 Kn k = C nn 1 C nn-2 n 1 KC nn-k n 1 -K- n k - 1 .
      Действительно, для образования сочетания, соответствующего
множеству X1, могут быть использованы все элементы множества X, то
есть множество X1 может быть выбрано C nn 1 способами. После выбора X1
множество X2 может быть выбрано C nn-2 n 1 способами (так как X2 является
подмножеством множества X \ X1 и |X \ X1| = n – n1), и для любого i, где 2 £ i
£ k, после выбора множеств X1, ..., Xi–1 множество Xi может быть выбрано
C nn-i n 1 -K- n i - 1 способами. Но тогда по правилу произведения выбор упорядо-
ченной последовательности множеств X1, ...,Xk можно осуществить
  n                 n
C n 1 C nn-2 n 1 KC n -k n 1 -K- n k - 1 способами, то есть формула доказана. Используя те-
перь эту формулу, а так же утверждение 3 и производя необходимые со-
кращения, получаем, что доказываемое утверждение справедливо.
      Пример 1. В студенческой группе, состоящей из 25 человек, при
выборе профорга за выдвинутую кандидатуру проголосовали 12 чело-
век, против — 10, воздержались — 3. Сколькими способами могло быть
проведено такое голосование?
                                                                                        47

Страницы