ТГиК-2019-Семинар-16.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Величины

$$\bar{A}_n^k=n^k$$

$$A_n^k=\frac{n!}{(n-k)!}$$

$$P_n=A_n^n=n(n-1)\cdot...\cdot1=n!$$

Перестановки с повторениями

Общая задача перестановок с повторениями формулируется следующим образом:

Имеется n элементов k различных типов: n_1 элементов первого типа, n_2 элементов второго типа, ..., n_k элементов k-го типа, n=n_1+n_2+...+n_k. Сколько можно составить различных перестановок из этих элементов?

Перестановки такого типа называются перестановками с повторениями, их число обозначают следующим образом:

$$P(n_1,n_2,...,n_k)$$

Если бы все элементы были различны, то число перестановок равнялось бы n!.. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В самом деле, возьмем, например, перестановку $$aa...a$$ $$bb...b $$ .... $$xx...x$$ , в которой сначала выписаны все элементы первого типа, потом все элементы второго типа, ..., наконец, все элементы k-ого типа. В первой группе элементы (первого типа) можно переставлять друг с другом n1! способами. Но так как все эти элементы одинаковые, то такие перестановки ничего не меняют. Точно так же ничего не меняют n2! перестановок элементов во второй группе, ..., nk! перестановок элементов k-й группе. Например, в перестановке "ммаа" ничего не изменится, если мы поменяем местами первый и второй элементы или третий и четвертый.

Перестановки элементов в разных группах можно делать независимо друг от друга. Поэтому по правилу произведения элементы перестановки можно переставлять друг с другом n1!n2!...nk! способами так, что она остается неизменной. ТО же самое верно и для любого другого расположения элементов. Поэтому множество всех n! перестановок распадается на части, состоящие из n1! n2!...nk! одинаковых перестановок каждая.

Значит, число различных перестановок с повторениями, которые можно сделать из данных элементов, равно

$$P(n_1,n_2,...,n_k) = \frac{n!}{n_1!n_2!....n_k!}$$ (1)

где, напомним, n = n1 + n2 + ... + nk.

Пользуясь формулой (1), легко найти, например, сколько перестановок можно сделать из букв слова "математика". здесь у нас две буквы "м", три буквы "а", две буквы "т", по одной букве "е", "и" ,"к", а всего букв 10. Значит по формуле (1) число перестановок равно

$$P(2, 3, 2, 1, 1, 1) = \frac{10!}{2!*3!*2!*1!*1!*1!} = 151 200$$

Перестановки с повторениями естественно возникают в анаграммах - текстах с переставленными буквами. Например, слова "москва" и "смоква" - анаграммы. Когда - то анаграммы применялись учеными в качестве своеобразного "анонса", они в краткой форме формулировали суть открытия, а потом переставляли в нем буквы и отправляли письмо своим коллегам. Когда же печаталась книга с подробным изложением результата, в ней давалась расшифровка анаграммы.

Задачи на семинар и самостоятельную работу

1.На первые две линии шахматной доски произвольным образом ставятся белые и черные фигуры (по два коня, два слона, две ладьи, ферзь и король каждого цвета). Сколькими способами можно это сделать?

(Решение: $$P = \frac{16!}{2!*2!*2!*2!*2!*2!*1*1*1*1} $$ )

Сколькими способами можно расставить те же фигуры по всей доске?

(Решение: $$P = \frac{64!}{2!*2!*2!*2!*2!*2!*1*1*1*1} $$ )

А если расставляются и все пешки (по 8 пешек каждого цвета)?

(Решение: $$P = \frac{64!}{2!*2!*2!*2!*2!*2!*1*1*1*1*8!*8!} $$ )

2.Найдите сумму четырехзначных чисел, получаемых при все­возможных перестановках следующих 4 цифр: а) 1, 2, 3, 4;

