67597

Основные соотношения комбинаторики

Лекция

Математика и математический анализ

Сколькими способами можно в совокупности добраться от Москвы до райцентра через Уфу 1. Сколькими способами можно выбрать конверт с маркой 1. Сколькими способами можно сделать этот выбор 1. Сколькими способами можно выбрать на шахматной доске белую и черную клетки не лежащие на одной горизонтали или вертикали...

Русский

2014-09-12

217 KB

5 чел.

Основные соотношения комбинаторики

Литература

1) Бронштейн Е.М. Комбинаторика в задачах. Методические указания. Уфа: УГАТУ. 1988.

1. Основной принцип комбинаторики. 

1.1. От Москвы до Уфы можно добраться поездом, самолетом, теплоходом, а от Уфы до райцентра поездом, самолетом, автобусом. Сколькими способами можно в совокупности добраться от Москвы до райцентра через Уфу?

1.2. Есть конверты без марок 5 видов и марки 4 видов. Сколькими способами можно выбрать конверт с маркой?

1.3. Из 12 слов мужского рода, 9 женского и 10 среднего нужно выбрать по одному слову каждого рода. Сколькими способами можно сделать этот выбор?

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

1.5. (Обобщение). Если элемент а1 можно выбрать n1 способами, после каждого выбора следующий за ним элемент а2 можно выбрать n2 способами, …, после выбора элементов а1, …, аk-1 элемент аk выбирается nk способами, т.е.

a1n1,

a2n2,

………

amnm,

то сколькими способами можно выбрать вектор (a1, …, am)? Ответ: n1n2nm.

Ответ задачи 1.5 называется основным принципом комбинаторики или принципом произведения.

2. Размещение с повторениями

2.1. Замок в автоматической камере хранения содержит 4 диска, на каждом из которых записаны цифры 0,1,…,9. Сколько различных кодов можно получить?

2.2. В группе из 25 человек разыгрывается три различных приза. Призы могут достаться одному человеку, двоим, троим. Сколькими способами призы могут распределиться?

2.3. В пачке 20 экзаменационных билетов. Каждый студент получает билет, отвечает на него, билет возвращается в пачку и после этого заходит следующий студент. Сколько различных вариантов раздачи билетов существует для 10 студентов?

2.4. На складе имеется 7 рулонов ткани различных цветов и 5 различных стульев. Каждого рулона достаточно для обивки всех стульев. Сколькими способами можно обить стулья?

2.5. (Обобщение). В пачке n карточек с номерами. Исследователь достает карточку, записывает номер и возвращает карточки назад. После этого он снова достает карточку и т.д. Сколько различных записей может быть после того, как доставалось k карточек? . (Комбинации 1-2-3, 1-3-2 и т.д. считаются разными.)  Ответ:.

3. Размещение без повторений

3.1. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из 5 языков на любой другой? А если языков 10?

3.2. Каков будет ответ в задаче 2.2, если каждый человек может получить лишь один приз?

3.3. Каков будет ответ в задаче 2.3, если экзаменатор не возвращает в пачку использованный билет?

3.4. Каков будет ответ в задаче 2.4, если каждого рулона ткани хватит только на один стул?

