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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

Ре ше ние:
Пусть X – мно же ст во сту ден тов в груп пе, X
1
– мно же ст во сту ден -
тов, про го ло со вав ших за вы дви ну тую кан ди да ту ру, X
2
— мно же ст во сту -
ден тов, воз дер жав ших ся от го ло со ва ния. То гда, |X| = 25, |X
1
| = 12,
|X
2
| = 10, |X
2
| = 3, X = X
1
È X
2
È X
3
; X
i
Ç X
j
= Æ при i ¹ j, а сле до ва тель но,
ис ко мое чис ло рав но
C
25
12 10 3, ,
.
Ис поль зуя ут вер жде ние 7, по лу ча ем:
C
25
12 10 3
25
12 10 3
1487285800
, ,
!
! ! !
=
× ×
=
.
Ут вер жде ние 8: Чис ло
C
n
n n
k1
K
, где n
i
³ 0, рав но чис лу (k,n)-раз ме -
ще ний с по вто ре ния ми, сре ди эле мен тов ко то рых со дер жит ся n
1
эле -
мен тов 1-го ти па, n
2
эле мен тов 2-го ти па и так да лее, n
k
эле мен тов k-го
ти па.
При мер 2. Сколь ки ми спо со ба ми мож но рас кра сить квад рат, раз -
де лен ный на 9 час тей (ри су нок 1.2.2), че тырь мя цве та ми та ким об ра зом,
что бы в пер вый цвет бы ли ок ра ше ны 3 час ти, во вто рой — 2, в тре тий —
3, в чет вер тый — 1?
Ре ше ние:
Пусть X – мно же ст во цве тов, где |X | = 4. То гда ка ж дое рас кра ши -
ва ние, рас смат ри вае мое как по сле до ва тель ность цве тов, в ко то рые ок -
ра ши ва ют ся про ну ме ро ван ные час ти квад ра та, яв ля ет ся упо ря до чен -
ной вы бор кой с по вто ре ния ми объ е ма 9 из мно же ст ва X, то есть (4,9) —
раз ме ще ние с по вто ре ния ми. При этом нас ин те ре су ют раз ме ще ния с
за дан ной ком би на ци ей эле мен тов (3 эле мен та — пер вый цвет, 2 — вто -
рой, 3 — тре тий, 1 — чет вер тый). Но то гда, ис поль зуя ут вер жде ние 8,
по лу ча ем, что ис ко мое чис ло равно:
C
9
3 2 3 1
9
3 2 3
5040
, , ,
=
× ×
=
!
! ! !
.
48
1 2 3
6 5 4
7 8 9
Рис. 1.2.2
       Решение:
       Пусть X – множество студентов в группе, X1 – множество студен-
тов, проголосовавших за выдвинутую кандидатуру, X2 — множество сту-
дентов, воздержавшихся от голосования. Тогда, |X| = 25, |X1| = 12,
|X2| = 10, |X2| = 3, X = X1 È X2 È X3; Xi Ç Xj = Æ при i ¹ j, а следовательно,
                           12,10, 3
искомое число равно C 25            .
       Используя утверждение 7, получаем:
                        12,10, 3          25!
                      C 25       =                  = 1487285800.
                                     12 ! ×10! × 3!
      Утверждение 8: Число C nn 1 Kn k , где ni ³ 0, равно числу (k,n)-разме-
щений с повторениями, среди элементов которых содержится n1 эле-
ментов 1-го типа, n2 элементов 2-го типа и так далее, nk элементов k-го
типа.

       Пример 2. Сколькими способами можно раскрасить квадрат, раз-
деленный на 9 частей (рисунок 1.2.2), четырьмя цветами таким образом,
чтобы в первый цвет были окрашены 3 части, во второй — 2, в третий —
3, в четвертый — 1?
                                       1        2       3
                                       6        5       4
                                       7        8       9

                                           Рис. 1.2.2



      Решение:
      Пусть X – множество цветов, где |X | = 4. Тогда каждое раскраши-
вание, рассматриваемое как последовательность цветов, в которые ок-
рашиваются пронумерованные части квадрата, является упорядочен-
ной выборкой с повторениями объема 9 из множества X, то есть (4,9) —
размещение с повторениями. При этом нас интересуют размещения с
заданной комбинацией элементов (3 элемента — первый цвет, 2 — вто-
рой, 3 — третий, 1 — четвертый). Но тогда, используя утверждение 8,
получаем, что искомое число равно:
                                                   9!
                             C 93, 2, 3,1 =                = 5040.
                                              3! × 2! × 3!
48

Страницы