Материал: Prak_alg

41 

ЗАДАЧИ

И

УПРАЖНЕНИЯ

33.

Сколькими

способами

можно

расставить

белые

фигуры

  (2 

коня

, 

2 

слона

, 2 

ладьи

, 

ферзя

и

короля

) 

на

первой

линии

шахматной

доски

?  

Ответ

:

 5 040. 

34.

Четыре

автора

должны

написать

книгу

из

 17 

глав

, 

причём

первый

и

третий

должны

написать

по

 5 

глав

, 

второй

 – 4 

главы

, 

а

четвёртый

 – 3 

главы

книги

. 

Сколькими

способами

можно

распределить

главы

между

авторами

?  

Ответ

:

!

3

!

4

!

5

!

5

!

17

. 

35.

Сколько

существует

перестановок

элементов

 1, 2

,

...,n , 

в

которых

элемент

 1 

находится

не

на

своём

месте

? 

Ответ

:

(

)(

)

1

1

n

n

-

-

! 

36.

Сколько

ожерелий

можно

составить

из

семи

бусинок

разных

раз

-

меров

? 

Ответ

:

 300. 

37.

Сколько

различных

браслетов

можно

сделать

из

четырёх

одина

-

ковых

рубинов

, 

пяти

одинаковых

сапфиров

и

шести

одинаковых

изумру

-

дов

, 

если

в

браслете

должны

быть

все

  15 

камней

? 

Сколькими

способами

можно

из

этих

камней

выбрать

три

камня

для

кольца

? 

Ответ

:

(

)

30

6

,

5

,

4

P

; 

10

1

2

3

1

3

=

+

+

C

. 

38.

Сколькими

способами

можно

разбить

(

п

  + 

т

  + 

р

)

предметов

на

три

группы

так

, 

чтобы

в

одной

было

п

,

в

другой

т

,

а

в

третьей

р

предметов

? 

Ответ

:

(

)

!

p

!

m

!

n

!

p

m

n

+

+

. 

39.

Сколькими

способами

можно

переставить

буквы

в

слове

  

а

) «

космос

?»                                              

б

) «

тартар

»? 

Ответ

:

а

) 180; 

б

) 90. 

40.

Сколькими

способами

можно

переставить

цифры

числа

  

а

) 12 341 234?                                            

б

) 12 345 234? 

Ответ

:

а

) 

!

5

21

´

;                                    

б

) P(1,2,2,2,1). 

42 

41.

Сколько

существует

вариантов

того

, 

что

три

человека

, 

сдавшие

свои

шляпы

в

гардероб

, 

не

получат

в

точности

свою

шляпу

?  

Ответ

:

2

=

N

. 

42.

Четыре

человека

сдают

свои

шляпы

в

гардероб

. 

Предполагая

, 

что

шляпы

возвращаются

наугад

, 

найти

число

случаев

и

вероятность

того

, 

что

в

точности

  k 

человек

получат

свои

шляпы

. 

Рассмотреть

все

значения

k (k = 0, 1, 2, 3, 4 ). 

Ответ

:

Имеем

  9,  8,  6,  0,  1 

случаев

с

вероятностями

3 1 1

1

, , , 0,

8 3 4

24

соответственно

. 

Замечание

.

Вероятность

равна

числу

Р

(

А

)

=

n

m

, 

где

 n – 

общее

число

комбинаций

, 

т

 –

число

 «

благоприятных

» 

комбинаций

. 

 
 

2.3 

Формула

включений

и

исключений

Пусть

имеется

N

предметов

и

п

свойств

a

1

, a

2

, …, a

n

. 

Каждый

из

рас

-

сматриваемых

предметов

может

обладать

одним

или

несколькими

из

этих

n 

свойств

. 

Обозначим

через

 N(

a

i1

, a

i2

, …, a

is

) 

число

предметов

, 

обладающих

свойствами

  a

i1

,  a

i2

,  …  ,  a

is

(

и

, 

быть

может

, 

некоторыми

другими

), 

а

через

N(

a

1

,

a

2

,…,

a

n

) 

–

число

предметов

, 

не

обладающих

свойствами

a

i1

, a

i2

, …, a

is

. 

Например

, N(

a

1

, a

3

, 

a

4

) – 