(Решение: Всего можно получить 4! = 24 четырехзначных числа. Каждая из цифр встретится 6 раз на позиции единиц, 6 раз на позиции десяток, 6 раз на позиции сотен и 6 раз на позиции тысяч. Тогда сумма всевозможных чисел равна Р = (1 + 2 + 3 + 4) * 6 *(1000 + 100 + 10 + 1) = 10 * 6 * 1111 = 66660)

б) 1, 2, 2, 5;

(Решение: Здесь общее число перестановок равно Р(1, 2, 1) = 12, причем цифры 1 и 5 появляются в каждом разряде по 3 раза, а цифра 2 — 6 раз. Поэтому сумма цифр в каждом разряде 3 • 1 + 3 • 5 + 6 • 2 = 30. Общая сумма равна 30 + 300 + 3000 + 30 000 = 33330.

Ответ: 33 330 )

в) 1, 3, 3, 3;

(Решение: Р=4*3333-(2000+200+20+2)=12*1111-2*1111=11110)

г) 1, 1, 4, 4.

(Ответ: 16 665)

г) Найдите сумму всех пятизначных чисел, которые можно получить, переставляя цифры 0, 1, 2, 3, 4 (цифра 0 не должна быть первой).

(Решение: Если снять ограничение, что цифра 0 не является первой, по­лучим сумму 2 666 640. Сумма чисел, «начинающихся на 0», равна 66 660. Поэтому сумма пятизначных чисел, не начинающихся цифрой 0, равна 2 599 980.)

Сочетания без повторений

В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочета­ниях. Сочетаниями из n элементов по k называют любой выбор k элементов из имеющихся различных n элементов.

Формула для числа сочетаний легко получается из выведен­ной ранее формулы для числа размещений. В самом деле, составим сначала все сочетания из n элементов по k, записав каждое в виде некоторого размещения (т. е. упорядочив эле­менты каждого сочетания), а потом будем переставлять входя­щие в каждое сочетание элементы всеми возможными способа­ми. При этом получатся все размещения из n элементов по k, причем каждое только по одному разу. Но таких перестановок для каждого сочетания можно сделать k, а число этих сочетаний равно C_n^k. Значит,

$$k!C_n^k=A_n^k => C_n^k=\frac{A_n^k}{k!} = \frac{n!}{(n-k)!k!}$$

Задачи на семинар и самостоятельную работу

1.Труппа состоит из 10 артистов. Сколькими способами можно выбирать из нее в течение двух вечеров по 6 человек для участия в спектаклях так, чтобы эти составы не совпадали друг с другом?

$$C_{10}^6(C_{10}^6-1)$$

2.Из спортивного клуба, насчитывающего 30 членов, надо составить команду из 4 человек для участия в беге на 1000 м. Сколькими способами это можно сделать? А сколькими способами можно составить команду из 4 человек для участия в эстафете 100 + 200 + 400 + 800?

$$C_{30}^4=27405; A_{30}^4=657720$$

3.а) Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт есть хотя бы один туз? Ровно 1 туз? Не менее двух тузов? Ровно два туза? б) Сколькими способами можно выбрать из полной колоды, содержащей 52 карты, 6 карт так, чтобы среди них были все четыре масти?

  • а) Общее число способов вынуть 10 карт равно $$С_52^10$$. Число способов, при которых не выбирают ни одного туза, равно $$C_48^10$$. Поэ­тому хотя бы один туз будет в $$C_52^10-C_48^10$$ случаях. Ровно один туз в $$C_4^1 * C_48^9$$ случаях, не менее двух тузов в $$C_52^10-C_48^10-C_4^1*C_48^9$$ случаях и ровно два туза в $$C_4^2 * C_48^8$$ случаях (выбираем двух тузов и еще 8 карт).
  • б) Шесть карт по четырем мастям могут распределиться так: 3 + 1+ 1 + 1 или 2 + 2 + 1 + 1. С учетом выбора одной или двух мастей получаем ответ в виде:

$$C_{4}^1C_{13}^3(C_{13}^1)^3+C_{4}^2(C_{13}^2)^2(C_{13}^1)^2$$