3.5. Пусть в коробке имеется n карточек. Достается одна из них, причем в коробку не возвращается. Так повторяется k раз. Сколько существует различных комбинаций выбора карточек. (Комбинации 1-2-3, 1-3-2 и т.д. также считаются разными.  

3.5. (Обобщение). Пусть дано множество А, содержащее n элементов. Сколько существует различных векторов в множестве Аk, все компоненты каждого из которых различны?

Ответ: - число размещений из n по .k.

4. Перестановки

4.1. Сколькими способами можно сформировать очередь из 5 человек?

4.2. Каков будет ответ в задаче 3.3, если студентов 20?

4.3. Каков будет ответ в задаче 3.4, если стульев 7?

  1.  (Обобщение). Сколькими способами элементы n- элементного множества А можно расположить в цепочку?

Ответ: Рn=n(n-1)1=n! - число перестановок из n.

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

5.1. В шахматном турнире участвует 10 человек. Сколько партий должно состояться, если каждая пара игроков должна встретиться один раз?

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

5.3. Каков ответ в задаче 3.2, если все призы одинаковые?

5.4. Каков ответ в задаче 3.4, если все стулья одинаковые?

  1.  (Обобщение). Сколько различных m- элементных подмножеств содержится в n - элементном множестве?

Ответ:

- число сочетаний из n по m. Числа Сnm иначе называются биноминальными коэффициентами.

Указание: Каждое сочетание расщепляется на Pm размещений.

6. Свойства биномиальных коэффициентов

, mn

Принимая во внимание, что 0!=1 из определения  получим

, .

Свойства биномиальных коэффициентов

1.

2.

3.

Бином Ньютона

Доказательство методом полной математической индукции

Для m=1

Индукционный переход

(заменим в первой сумме n на n'=n+1)

(согласно свойству 2)

,

что и требовалось доказать.

6.3. Треугольник Паскаля есть таблица, составленная так:

      1

   1  1

  1  2  1

 1  3  3  1

Каждое число равно сумме двух, стоящих над ним(считаем, что на пустых местах стоят нули). Как найти m число в n строке?

7.Разбиения множества.

Cn – это фактически число способов, которыми можно n – элементное множество разбить на два подмножества – одно из m элементов, а второе – из (n-m) элементов.

7.1.Из группы в 25 человек 12 человек необходимо направить на практику на одно предприятие, 10 – на второе, а 3 – на третье. Каким числом способов это можно сделать?

7.2.Имеется 4 предмета 1 типа, 3 – второго, 5 – третьего. Сколько существует различных перестановок этих предметов?

7.3.(Обобщение).n элементов надо разбить на m групп пак, чтобы в первой было r1, во второй - r2,…,в m -  rm элементов.

Сколькими способами это можно сделать? (r1+…+rm = n).

Ответ: n!/r1! … rm!.

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

8.1.В магазине продаются конфеты двух видов. Сколькими способами можно купить четыре конфеты? А если надо купить 8 конфет 4 видов?

8.2.Каков будет ответ в задаче 2.4, если стулья одинаковые?

8.3.Сколько целых неотрицательных решений имеет уравнение

х1234567 = 5? (Сравните с задачей 8.2).

8.4.Сколько существует различных r – элементных множеств, составленных из предметов n видов?

Ответ: Crn+r-1

9. Разные задачи.

Вы познакомились с основными приемами элементарной комбинаторики. В следующих задачах используются эти приемы.

9.1. Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами равной ширины, если имеется материя 6 цветов? А если один из цветов должен быть красным? А если допускаются полоски одноцветные?

9.2. Сколькими способами можно выбрать три краски из имеющихся шести?

9.3. Сколькими способами можно выбрать из колоды в 36 карт по одной карте каждой масти? А если среди выбранных карт не должно быть ни одной пары карт, отличающихся лишь мастью?

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

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

9.6. Сколько различных слов можно получить, переставляя буквы слова “математика”? А слова “ингредиент”?

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

9.8. Имеется 20 абонентов телефонной сети. Сколькими способами можно одновременно соединить три пары абонентов?

9.9 Сколькими способами могут встать в круг 5 юношей и 5 девушек? А если необходимо, чтобы никакие двое юношей или девушек не стояли рядом?

9.10. Сколько различных ожерелий можно составить из 10 различных бусинок? А если  бусинки двух видов – 2 черных и 8 белых?

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

9.12. У ювелира есть 5 одинаковых изумрудов, 8 одинаковых рубинов и 7 одинаковых сапфиров. Сколькими способами он может выбрать из них три камня для брошки?

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

9.14. Пусть дан n-угольник такой, что никакие три его диагонали не пересекаются в одной точке, не являющейся вершиной. Сколько точек пересечения диагоналей имеется внутри n-угольника? А всего на плоскости?

9.15 Дано m предметов одного сорта и n другого. Найти число выборок, составленных из r предметов одного сорта и S другого.

9.16 Сколькими способами можно выбрать 12 человек из 17, если данные 2 человека не могут быть выбраны вместе? А если данные три человека?

9.17. На полке находятся m+n различных книг, из которых m в черных переплетах, а n – в красных. Сколько существует перестановок книг, при которых книги в черных переплетах занимают первые m мест? Сколько ситуаций, в которых все книги в черных переплетах стоят рядом?

10. Производящие функции.

10.1.Пусть А = {A1,…,An}. Каков смысл коэффициента при zk (kn) многочлена еn(z) = (1+A1z)(1+Anz)?

Ответ: множество сочетаний из n по k.

10.2.(Продолжение). Каков смысл коэффициента при zk многочлена dn(z)= (1+z)n =(1+z) … (1+z)?

Ответ:  число сочетаний . Сравните с задачей 5.7.

Многочлены вида еn(z) называются энумераторами, а dn(z) – денумераторами сочетаний.

10.3. Исходя из задачи 10.2, найдите суммы:

1) Cn0+Cn1+…+Cnn (1+1)n=2n.

2) Cn0-Cn1+…+(-1)n Cnn (1-1)n=0