число

предметов

, 

обладающих

свойствами

a

1

, 

a

3

, 

но

не

обладающих

свойством

a

4

.

Справедлива

формула

  

N(

a

1

,

a

2

,…,

a

n

) = N – N(

a

1

) – N(

a

2

) – …– N(

a

n

) + N(

a

1 

, a

2

) + 

+ N(

a

1

 , a

3

) +…+ N(

a

1 

, a

n

) +…+ N(

a

n–1

 , a

n

) – N(

a

1

 , a

2

 , a

3

) –…–        (9) 

– N(

a

n–2

, a

–1

, a

n

) +…+ (–1)

n

 N(

a

1

, a

2

, … , a

n

). 

Формула

 (9) 

н

a

зыв

ae

т

c

я

формулой

включений

и

исключений

.

Здесь

слагаемые

включают

все

комбинации

свойств

a

1

,a

2

,…,a

n

без

учёта

их

по

-

рядка

; 

знак

  «+» 

ставится

, 

если

число

учитываемых

свойств

чётно

, 

и

знак

  

 « – », 

если

это

число

нечётно

. 

Пример

 14.

В

результате

опроса

 70 

студентов

выяснилось

, 

что

 45 

из

них

занимаются

спортом

, 29 – 

музыкой

, 9 – 

и

спортом

, 

и

музыкой

. 

Сколько

студентов

из

числа

опрошенных

не

занимаются

ни

спортом

, 

ни

музыкой

.  

Решение

.

Чтобы

применить

формулу

  (9), 

обозначим

через

a

1

(

a

2

)  –

свойство

студента

, 

состоящее

в

том

, 

что

он

занимается

спортом

 (

музыкой

).  

43 

Тогда

имеем

N = 70, N(a

1

) 

= 45, 

N(a

2

) = 29, N(a

1

,a

2

) = 9.

Нужно

найти

число

N(

a

1

,

a

2

)

. 

По

формуле

 (9) 

получаем

N(

a

1 

, 

a

2

) = N 

– 

N(a

1

) 

–

 N(a

2

) + N(a

1

,a

2

) = 70 

– 

45 

–

 29 + 9 = 5. 

Предположим

теперь

, 

что

число

N(a

1

,a

2

,...,a

n

)

зависит

не

от

самых

этих

свойств

, 

а

лишь

от

их

числа

. 

Введём

следующие

обозначения

 : N

(0)

 = N, N

(1)

 = N(

a

1

) =…= N(

a

n

),  

N

(2)

 = N(

a

1

, a

2

) =…= N(

a

n-1

, a

n

), … , N

(k)

 = N(

a

1

, … , a

k

) =…= N(

a

n–k+1

, … , a

n

), 

N

(n)

 = N(

a

1

, a

2

, …, a

n

), 

N

=N(

a

1

,

a

2

,…,

a

n

). 

Тогда

формула

 (9) 

примет

вид

: 

N

=N

(0) 

– 

1

n

C

N

(1) 

+ 

2

n

C

N

(2) 

–…+(–1)

n

n

n

C

N

(n)

, 

или

  

N

=

å

=

n

k

0

(–1)

k

k

n

C

N

(k)

                                (10) 

Очевидно

, 

формула

 (10) 

есть

частный

случай

формулы

 (9). 

Пример

  15.

Пусть

имеется

п

карточек

, 

пронумерованных

от

 1 

до

п

.

Сколькими

способами

можно

расположить

их

в

ряду

так

, 

чтобы

ни

для

ка

-

кого

 i (1 

£

 i 

£

 n) 

карточка

с

номером

 i 

не

занимала

бы

 i-

го

места

? 

Решение

. 

Число

всевозможных

расположений

 (

перестановок

) n 

карто

-

чек

в

ряд

равно

 P

n 

= n! = N

(0)

. 

Обозначим

через

a

i

свойство

: «i-

я

карточка

за

-

нимает

место

с

номером

 i (i = 1, 2, …, n)». 

Тогда

 N(

a

i

) = N

(1)

 = P

n – 1

 = (n – 1)! – 

число

перестановок

всех

карточек

в

ряду

, 

кроме

 i-

й

, 

которая

остаётся

на

 i-

м

месте

; N(

a

i

, a

j

) = N

