67597

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

Лекция

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

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

Русский

2014-09-12

217 KB

6 чел.

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

Литература

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


 

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

79304. Философия и концепция управления персоналом 12.89 KB
  Философия управления персоналом философскопонятийное осмысление сущности управления персоналом его возникновения связи с другими науками и направлениями науки об управлении уяснение лежащих в основе управления персоналом идей и целей. В частности философия управления персоналом рассматривает процесс управления персоналом с логической психологической социологической экономической организационной и этической точек зрения. Сущность философии управления персоналом организации заключается в том что работники имеют возможность...
79305. Принципы и методы управления персоналом 13.77 KB
  Принципы управления персоналом правила основные положения и нормы которым должны следовать руководители и специалисты в процессе управления персоналом. Управление персоналом традиционно осуществляется на основе принципов: научности; демократического централизма; плановости; первого лица; единства распорядительства; отбора подбора и расстановки кадров; сочетания единоначалия и коллегиальности централизации и децентрализации; линейного функционального и целевого управления; контроля исполнения решений и др. Современные зарубежные...
79306. Теория потребления 38.81 KB
  Потребительское поведение и полезность блага. рациональный потребитель стремится максимизировать полезность. Полезность это субъективное понятие которое характеризует степень удовольствия от покупки данного товара. Предельная полезность это добавочная полезность или удовлетворение извлекаемое потребителем из одной дополнительной единицы конкретной продукции.
79307. Теория производства и издержек 72.85 KB
  Теория производства и издержек Производственная функция. Издержки производства. Издержки производства в краткосрочном периоде. Издержки производства в долгосрочном периоде.
79308. Рынок совершенной конкуренции 23.72 KB
  Прибыль фирмы будет максимизироваться при таком объёме производства когда валовой доход превышает валовые издержки на максимальную величину. Оптимальным будет считаться такой объём производства когда валовые издержки будут превышать валовой доход на минимальную величину. Фирме следует закрыться в том случае когда ей не удастся покрыть свои переменные издержки. Если предельные издержки меньше предельного дохода то в таких условиях фирме следует увеличивать производство.
79309. Фирма в условиях чистой монополии и несовершенной конкуренции 12.19 KB
  в данном случае понятия фирмы и отрасли совпадают производится уникальный продукт у которого не существует близких заменителей велики барьеры для вступления в отрасль. Так же как и фирмы в условиях совершенной конкуренции сталкивается с двумя ограничениями: связанные с издержками связанные со спросом рисунок Линия спроса убывает. Однако с другой стороны практика показывает что фирмымонополисты часто осуществляют затраты для сохранения монопольного положения на рынке.
79311. Инвестиции и рынок ценных бумаг 9.91 KB
  капитальные фонды и формирование рыночного спроса на инвестиции дисконтирование доходов от инвестиций формирование и развитие рынка ценных бумаг сущность ценных бумаг и их виды 1. Рынок ценных бумаг это часть рынка ссудных капиталов где формируется спрос и предложение на ценные бумаги. Институты рынка ценных бумаг: банки специальные кредитные учреждения фондовая биржа 2 вида рынка ценных бумаг: Первичный рынок биржевой охватывает лишь новые выпуски ценных бумаг Вторичный фондовый рынок где производится купляпродажа ранее выпущенных...
79312. Введение в экономическую теорию и общественное производство 51.78 KB
  Сущность и элементы общественного производства. Экономика это наука о способах использования ограниченных ресурсов общества для производства товаров и услуг и их распределения среди различных групп людей. Можно выделить три уровня производства: процесс труда отдельного индивидуума производство в рамках предприятия микроуровень производство в рамках общества государства страны макроуровень производство в рамках мира Элементы общественного производства: рабочая сила это совокупность определенных физических и духовных способностей...