3) C2n0+C2n2+…+C2n2n   (=((1+1)2n+(1-1)2n)/2)   (1+1)2n=22n, (1-1)2n=0.

4) C2n1+C2n3+…+C2n2n-1 (=((1+1)2n-(1-1)2n)/2).

10.4. Попробуйте найти суммы из 10.3 по определению величин Cnm.

10.5. Получите результат задачи 6.2 из равенства dn(z)=dn-1(z) (1+z).

10.6. Каков смысл коэффициента при zk произведения en(z)=(1+a1z+a2z2+…)…(1+anz+an2z2+…)?

10.7. (Продолжение). Каков смысл коэффициента при zm произведения en(z)=(1+z+z2+…)n?

Вспомните, что при z<1  1+z+z2+…=1/(1-z). Тогда dn(z)=(1z)-n. Разложите dn(z)  вряд Маклорена. Сделайте вывод. Сравните ответ с задачей 8.4.

10.8. Запишите самостоятельно энумераторы и денумераторы для нахождения сочетаний с повторениями, в которых элемент каждого из n видов встречается:

  1.  хотя бы один раз;

четное число раз;

1 вида не менее k1, 2 – не менее k2, … , n – не менее kn раз;

1 вида – не более k1, 2 – не более k2, … , n – не более kn раз;

10.9. (Продолжение 10.2). Каков смысл коэффициентов при  zk/k! В dn(z) ? Ответ: число размещений из n по k, поскольку размещений в k! раз больше, чем сочетаний.

10.10. Записать денумератор для размещений из n с повторениями. Ответ: (1+z+z2/2!+…)n. Преобразуйте и получите коэффициенты в разложении. Сравните с задачей 2.5.

10.11. Запишите денумератор для размещений из трех с повторениями, где каждый элемент встречается не менее 1 раза. Сколько будет размещений такого вида, содержащих 5 элементов?

11. ИПОЛЬЗОВАНИЕ РЕКУРЕНТНЫХ СООТНОШЕНИЙ

Если a0, a1, …, an,… -некоторые числа, то можно построить степенной ряд . Иногда удается идти обратным путем – по свойству ряда как функции от z устанавливать свойства членов последовательности.

11.1. Пусть fnr – число сочетаний с повторениями из n видов по r (см. задачу 8.4):

  1.  проверьте, что fn1=n, fn0=1;

докажите, что fnr=fnr-1+ fn-1r;

пусть , докажите, что An(z)= An-1(z)/(1-z);

получите формулу для An(z), не содержащую Ai(z) при i<n. (Сравните с задачей 10.7).

11.2. (Числа Фибоначчи). Числами Фибоначчи называются члены последовательности, заданные по правилу:

B0=B1=1, Bn=Bn-1+Bn-2 при n>=2.

Пусть

  1.  докажите, что F(z)=1+zF(z)+z2F(z);

найдите F(z);

воспользуйтесь разложением рациональной дроби на простейшие, разложением функции 1/(z-a) в степенной ряд и найдите Bn.

Ответ:

12. ФОРМУЛА ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ

12.1. В группе 25 студентов. 15 занимается лыжами, 12 – коньками, а 8 – и тем и другим. Сколько студентов не занимается ни тем, ни другим.

12.2. (Обобщение). Проверьте, что если A  и B- конечные множества, то . Здесь  -число элементов множества A.