(2)

 = P

n – 2

 = (n – 2)! – 

число

перестановок

всех

карточек

в

ряду

, 

кроме

двух

карточек

с

номерами

 i 

и

 j, 

остающихся

на

месте

, 

т

. 

е

. 

на

  

i-

м

и

 j-

м

местах

, 

и

т

. 

д

. N(

a

i1

, a

i2

, … , a

ik

) = N

(k)

 = P

n–k

 = (n – k)! – 

число

рас

-

положений

, 

при

которых

карточка

с

номером

  i

s

занимает

  «

своё

» 

место

i

s

 (s = 

k

,

1

). 

По

формуле

 (10) 

получаем

, 

что

искомое

число

N

равно

( )

( ) ( ) ( )

( )

å

å

å

=

=

-

=

-

=

-

-

-

=

-

=

n

k

k

n

k

k

k

n

n

k

k

n

k

k

n

k

n

k

n

k

n

P

C

N

0

0

0

1

1

1

1

!

!

!

!

!

!

Заметим

, 

что

полученное

число

способов

располагаться

любой

  i-

й

карточки

не

на

  i-

м

месте

согласуется

с

формулой

  «

числа

беспорядков

» 

(

см

. (8) 

на

стр

. 41). 

ЗАДАЧИ

И

УПРАЖНЕНИЯ

1.

При

обследовании

читательских

вкусов

студентов

оказалось

, 

что

60  % 

студентов

читает

журнал

А

,  50  %  – 

журнал

В

,  50  %  – 

журнал

С

, 

30 %  – 

журналы

А

и

В

,  20  %  – 

журналы

В

и

С

,  40  %  – 

журналы

А

и

С

, 

10 % – 

журналы

А

, 

В

и

С

. 

Какой

процент

студентов

: 

а

) 

не

читает

ни

одного

44 

из

этих

журналов

? 

б

) 

читает

в

точности

два

журнала

? 

в

) 

читает

только

один

журнал

В

? 

Задачу

решить

двумя

способами

  (

с

помощью

формулы

(9) 

и

кругов

Эйлера

).  

Ответ

:

а

) 20 %; 

б

) 60 %. 

2.

При

опросе

 13 

человек

, 

каждый

из

которых

знает

по

крайней

мере

один

иностранный

язык

, 

выяснилось

, 

что

  10 

человек

знают

английский

язык

, 7 – 

немецкий

, 6 – 

испанский

, 5 – 

английский

и

немецкий

, 4 – 

англий

-

ский

и

испанский

,  3  – 

немецкий

и

испанский

. 

Сколько

человек

знают

: 

а

) 

все

три

языка

? 

б

) 

ровно

два

языка

? 

в

) 

только

английский

язык

? 

Ответ

:

 2, 6, 3. 

3.

На

экскурсию

поехало

 92 

человека

. 

Бутерброды

с

колбасой

взяли

47 

человек

, 

с

сыром

 – 38 

человек

; 

с

ветчиной

 – 42 

человека

; 

и

с

сыром

, 

и

с

колбасой

 – 28 

человек

; 

и

с

колбасой

, 

и

с

ветчиной

 – 31 

человек

; 

и

с

сыром

, 

и

с

ветчиной

 – 26 

человек

. 

Все

три

вида

бутербродов

взяли

 25 

человек

. 

Не

-

сколько

человек

вместо

бутербродов

взяли

пирожки

. 

Сколько

человек

взя

-

ли

с

собой

пирожки

? 

Ответ

:

 25 

человек

. 

4.

Найти

количество

натуральных

чисел

, 

не

превосходящих

  1000 

и

не

делящихся

ни

на

одно

из

чисел

 3, 5 

и

 7? 

Ответ

:

 457. 

 
5.

Найти

количество

натуральных

чисел

, 

не

превосходящих

  1000 

и

не

делящихся

ни

на

одно

из

чисел

 6, 15 

и

 10? 

Ответ

:

 734. 

6.

Показать

, 

что

если

п

 = 30

т

,

то

количество

натуральных

чисел

, 

не

превосходящих

п

и

не

делящихся

ни

на

одно

из

чисел

 6, 10 

и

 15, 

равно

22m. 

 
7.

Сколько

