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с.


 

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

47421. Особенности методики развития скоростно-силовых способностей у школьников 5-х классов в процессе занятий физическими упражнениями 359 KB
  Большой вклад в теорию игры внесли Е.Ушинский считал что значение игры в развитии и воспитании личности уникально так как игра позволяет каждому ребенку ощутить себя субъектом проявить и развить свою личность. Одна из причин тому – недостаточное внимание к разработке теории игры школьников. Сущность игры заключается в том что в ней важен не результат а сам процесс процесс переживаний связанных с игровыми действиями.
47422. Разработка системы приёмов организации и развития внимания детей 5 – 6 классов 367.5 KB
  Основные свойства внимания. Возрастные особенности внимания школьников. Организация внимания школьника. Наглядность как основной компонент развития внимания на уроках немецкого языка.
47423. Процесс формирования и развития организационной культуры предприятия «СТОМГРУПП» 777 KB
  Предложения по развитию и укреплению культуры организации СТОМГРУПП. Одним из важнейших мотивов для исследования организационной культуры является то что традиционные методы управления организациями построенные на функциональной специализации работников и подразделений разделении труда обособленности отдельных структур организации друг от друга основанные на линейности и равновесности процессов не отвечают сложившимся в настоящем условиям. Таким образом современным организациям требуется новая идеология...
47424. ОСОБЕННОСТИ КОРРЕКЦИОННОЙ РАБОТЫ ПО РАЗВИТИЮ РЕЧИ У ДЕТЕЙ С ОНР 1.32 MB
  Исследование состояния связной речи детей старшего дошкольного возраста с общим речевым недоразвитием. Формирование связной речи у детей Библиография Введение Проблемой нашего исследования является уровень связной речи детей с общим недоразвитием речи.
47425. Кассовые операции 53.88 KB
  Виды услуг предоставляемых в отделении почтовой связи. Учет кассовых операций в отделении почтовой связи. Порядок получения сумм подкреплений денежной наличности в отделении почтовой связи. Порядок высылки сверхлимитных остатков из кассы отделения почтовой связи.
47426. Рестораны национальных кухонь в Астрахани и их использование в туристском бизнесе 946 KB
  Национальная кухня составляет важный элемент культуры региона. Туристы любят пробовать национальные блюда той страны, по которой путешествуют. Например, почти все туристы, впервые посещающие Россию, желают отведать борщ и пельмени.
47427. Специфика и приоритетные направления развития современных российско-грузинских отношений 429 KB
  Проанализировать российско-грузинские отношения в конце XX начале XXI века в трудах современных исследователей и прессе. Выявить специфику становления российско-грузинских взаимосвязей в русле национальной политики. Обозначить территориальные аспекты российско-грузинских взаимоотношений. Изучить вопросы экономического сотрудничества Грузии и России...
47428. ОЦІНКА ПРОЦЕСУ УПРАВЛЯННЯ МІЖНАРОДНОЮ МАРКЕТИНОГОВОЮ ДІЯЛЬНІСТЮ ТОВ «УНІВЕРСЛА ПРОДУКТ» 569 KB
  Для ефективного управління зовнішньоекономічною діяльністю на підприємстві потрібна відповідна умовам його роботи структура управління. На підприємствах, які беруть активну участь у зовнішньоекономічній діяльності, зовнішньоторговельний апарат існує у двох формах: як частина внутрішньовиробничої структури у вигляді зовнішньоекономічного відділу і як відносно самостійний підрозділ у вигляді зовнішньоторговельної фірми
47429. СОДЕРЖАНИЕ ФУНКЦИОНАЛЬНОГО АСПЕКТА УПРАВЛЕНИЯ ПРОЕКТОМ 208.5 KB
  Необходимо отметить что инвестиционная деятельность в современных условиях тесно связана с умением разработать эффективный инвестиционный план или проект а затем обеспечить определенные ими ограничения по ресурсам и реализовать заданный уровень качества продукции проекта. Не проводилось никакого управления на прединвестиционной и эксплуатационной фазе проекта. Практически не осуществлялось эффективного планирования на стадии реализации проекта. Отсюда сущность управления проекта обеспечить корректное выполнение поставленных целей с...