12.3. Из 25 человек 15 занимается футболом, 12 – волейболом и 13 – баскетболом; 12 – футболом и баскетболом, 8 занимается всеми тремя видами спорта. Сколько человек занимается хотя бы одним видом спорта?

12.4. (Обобщение). Проверьте, что если A, B, C – конечные множества, то

12.5. (Обобщение). Как будет выглядеть аналог формул из задач 12.2. 12.4. для n множеств?

Ответ:

.

Указание: Один из путей доказательства – проверить, что каждый элемент  в правой части дает слагаемое 1. Для этого предположите, что , .

12.6. Сколько существует перестановок чисел 1,…, n, в которых :

  1.  число k расположено на  k месте?

числа k1 ,  k2 расположены на своих местах?

Числа k1 , …, km расположены на своих местах?

хотя бы одно из чисел 1,…, n расположено на своем месте?

ни одно из чисел 1 , …, n   не расположено на своем месте (беспорядки)?

12.7. Пусть Dn – число беспорядков среди перестановок чисел 1, …, n (см. задачу 12.6 п.5). Найти . Ответ несколько неожиданный: 1/e.

13. ПОРЯДОК КОМБИНАТОРНЫХ ЗАДАЧ

13.1. Докажите, что (n/z)n/2<n!<nn при n>=2.

Докажите что  возрастает при изменении k от 1 до n+1  и убывает – при изменении k от  n+1 до 2n+1.

13.3. Докажите, что

Эти результаты показывают, что комбинаторные величины очень быстро растут с ростом n.

Для n! известна весьма точная приближенная формула Стирлинга: , причем отношение этих величин имеет предел 1 при n. Поразительно, что здесь участвует число  - отношение длины окружности к диаметру.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

  1.  Виленкин И.Я. Комбинаторика. –М.:Наука, 1969. –328с.

Виленкин И.Я. Популярная комбинаторика. –М.:Наука, 1975.-208с.

Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. –М.:Наука, 1977. –80с.

Кофман А. Введение в прикладную комбинаторику. М.:Наука, 1975. – 480с.

Холл М. Комбинаторика. –М.:Мир, 1970. –424с.


 

А также другие работы, которые могут Вас заинтересовать

34273. Аллельные гены 11.22 KB
  Такие парные гены называют аллельными генами или аллелями. Взаимодействиеполное доминированиецвет глазнеполноеокраска ночной красавицысверхдоминированиеу гетерозигот признак выражен лучше чем у гомозигот по доминанту те кто болеет серповидно клеточной анемиейне страдают от маляриикодоминирование оба аллеля выявляют свое действие одинаковогруппы крови Неаллельныегены содержащиеся в разных локусах. Комплементарность доминантные аллели из разных аллельных пар дополняют друг другагены пигментации волос Эпистазподавление гена...
34278. Аномалия 44 KB
  Пороки развития аномалии развития совокупность отклонений от нормального строения организма возникающих в процессе внутриутробного или реже послеродового развития. Пороки развития возникают под действием разнообразных внутренних наследственность гормональные нарушения биологическая неполноценность половых клеток и др. К наследственным относят пороки возникшие в результате мутаций т. Б зависимости от того на каком уровне произошла мутация на уровне генов или хромосом наследственно обусловленные пороки подразделяют на гениые и...
34279. Взаимное влияние аллельных генов 182.5 KB
  Этот вид взаимодействия генов заключается в том что при наличии двух доминантных аллелей разных генов появляется новый признак то есть для появления нового признака у организма должен быть генотип АВ. Если одна пара генов определяющих окраску будет рецессивной гомозиготой т. не будет синтезироваться нужный белок то даже если вторая пара генов будет нести доминантный аллель цветки окрашены не будут.
34281. Задачей медицинской генетики является выявление и профилактика наследственных заболеваний 60.16 KB
  При изучении генетики чаще всего используются такие методы: Генеалогический метод состоит в изучении родословных на основе менделевских законов наследования и пoмoгeт установить характер наследования признака доминантный или рецессивный. Этим методом выявлены вредные последствия близкородственных браков которые особенно проявляются при гомозиготности по одному и тому же неблагоприятному рецессивному аллелю. Близнецовый метод состоит в изучении различий между однояйцевыми близнецами. С помощью близнецового метода выявлена роль...