неотрицательных

целых

чисел

, 

меньших

миллиона

, 

со

-

стоит

только

из

цифр

 1, 2, 3, 4? 

2.4 

Задачи

с

ограничениями

Рассмотрим

в

данном

параграфе

комбинаторные

задачи

сначала

с

ог

-

раничениями

на

порядок

элементов

, 

когда

на

порядок

элементов

накла

-

дываются

некоторые

дополнительные

условия

. 

В

таких

задачах

удобно

45 

применять

метод

  – 

объединение

нескольких

одинаковых

элементов

в

блоки

.  

Далее

рассмотрим

задачи

на

разбиения

, 

где

требуется

разделить

элементы

на

две

или

более

групп

в

соответствии

с

некоторыми

условиями

, 

и

требуется

найти

число

всевозможных

различных

способов

раздела

. 

При

этом

необходимо

учитывать

, 

существенен

ли

порядок

элементов

в

группах

, 

различаем

ли

мы

элементы

, 

входящие

в

группы

, 

и

сами

группы

и

т

. 

д

. 

При

решении

этих

задач

обычно

элементы

располагают

в

ряд

и

применяют

так

называемый

метод

введения

перегородок

. 

Пример

 16.

Имеются

предметы

 k 

сортов

 : n

1 

предметов

одного

сорта

, 

n

2

предметов

другого

сорта

, … , n

k 

предметов

 k-

го

сорта

, 

где

все

предметы

одного

сорта

всё

же

различны

друг

от

друга

. 

Найти

число

перестановок

этих

предметов

, 

в

которых

все

предметы

одного

и

того

же

сорта

стоят

ря

-

дом

. 

Решение

.

Из

данных

 k 

сортов

 (

блоков

) 

можно

сделать

 P

k 

= k! 

пере

-

становок

. 

Но

ещё

можно

переставлять

предметы

внутри

блоков

 n

1

!, n

2

!, … , 

n

k

! 

способами

. 

Далее

по

правилу

произведения

имеем

  n

1

!n

2

!…n

k

!k! 

пере

-

становок

.  

Пример

  17.

Сколькими

способами

можно

переставить

буквы

слова

«

перемет

» 

так

, 

чтобы

три

буквы

 «

е

» 

не

шли

подряд

? 

Решение

.

Объединим

все

буквы

 «

е

» 

в

блок

 «

еее

». 

Число

перестано

-

вок

, 

в

которых

все

три

буквы

 «

е

» 

идут

подряд

, 

равно

числу

перестановок

из

 5-

ти

объектов

 : «

еее

», «

п

», «

м

», «

р

», «

т

», 

т

. 

е

. P

5 

= 5! 

Всего

же

переста

-

новок

с

повторениями

из

букв

данного

слова

можно

составить

P(3,1,1,1,1) = 840. 

Значит

, 

искомое

число

перестановок

, 

где

три

буквы

 «

е

» 

не

идут

рядом

равно

 N = 840 – 120 = 720 (

способов

). 

Пример

  18.

Сколькими

способами

можно

расставить

  m 

нулей

и

  k 

единиц

так

, 

чтобы

никакие

две

единицы

не

стояли

рядом

? 

Решение

.

Выпишем

сначала

 m 

нулей

. 

Для

единиц

получается

 (m + 1) 

место

 (

одно

впереди

, (m – 1) 

в

промежутках

между

нулями

и

одно

сзади

). 

На

любые

из

этих

  (m  +  1) 

мест

можно

поставить

одну

из

  k 

единиц

. 

Это

можно

осуществить

1

k

m

C

+

способами

, 

причём

 k 

£

 m + 1. 

Пример

  19.

На

полке

стоят

  12 

книг

. 

Сколькими

способами

можно

выбрать

из

них

 5 

книг

так

, 

чтобы

никакие

две

из

них

не

стояли

рядом

? 

Решение

.

Зашифруем

каждый

выбор

книг

последовательностью

из

нулей

и

единиц

следующим

образом

: 

каждой

оставленной

книге

сопоста

-

вим

 0, 

а

каждой

взятой

 – 1. 

В

результате

получим

последовательность

из

 5 

единиц

и

  7 

нулей

, 

причём

в

последовательности

не

будет

двух

подряд