4. Пять девушек и трое юношей играют в городки. Сколькими способами они могут разбиться на две команды по 4 человека, если в каждую команду должен входить хотя бы один юноша?

(Решение: В одной команде играет один юноша, а в другой — двое. Юношей можно разбить на команды 3 способами. После этого надо выбрать в первую команду 3 девушек из 5. Это можно сделать $$C_5^3 = 10$$ способами. Всего по правилу произведения получаем 30 спо­собов разбивки на команды.)

5. У одного человека есть 7 книг по математике, а у другого — 9 книг. Сколькими способами они могут обменять одну книгу одного на одну книгу другого? А 3 книги одного на 3 книги другого?

(Решение: Одну на одну — по правилу произведения 7 • 9 = 63 способа. Три на три — первый может выбрать книги для обмена C_7^3 = 35 спо­собами, а второй C_9^3 = 84 способами. Всего 35-84 = 2940 способов.)

6.Из группы, состоящей из 7 мужчин и 4 женщин, надо выбрать 6 человек так, чтобы среди них было не менее двух женщин. Сколькими способами это может быть сделано?

(Решение:Можно выбрать двух, трех ли четырех женщин и добрать недостающее число мужчин, получится $$C_4^2 * C_7^4 + C_4^3 * C_7^3 + C_4^4 * C_7^2 = 371$$ способ. А можно из всех способов вычесть способы без женщин или с 1 женщиной, опять получим $$C_{11}^6 - C_7^6 - C_4^1 * C_7^5 = 371$$ способ)

7.Рота состоит из 3 офицеров, 6 сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, двух сержантов и 20 рядовых? А если в отряд должны войти командир роты и старший по возрасту из сержантов?

(Решение: Офицера можно выбрать $$C_3^1$$ способами, сержантов $$C_6^2$$ способами и рядовых $$C_{60}^{20}$$ способами. Всего по правилу произведения получаем $$C_3^1 * C_6^2 * C_{60}^{20}$$ способов выбора. Если в отряде должен войти командир роты и старший из сержантов, то получаем $$C_5^1 * C_{60}^{20}$$ способов выбора.)

8.У Миши 6 друзей и ежедневно в течение 20 дней он приглашает к себе в гости троих из них так, что компания ни разу не повторяется. Сколькими способами он может это сделать?

(Решение: Так как С_6^3 = 20, то каждый способ выбора компании будет использован. Число перестановок этих способов равно 20!)

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

Мы уже говорили, что разобранная задача относится к типу задач на сочетания с повторениями. Общая формулировка этих задач такова: Имеются предметы п различных типов. Сколькими спосо­бами можно сделать из них комбинацию из к элементов, если не принимать во внимание порядок элементов в комбинации, при этом предметы одного типа могут повторяться?

Иными словами, различные комбинации должны отличаться количеством предметов хотя бы одного типа. Такие комбинации называют сочетаниями с повторениями из n элементов по k.

$$\bar{C}_n^k = \frac{(k + n - 1)!}{k!(n-1)!}=C_{n+k-1}^k$$

Задачи на семинар и самостоятельную работу

1.В почтовом отделении продаются открытки 10 видов.

а)Сколь­кими способами можно купить в нем 12 открыток?

(Решение: $$\bar{C}_{10}^2 = C_{21}^{12}$$)

б)Сколькими способами можно купить 8 открыток?

(Решение: $$\bar{C}_{10}^8 = C_{17}^{8}$$)

в)Сколькими способами можно купить 8 различных открыток?

(Решение: $$C_{10}^{8}$$)

2. а)Сколькими способами могут выпасть три различные игральные кости?

(Решение: Если кости различны (или одна кость бросается 3 раза), то $$\bar{A}_{6}^3 = 6^3$$)

б)Во скольких случаях хотя бы на одной кости выпадет 6 очков?

(Решение: $$\bar{A}_{6}^3 - \bar{A}_{5}^3 = 6^3 - 5^3$$)

