Комбинаторика

 

лекция  по  комбинаторике

            . 

            Методическая  и школьная литература:

1. Виленкин Н.Я. и др. Алгебра и математический анализ для 11 класса: Учеб. пособие для учащихся шк. И классов с углубл. изуч. Математики / Н.Я.Виленкин., О.С.Ивашев-Мусатов, С.И.Шварцбурд. – М.: Просвещение, 1993. – 288с.
2. Макарычев Ю.Н. и др. Алгебра. 9 кл.: Учеб. для шк. и кл. с углубл. изуч. математики. – М.: Мнемозина, 2004. – 439с.
3. Макарычев Ю.Н., Миндюк Н.Г. Алгебра: Элементы статистики и теории вероятностей: Учеб. пособие для учащихся 7-9 кл. общеобразоват. учреждений / Под. ред. С.А.Теляковского. – М.: Просвещение, 2003. – 78с.
4. Мордкович А.Г., Семенов П.В. События. Вероятности. Статистическая обработка данных: Доп. параграфы к курсу алгебры 7-9 кл. общеобразоват. учреждений. – М.: Мнемозина, 2004. – 112с.
5. Решение задач по статистике, комбинаторике и теории вероятностей. 7-9 классы / Авт.-сост. В.Н.Студенецкая. – Волгоград: Учитель, 2005. – 429с.
6. Ткачева М.В., Федорова Н.Е. Элементы статистики и вероятность: Учеб. пособие для 7-9 кл. общеобразоват. учреждений. – М.: Просвещение, 2004. – 112с.

Обратите  внимание на то, что  курсив после символа G обозначает мое обращение к Вам!

Успехов в овладении каждым из разделов!

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

                                          Т.С.

Лекция 

тема. Комбинаторика 

     Комбинаторная задача – задача, решение которой предполагает рассмотрение перебора различных вариантов. В частности, одним из видов комбинаторных задач являются задачи на соединения.

      Виды  соединений: сочетания, размещения, перестановки.

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

(«схема  выбора без возвращения»)

      Определение 1. Сочетанием из n элементов по m (иногда читают просто: из n по m) называется m-элементное подмножество некоторого n-элементного множества.

      Вывод:  чтобы назвать какой – либо объект сочетанием из n по m, необходимо проверить одновременное выполнение следующих условий, существенных признаков понятия «сочетание»:  1. Заданы два множества.

                     2. Одно из множеств является подмножеством другого.

                     3. Основное множество  содержит n элементов.

                     4. Подмножество содержит  m элементов.

     Формула 1 (число сочетаний «из эн по эм»):

     Например: Сколькими способами можно составить  букет из 3 цветов, если в вашем распоряжении 5 цветов: мак, роза, тюльпан, лилия, гвоздика?

     Решение (  G обратить внимание на его оформление!)

     Основное  множество: {мак, роза, тюльпан, лилия, гвоздика}  Þ

     Соединение  – букет из трех цветков Þ

     Проверим, важен ли порядок:

     {тюльпан,  лилия, гвоздика} и {лилия, тюльпан,  гвоздика} – один и тот же  букет Þ порядок неважен Þ это подмножество Þ это сочетание «из пяти по три».

      (букетов)

     Ответ: 10 букетов 

      Определение 2. Размещением из n элементов по m (или просто: из n по m) называется последовательность, состоящая из m различных элементов некоторого n-элементного множества.

      Характерные особенности понятия «размещение», существенные признаки понятия «размещение»: 1. Задано некоторое множество из n элементов.

2. Выделена последовательность элементов этого множества.
3. Эта последовательность содержит m элементов.
4. Эти m  элементов различны.

 

Различие  в определениях сочетаний  и размещений.

     Сочетание – это подмножество, содержащее m элементов из n.

     Размещение – это последовательность, содержащая m элементов из n.

     Вопрос: существует ли разница между последовательностью  и подмножеством?

     Ответ: при формировании последовательности, важен порядок следования элементов, а при формировании подмножества порядок не важен. Значит, при формировании сочетания из n-элементного множества, безразличен порядок следования элементов, а при формировании размещения из n-элементного множества, порядок следования элементов важен.

      Формула 2 (число размещений «из эн по эм»):

     Например: Сколько существует двузначных чисел, в которых цифра десятков и  цифра единиц различны и нечетны?

     Решение ( G обратить внимание на его оформление!)

     Основное  множество: {1, 3, 5, 7, 9} – нечетные цифры Þ

     Соединение  – двузначное число Þ

     Проверим, важен ли порядок: – разные двузначные числа Þ порядок важен Þ это последовательность Þ это размещение «из пяти по два».

      (двузначных чисел)

     Ответ: 20 чисел 

     Определение 3. Перестановкой из n элементов называется последовательность, состоящая из всех элементов некоторого n-элементного множества, причем число элементов этой последовательности равно n.

     Характерные особенности понятия «перестановка», существенные признаки понятия:

1. Задано  некоторое множество из n элементов.

2. Составляется  последовательность из всех элементов  этого множества.

3. Эта  последовательность содержит n элементов. 

     Различия  и сходства  в определениях перестановок и размещений.

     Сходства. Перестановки и размещения – это последовательности элементов n-элементного подмножества. В них имеет значение порядок следования элементов последовательности.

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

     Формула 3 (число размещений «из эн по эм»):

     Например: В расписании сессии 3 экзамена (история, геометрия, алгебра). Сколько может быть вариантов расписаний?

     Решение (  G обратить внимание на его оформление!)

     Основное  множество: {история, геометрия, алгебра} Þ

     Соединение  – вариант расписания сессии

     Проверим, важен ли порядок:

     {история,  геометрия, алгебра} и {геометрия, история, алгебра} – варианты расписания сессии для разных групп Þ порядок важен Þ это последовательность Þ это размещение «из трех по три» Þ это перестановка из трех элементов.

      (вариантов)

     Ответ: 6 вариантов

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

которые помогут облегчить  дальнейшие вычисления

2. (правило симметрии)
5. (правило Паскаля)

 

Более «сложные»  задачи на соединения связаны с двумя  правилами 

Правило суммы (или сложения): Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать объект А или объект В можно выбрать (m+n) способами. 

Правило произведения (или умножения): Если некоторый объект А может быть выбран из совокупности объектов m способами, и после такого выбора объект В может быть выбран n способами, то пару объектов А и В в указанном порядке можно выбрать (m× n) способами.

     Например: Сколькими способами можно собрать 3 бандероли с равным количеством  книг, если есть 9 книг различных авторов.

Решение

     Основное  множество: {1 книга, 2 книга, …, 9 книга}

     Соединение – бандероль из трех книг Þ

     Проверим, важен ли порядок:

     {1 книга, 2 книга, 5 книга } и {5 книга, 1 книга, 2 книга } – одна и та  же бандероль Þ порядок неважен Þ это подмножество Þ это сочетание «по три»

     Учтем, что после того, как соберут первую бандероль («объект А»), останется 6 книг (для выбора «объекта В»), после чего останется всего три книги.

      (способов) 

Задания для тренировки

1. Сколькими способами могут разместиться 4 пассажира в 4-хместной каюте?
2. При встрече 16 человек обменялись рукопожатиями. Сколько всего было сделано рукопожатий?
3. Сколькими способами можно разместить 6 человек на одной скамейке?
4. Группа учащихся в 30 человек пожелала обменяться своими фотографиями. Сколько фотографий потребовалось для этого?
5. Учащиеся школы изучают 10 различных предметов. Сколькими способами можно составить расписание уроков на один день, чтобы при этом было 5 различных предметов, и чтобы каждый предмет занимал 1 урок?
6. Анаграммой называется слово (даже не имеющее смысла), составленное из всех букв данного слова, причем каждая буква повторяется столько раз, сколько раз она входит в данное слово. Сколько анаграмм можно сделать из слова «журнал».
7. Сколько бригад по 5 человек в каждой можно составить из 12 человек для отправки на особое задание?
8. Сколькими различными способами можно избрать из 15 человек делегацию в составе 3 человек для переговоров с администрацией для сохранения зарплаты?
9. Сколькими различными способами собрание, состоящее из 40 человек, может выбрать из своей среды председателя, его заместителя и секретаря?
10. Сколько прямых можно провести через 8 точек, из которых никакие 3 не лежат на одной прямой?
11. Сколько различных пятизначных чисел можно написать с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 (без повторений)?
12. Определить число диагоналей 5-тиугольника.
13. Из ящика, где находятся 15 шаров, занумерованных последовательно от 1 до 15, вынимают три шара. Определить число возможных комбинаций номеров при этом.
14. Сколько различных плоскостей можно провести через 10 точек, если никакие три из них не лежат на одной прямой и никакие 4 точки не лежат в одной плоскости? Нет ли лишних данных в этой задаче?
15. Сколькими различными способами можно положить в 2 кармана 7 монет различного достоинства?