в)Во скольких случаях ровно на одной кости выпадет 6 очков?

(Решение: $$\C_{3}^1 * \bar{A}_{5}^2 = 3 * 5^2$$)

г)Во скольких случаях ровно на одной кости выпадет 6 очков, а на другой — 3 очка?

(Решение: $$ 3 * 2 * 4 $$ )

А если кости неразличимы?

а)(Решение: Если кости неразличимы, то $$\bar{C}_{6}^3 = C_{8}^3 = 56$$)

б)(Решение:$$\bar{С}_{6}^3 - \bar{С}_{5}^3 = \bar{С}_{6}^2 = 21$$)

в)(Решение: $$\bar{C}_{5}^2 = C_{6}^2 = 15$$)

г)(Решение: $$ 4 $$ )

3.Сколько существует треугольников, у которых длина каждой стороны принимает одно из значений 4, 5, 6, 7?

(Решение: Неравенство треугольника всегда будет выполнено, поэтому мы имеем сочетания с повторениями их элементов 4 типов по три элемента в сочетании. Их число равно $$\bar{C}_{4}^3 = C_{6}^3 = 20$$)

Перестановки с ограничениями

Задачи на семинар и самостоятельную работу

1.Сколькими способами можно переставить буквы слова «пере­шеек» так, чтобы четыре буквы «е» не шли подряд?

(Решение: В перестановках, где 4 буквы «е» идут подряд, их можно объединить и считать одной буквой. Поэтому число таких перестано­вок равно 5!. Остается Р(4, 1, 1, 1, 1) - 5! = 1560 перестановок.)

2.На окружности отмечено n точек. Сколько существует различ­ных многоугольников (необязательно выпуклых), вписанных в эту окружность, вершинами которых служат данные точки? А сколько выпуклых многоугольников?

(Решение: Каждый k-угольник определяется выбором k точек из n, взятых в определенном порядке, причем циклическая перестановка точек и изменение направления обхода вершин не меняет k-угольника. Поэтому различных k-угольников будет $$\frac{1}{2k}A_n^k$$, а вообще число многоугольников $$\sum_{i=3}^n \frac{1}{2k}A_n^k $$. Число выпуклых многоугольников равно $$\sum_{i=3}^n C_n^k $$ )

3. а)Сколькими способами можно переставлять буквы в слове «фацетия» так, чтобы не менялся порядок гласных букв?

(Решение: Выпишем гласные в данном порядке. Тогда для буквы "ф" имеем 5 мест. После того как она вписана, имеем 6 мест для буквы "ц" и, наконец, 7 мест для буквы "т". Всего $$5 * 6 * 7 = 210$$ способов.)

б)А в слове « параллелизм » ?

(Решение: Для слова « параллелизм » число способов равно $$\frac {A_{11}^7}{P_3} = 277 200$$ (следует учесть, что буква "л" входит в это слово трижды) )

4.Сколькими способами можно переставить буквы слова «пас­тух» так, чтобы между двумя гласными были две согласные буквы?

(Решение: сначала фиксируем последовательность гласных (2 способа). затем поставим между этими гласными 4 согласные ($$A_4^2 = 12$$ способов. Первую из оставшихся согласных можно поставить до или после обеих гласных, и для второй имеем уже три места. Всего получаем $$ 2 * 12 * 2 * 3 = 144$$ способа)

5.Сколько пятизначных чисел можно составить из цифр числа 12312343 так, чтобы три цифры 3 не шли друг за другом?

(Решение: Общее количество пятизначных чисел, которые можно составить из данных цифр, равно $$ 3 * \frac{5!}{2!} + C_3^2C_2^1 * \frac{5!}{(2!)^2} + C_3^1 * \frac{5!}{3!} + C_2^1 * \frac{5!}{3!2!} = 440$$. Из их числа в $$3P_3 + 2 * \frac{P_3}{2!} = 24$$ цифра 3 идет подряд три раза. Получаем 416 искомых чисел. )