РефератыМатематикаЭлЭлементы комбинаторики

Элементы комбинаторики

Факультативный курс по теме:


Элементы комбинаторики


Автор: Лузина Татьяна Юрьевна


Рецензент: Янкина Лидия Григорьевна


Кунгурское педагогическое училище 2009 год


Введение


В данной разработке факультативного курса предлагается 11 уроков. На которых предлагается решение задач, подготовка сообщений и докладов и их защита; практические, самостоятельные работы; практикумы по решению задач, по составлению задач; контрольная работа.


Данный факультативный курс предназначен для учеников 8 класса, но может и использоваться учениками других классов, т. к. материал излагается с самих азов. Он прост, понятен и в то же время не потерял своей научности.


Оглавление


Предисловие


Урок 1 Введение


Урок 2 Поиск закономерностей


Урок 3 Перебор возможных вариантов


Урок 4 Правило суммы и правило произведения


Урок 5 Самостоятельная работа по темам: «Поиск закономерностей», «Дерево возможных вариантов», «Правило произведения»


Урок 6 Размещения


Урок 7 Тест по темам: «Размещение без повторений», «Размещение с повторениями»


Урок 8 Перестановки


Урок 9 Сочетания


Урок 10 Урок-практикум. Подготовка к контрольной работе


Урок 11 Контрольная работа


Литература


Предисловие


Вы начинаете изучать раздел математики под названием «Комбинаторика».


В данном факультативном курсе вы найдете много интересных и полезных для себя сведений, которые связаны с жизнью.


Любую тему вам поможет отыскать «Оглавление».


Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций можно составить из заданных объектов, называется комбинаторикой.


Комбинаторика возникла в XVIIвеке. Тогда широко были распространены лотереи, игры в карты и кости. И первые комбинаторные задачи касались именно азартных игр, так как возникало много вопросов, сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре.


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


В данном факультативном курсе будут использованы такие виды деятельности, как практические, самостоятельные работы, решение задач, защита докладов и сообщений. Данный курс вам поможет по-другому посмотреть на окружающий мир. Изучив его, вы сможете объективно оценивать некоторые вещи, опираясь на математические подсчеты.


Желаю вам успехов в овладении тайнами удивительного раздела математики – комбинаторики!


Урок 1. Введение


Цели:


· дать понятие науки «Комбинаторика», «Комбинаторные задачи»;


· познакомить учащихся с историей данной науки;


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


Ход урока


1. Сообщение темы и целей


2. Работа по теме


Комбинаторика – ветвь математики, изучающая комбинации и перестановки предметов. Еще комбинаторику можно понимать как перебор возможных вариантов. Комбинаторика возникла в XIIвеке. Долгое время она лежала вне основного русла развития математики.


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


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


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


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


Задачи, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными.
Область математики, в которой изучаются комбинаторные задачи, называется комбинаторикой.
Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях


Раздел комбинаторики, в котором рассматривается лишь вопрос о подсчете числа решений комбинаторной задачи, теорией перечислений.


Комбинаторика как наука стала развиваться в XIIIвеке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма. Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 году. Он также впервые ввел термин «комбинаторика». Значительный вклад в развитие комбинаторики внес Л.Эйлер.


3. Перечень тем докладов


1) Дж. Кардано


2) Н. Тарталье


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


4) Б. Паскаль


5) П. Ферма


6) Треугольник Паскаля


7) Л.Эйлер


8) Г. Галилею


9) Г. Лейбниц


10) Некоторые свойства числа сочетаний


11) Правила решения комбинаторных задач


12) Комбинаторная геометрия


13) Историческая справка о науке «Комбинаторике»


14) Магические квадраты


4. Итог урока


Урок 2. Поиск закономерностей


Цели:


· рассмотреть некоторые виды закономерностей.


Оборудование: мультимедийный проектор, жетоны.


Ход урока


1. Сообщение темы и целей.


2. Домашнее задание.


1. Выявить закономерности и записать еще 4 числа:


1)










562 (26)
652
369 (__) 963

2) ответ: 36 – сумма цифр в числе


3. Разминка


Итак, начнем наш урок с разминки. Сегодня она будет в другой форме – в виде соревнования. Я задаю вопросы, и кто быстрее поднимет руку, тот и будет отвечать. За каждый правильный ответ даются жетоны.


1) Портной имеет кусок сукна в 16 м, от которого он ежедневно отрезает по 2 метра. По истечении скольких дней он отрежет последний кусок? (7 дней)


2) Разделить 5 яблок между пятью лицами так, чтобы каждый получил по яблоку, и одно осталось в корзине? (Один берет корзину вместе с яблоком)


3) Четыре коровы черной масти и три - рыжей масти за пять дней дали такой же надой молока, как 3 коровы черной масти и 5 рыжей за 4 дня. Какие коровы молочнее: черной или рыжей масти? (рыжей)


4) Как представить цифру 4 тремя пятерками? (4=5-5:5)


5) Шесть ног, а бежит не быстрее, чем на четырех. (всадник на коне)


6) Какие часы показывают верное время только два раза в сутки? (которые остановились)


7) В известной сказке «Поди туда – не знаю куда, принеси то – не знаю что» царь послал стрелка Андрея за «тридевять земель». Тридевять - это сколько? (27)


8) Шел Кондрат в Ленинград, а навстречу 12 ребят.


У каждого по 3 лукошка, в каждом лукошке – кошка.


У каждой кошки – 12 котят. У каждого котенка


В зубах по 4 мышонка. И задумался старый Кондрат:


«Сколько мышат и котят ребята несут в Ленинград?»


Как бы вы ответили на этот вопрос? (Один Кондрат шел в Ленинград)


9) В мешке лежат шарики белого и черного цвета. Сколько нужно взять шариков, чтобы 2 было одинакового цвета? (3)


10) Поехал мужик зимой на ярмарку, а базар далеко. Вот едет он лесом-полем, лесом-полем, лесом-полем. Встречает Бабу-Ягу и спрашивает: «Куда ехать?» Она ему показывает направо. И вот он снова едет лесом-полем, лесом-полем, лесом-полем, встречает Лешего. Спрашивает: «Как доехать до базара?» Он показывает налево. Вот он снова едет лесом-полем, лесом-полем, лесом-полем и выезжает к реке. А за рекой – базар. Как ему перебраться на тот берег, учитывая, что лодки нет и надо переправить весь груз? (Дело было зимой). Молодцы!


4. Работа по теме.


4.1. Объяснение материала.


Кто знает, что такое закономерность? Это закон, правило, по которому записаны числа, расположены фигуры.


4.2. Решение примеров.


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


1) Вставить недостающую картинку.


Ну, что, поняли, как выявляют закономерности в расположении фигур?


Теперь давайте попробуем выявлять закономерности в числовых рядах. Тот, кто ответит первым, получит жетон.


2) Вставить пропущенные числа:


1) 24, 21, 19, 18, 15, 13, _ , _ , 7,6 (12, 9);


2) 1, 4, 9, 16, _ , _ , 49, 64, 81, 100 (25, 36);


3) 16, 17, 15, 18, 14, 19, _ , _ (13, 20);


4) 1, 3, 6, 8, 16, 18, _ , _ , 76, 78 (36, 38);


5) 7 26 19; 5 21 16; 9 _ 4 (13);


6) 2 4 8 10 20 22 _ _ 92 94 (44, 48);


7) 24 22 19 15 _ _ (10, 4).


3) Продолжить ряд:


a. 15 16 18 21 25 _ (30);


b. 2 5 8 11 _ (14);


c. 6 9 12 15 18 _ (21);


d. 16 12 15 11 14 10 _ _ (13, 9);


e. 3 7 11 15 18 _ (22).


4) Вставить пропущенное число


a. 2 5 9 (2+4):2=3


4 7 5 (5+7):2=6


3 6 ? (9+5):2=7


b. 7 9 5 11 7+9-5=11


4 15 12 7 4+15-12=7


13 8 11 ? 13+8-11=10



(3*5*8)/10=12


c. 148 (220) 368 368-148=220


243 (___) 397 397-243=154


d. 12 (56) 16 (12+16)∙2=56


17 (__) 21 (21+17) ∙2=76


5. Итог урока.


Урок 3. Перебор возможных вариантов. Дерево возможных вариантов


Цели:


- дать понятия: комбинаторика, комбинаторные задачи;


- изучить способы решения комбинаторных задач: перебор возможных вариантов, дерево возможных вариантов;


Оборудование: мультимедийный проектор, задачи на карточках.


Ход урока


1. Сообщение темы и целей


2. Подготовительная работа


Давайте с вами решим задания, которые подведут нас к теме.


2.1. Решение ребусов



Выявление закономерности



Решение задач



Изучение новой темы. Разбор задач


Давайте рассмотрим такую задачу: сколько двузначных чисел можно составить, используя цифры 1, 4 и 7?


Решение: для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7:


11, 14, 17, 41, 44, 47, 71, 74, 77.


Этот метод называется перебором вариантов. Таким образом, их трех данных цифр можно составить всего 9 различных двузначных чисел.


Эту задачу можно решить и другим способом. Его название – дерево возможных вариантов. Для этой задачи построена специальная схема.


Ставим звездочку. Она будет обозначать количество возможных вариантов.


Далее отводим от звездочки 3 отрезка. А почему? Как вы думаете? Так как в условии задачи даны 3 цифры – 1, 4, 7.


Ставим эти цифры на концах отрезков. Они будут обозначать число десятков в данном числе.


Далее от каждой цифры проводим по 3 отрезка. Почему? От цифры 1 три отрезка, от цифры 4 три отрезка и от цифры 7 также проводим три отрезка.


На концах этих отрезков записываем также цифры 1, 4, 7. Они будут обозначать число единиц.


рассмотрим, какие числа получились: 11, 14, 17, 41, 44, 47, 71, 74, 77. То есть всего получилось 9 чисел.


Эта схема действительно похожа на дерево, правда «вверх ногами» и без ствола.


Решение задач.


Итак, давайте решим несколько задач.


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


Ответ: всего 8 чисел.


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


Ответ: всего можно составить 6 вариантов расписания.


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


Ответ: всего 4 числа.


А теперь давайте сделаем так: мальчики решают задачу: Данила, Андрей и Коля собрались потренироваться в бросании мяча в баскетбольную корзину. У них только один мяч, и им надо договориться, кто за кем будет бросать мяч в корзину. Сколькими способами они могут занять очередь?


Девочки решают задачу: в костюмерной танцевального кружка имеются зелёные и жёлтые кофты, а также синие, красные и чёрные юбки. Сколько можно из них составить различных костюмов?


Домашнее задание


Откройте дневники и запишите домашнее задание. Решить задачи на карточках.


1. Сколько всего четырехзначных чисел можно составить из цифр 0 и 3?


2. В палатке имеется 3 сорта мороженого: рожок, брикет и эскимо? Наташа и Данил решили купить по одной порции каждого сорта мороженого. Сколько существует вариантов такой покупки?


Итог урока


Урок 4. Правило суммы и правило произведения


Цели:


· познакомить учащихся с правилами произведения и суммы в комбинаторике;


· закрепить правила с помощью решения задач;


Оборудование:


Ход урока


1. Сообщение темы и целей


2. Домашнее задание на карточках


1) Сколькими способами можно выбрать гласную и согласную буквы из слова «ЗДАНИЕ»? (в слове «здание» 3 согласных и 3 гласных буквы. По правилу произведения получаем 3*3=9 способами)


2) Сколькими способами можно указать на шахматной доске два квадрата – белый и черный? Решите эту же задачу, если нет ограничений на цвет квадратов; если надо выбрать два белых квадрата. (На шахматной доске 64 клетки: 32 белых квадрата, 32 черных квадрата. По правилу произведения получаем число выбора двух квадратов: одного черного и одного белого: 32*32=1024.


Если нет ограничений на цвет, то первый квадрат можно выбрать 64 способами, а второй – 63 способами (один квадрат уже выбран), следовательно, 64*63=4032


Если надо выбрать два белых квадрата, то первый квадрат можно выбрать 32 способами, а второй квадрат – 31 способом, поэтому, 32*31=992.


3. Повторение


Решить задачу: сколько трехзначных чисел можно составить из цифр 0, 5, 8?


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


4. Работа по новой теме


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


Например: на тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?


По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5+4=9 способами.


Задача 1
: сколько трехзначных чисел можно составить из цифр 1,3,5,7, используя в записи числа каждую из них не более одного раза?


Решение: составим дерево возможных вариантов.


Эту задачу можно решить по-другому и намного быстрее, не строя дерева возможных вариантов. Рассуждать будем так. Первую цифру трехзначного числа можно выбрать четырьмя способами. Так как после выбора первой цифры останутся три, то вторую цифру можно выбрать из оставшихся цифр уже тремя способами. Наконец, третью цифру можно выбрать (из оставшихся двух) двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 4∙3∙2, т.е. 24.


Сформулируем правило умножения: если объект А можно выбрать
m
способами и если после каждого такого выбора объект В можно выбрать п способами, то выбор пары (А, В) в указанном порядке можно осуществить
m
∙п способами.


Например, решите задачу с помощью правила умножения: сколько пятизначных чисел можно составить из цифр 5, 9, 0, 6?


По правилу умножения получаем: 4∙4∙4∙4=256 чисел.


Правило умножения можно также проиллюстрировать.


Задача 2
: из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут?


Решение: Пусть из города А в В туристы могут выбрать двумя способами. Далее в каждом случае они могут проехать из В в С тремя способами. Значит, имеется 2∙3 вариантов маршрута из А в С. Так как из города С на пристань можно попасть двумя способами, то всего существует 2∙3∙2=12 способов выбора туристами маршрута из города А к пристани.


Например: из пункта А в пункт В можно попасть десятью путями, а из пункта В в пункт С – девятью путями. Сколько имеется маршрутов из пункта А в пункт С через пункт В?


Решение: 10∙9=90 маршрутов


Задача 3
: В кафе имеются три первых блюда, пять вторых блюд и два третьих. Сколькими способами посетитель кафе может выбрать обед, состоящий из первого, второго и третьего блюд?


Решение: первое блюдо можно выбрать тремя способами, второе – пятью и третье – двумя, отсюда, по правилу умножения получаем 3∙5∙2=30 способами.


5. Первичное закрепление знаний


1. Сколько различных пятизначных чисел, делящихся на 10 можно составить из цифр 0, 1, 2, 3, 4? Каждую цифру можно использовать в записи только один раз.


2. Сколько пятизначных чисел, делящихся на три, можно составить из цифр 3, 4, 6, 7, 9 если каждое число не содержит одинаковых цифр?


3. Сколько шестизначных чисел можно составить из цифр 4, 5, 6, 7, 8, 9 так, чтобы каждое из них начиналось с комбинации «567»?


4. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6 так, чтобы каждое из них начиналось с комбинации «45»?


5. Сколько чётных положительных пятизначных чисел можно получить из цифр 5, 9, 6, 0, так, чтобы цифры в числе не повторялись?


6. Сколько чётных положительных пятизначных чисел можно получить из цифр 1, 2, 3, 4?


6. Итог урока


Урок 5. Самостоятельная работа по темам: «Поиск закономерностей», «Дерево возможных вариантов», «Правило произведения»


Цели:


· проверить знания по темам: «Поиск закономерностей», «Перебор возможных вариантов. Дерево возможных вариантов», «Правило суммы и правило произведения».


Оборудование: карточки с самостоятельной работой


Ход урока


1. Сообщение темы и целей


2. Самостоятельная работа


Самостоятельная работа


1. Сколько чисел, меньших ста, можно составить из цифр 0, 1, 2?


2. У рояля 88 клавиш. Сколькими способами можно извлечь последовательно 4 звука?


3. Сколько различных танцевальных пар (юноша, девушка) можно составить из пяти юношей и восьми девушек?


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










256 (23)
19
62 (__) 781

5. Выявите закономерность и запишите число:


6. На тарелке лежат 10 яблок и 6 апельсинов. Сколькими способами можно выбрать один плод?


7. Из города А в город В ведут три дороги, а из В в С – две дороги. Сколькими способами можно пройти из А в С через В? Покажите чертеж.


8. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если: а) цифры не повторяются? б) цифры могут повторяться?


Ответы и решения


1. 0, 1, 2, 10, 11, 12, 20, 21, 22. Всего 9 чисел


2. 88∙88∙88∙88=59 969 536 способами


3. 5∙8=40 пар


4. 3∙3∙3=27


Самое большое число: 777


Самое маленькое число: 333


777 – 333 = 444 – разность


5. 24


6. 10+6=16 способами


7. 3∙2=6 способами


8. а) 60 чисел


б) 243 числа


3. Итог урока


Урок 6. Размещения


Цели:


· сформулировать определение размещений с повторениями, размещений без повторений


· закрепить на решении задач число размещений с повторениями, без повторений;


· рассмотреть понятие «кортеж», «факториал».


Оборудование: аншлаги с формулами


Ход урока


1. Сообщение темы и целей


2. Домашнее задание на карточках


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


2) Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневый переплеты. Сколькими способами он может это сделать? ()


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


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


3. Повторение


Решить задачу: сколькими способами можно обозначить вершины треугольника, используя буквы А,В,С,D,Eи F?(60)


4. Работа по теме
.


- Вспомните, что такое кортеж? Кортеж
– это множество, в котором порядок элементов строго определен.


- Мы также часто можем встретить задачи, в которых нужно сосчитать число размещений с повторениями


4.1. Понятие «размещений с повторениями»


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


Кортежи длины k
,
составленные из элементов п
-множества, называют размещениями с повторениями
из п
элементов по k
.


Число размещений с повторениями находится по формуле:


Вычислите: ;


Решение: = 53
=125; =35
=243.


Понятие «факториал»


Произведение всех чисел от 1 до nназывается факториалом
и обозначается n!. В комбинаторике 0!=1 и 1!=!


Задача. Вычислите: 4!; 6!.


4!=4*3*2*1=24


6!=6*5*4*3*2*1=720


- Запишем в тетрадь таблицу


























n
2
3
4
5
6
7
8
9
10
11
n! 2 6 24 120 720 5040 40320 362880 3628800 39916800

Правило суммы и произведения – это общие правила решения комбинаторных задач. Кроме них в комбинаторике пользуются формулами для подсчета числа отдельных видов комбинаций, которые встречаются наиболее часто.


Понятие «размещений без повторений»


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


Кортежи длины k, составленные из элементов п
-множества, так что все элементы каждого кортежа должны быть различными, называют размещениями без повторений
из п
элементов по k
, а их число обозначают .


При этом размещения отличаются друг от друга как самими элементами, так и их порядком.


Число размещений без повторений находится по формуле:


– Итак, в примере 1 нам нужно было составить двузначные числа из известных 3 цифр. По формуле получаем способов


Задача. Сколько трехзначных чисел можно записать, используя цифры 1,3,6,7,9, если каждая их них может быть использована в записи только один раз? Постройте дерево возможных вариантов.


Решение: по формуле получаем: способов


– Как вы думаете, как удобнее решать эти задачи: деревом возможных вариантов или по формуле?


5.Закрепление


Задача 1.
Для запирания автоматической камеры применяется секретный замок, который открывается лишь тогда, когда набрано «тайное слово». Это слово набирают с помощью пяти дисков, на каждом из которых изображено 12 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова и подбирающего его наудачу?


Решение.
Из условия задачи видно, что порядок выбираемых букв очень важен. Поэтому мы имеем дело с кортежем длиной 5 (пять дисков). Каждый элемент кортежа может быть выбран 12-ю способами (букв на каждом диске 12). Поэтому число ко

мбинаций 125
=248 831.


Задача 2.
Сколько различных четырехзначных чисел можно составить из цифр 2, 6, 7, 8 и 9, если каждая цифра может входить в комбинацию несколько раз?


Решение. Порядок цифр важен, т.к. 2678 или 6278 – это разные числа. Поэтому имеем дело с кортежем длины 4 (четырехзначное число), каждый элемент которого можно выбрать пятью способами (цифр дано пять). Следовательно, число различных комбинаций равно 45
=1024.


Задача 3.
На референдуме предложены четыре вопроса, на которые надо ответить «да» или «нет». Сколько есть возможностей заполнения бюллетеня (на все вопросы надо дать ответ)?


Решение. Получаем кортеж длины 4 (столько вопросов в бюллетене), каждый элемент может быть выбран двумя способами («да» или «нет»). Поэтому число различных возможностей равно 24
=16


Задача 4.
Неудовлетворенные решением Париса Гера, Афина и Афродита обратились к трем мудрецам с просьбой назвать прекраснейшую из них. Каждый из мудрецов высказал свое мнение. Сколько могло возникнуть вариантов ответа на поставленный вопрос у этой тройки? (63
=216)


Задача 5.
У Лены есть восемь красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если собирается каждую букву раскрашивать одним цветом? (88
=16777216)


Задача 6
. Сколькими различными способами можно распределить между шестью лицами две различные путевки в санаторий?


Решение.


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


Решение: способами


Задача 8.
В классе изучаются 7 предметов. В среду 4 урока, причем все разные. Сколькими способами можно составить расписание на среду?


Решение: способов


Задача 9
. В чемпионате по футболу участвуют десять команд. Сколько существует различных возможностей занять командам первые три места?


Решение:


Задача 10
. Из десяти различных книг выбирают четыре для посылки. Сколькими способами это можно сделать?


Решение.


Задача 11
. Для запирания сейфа на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова? (125
=248 832 удачных попыток, следовательно, неудачных 248 831)


6. Итог урока


Что нового узнали на уроке?


По какой формуле находится число размещений без повторений, с повторениями?


Урок 7. Тест по темам: «Размещение без повторений», «Размещение с повторениями»


Цели:


· Проверить знания по темам: «Размещение без повторений», «Размещение с повторениями» с помощью теста.


Оборудование: карточки с тестом


Ход урока


1. Сообщение темы и целей


2. Тест


1. Из 30 студентов класса надо выбрать хозяйку класса, старосту и физорга. Сколькими способами это можно сделать?


А) 24360 б) 2730 в) 6720


2. В конкурсе песен «Галерея звезд» участвуют 15 человек. Сколькими способами могут распределиться между ними места?


А) 24360 б) 2730 в) 6720


3. Сколько трехзначных чисел можно составить из цифр 5, 6, 8, 7, 1?


А) 243 б) 2730 в) 6720


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


А) 248 832 б) 248 831 в) 248 833


5. Сколько четырехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6?


А) 24360 б) 4 096 в) 6720


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


А) 24360 б) 2730 в) 6720


7. Сколькими способами из колоды, содержащей 36 карт, можно выбрать по одной карте каждой масти?


А) 24360 б) 2730 в) 1 413 720


8. Сколько можно составить трехзначных чисел из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9? Рассмотрите два случая: а) цифры, входящие в одно и тоже число различны; б) среди входящих в одно и тоже число, могут быть одинаковые.


А. а)60 480 б)19 683 в) 672


Б. а)19 683 б) 60 480 в) 6720


Ответы и решения


1. способами


2. способами


3. чисел


4. 125
=248 832 – удачных попыток, тогда неудачных 248 831.


5. 46
=4 096 чисел


6. спсобами


7. способами


8. а) чисел


9. б) 39=19 683 чисел


3. Итог урока


Урок 8: Перестановки


Цели:


· познакомить учащихся с перестановками без повторений, перестановками с повторениями;


· закрепить новые формулы с помощью решения задач.


Оборудование: аншлаги с формулами


Ход урока


1. Сообщение темы и целей


2. Домашнее задание:


1) Сколькими способами можно разместить 12 человек за столом, на который поставлено 12 приборов?


2) Сколькими способами можно установить дежурство по одному человеку в день среди семи учащихся группы в течение семи дней?


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


4) Сколькими способами можно посадить за круглый стол пять мужчин и пять женщин так, чтобы никакие два лица одного пола не сидели рядом?


4. Работа по теме


4.1. Повторение


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


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


- Дайте определение размещений без повторений


- Что такое факториал?


4.2. Понятие «перестановки без повторений»


Два размещения без повторений из nэлементов по n, состоящие из одних и тех же элементов, расположенных в различном порядке называются перестановками без повторений из
n
элементов.
Их число обозначают Рn
.


- Выведем формулу.



Следовательно, число перестановок без повторений находится по формуле: Рп
=
n
!


Вычислите: Р3
; Р5


Р3
=3!=6; Р5
=5!=120


4.3. Понятие «перестановки с повторениями»


Пусть дан кортеж длинны п,
составленный из элементов множества Х=
{х1
, …, х
k
}.
Причем буква х1
входит в этот кортеж п1
раз, буква х
k
= п
k
раз. Тогда п=п1
+ … +п
k
.
Если переставлять в этом кортеже буквы, то будут получаться новые кортежи, имеющие тот же состав. Эти кортежи называются перестановками с повторениями из букв х1
,… , х
k
, имеющими состав (п1
, … , п
k
).


Число таких перестановок обозначается Р(п1
, … , п
k
)
и находится по формуле:



Упражнение. Вычислите: Р
(2, 5, 3); Р
(1, 2, 3, 4).


Решение. Р
(2, 5, 3); п
=2+5+3=10, п1
=2, п2
=5, п3
=3




5. Закрепление


Задача 1.
Найдите число способов расстановки 8 ладьей на шахматной доске, при которых они не бьют друг друга.


Решение. Каждый искомый способ задается перестановкой 8 чисел1,2, … 8. Эти числа указывают номера горизонталей занятых полей на первой, второй, …, восьмых вертикалей. Значит, таких перестановок 8!. Таким образом, ладьи можно расставить 8!=40 320 способами.


Задача 2.
Сколькими способами можно представлять друг с другом цифры 1, 2, 3, 4?


Решение.
Р4
=4!=24.


Задача 3.
За столом пять мест. Сколькими способами можно расставить пятерых гостей?


Решение.
Р5
=5!=120


Задача 4.
У Лены есть 8 разных красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если каждая буква может быть раскрашена одним цветом и все 8 букв должны быть разные по цвету.


Решение.
Присвоим каждой краске номер от 1 до 8. Тогда каждый искомый способ задается перестановкой 8 чисел 1,2, …, 8. Значит, таких перестановок 8!. Поэтому она может написать «Новый Год» 8!=40 320 способами.


Задача 5
. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5?


Решение. 5!=120


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


Решение. Это слово имеет состав: м – 2, а – 3, т – 2, е – 1, и – 1, к – 1, то есть (2, 3, 2, 1, 1, 1), поэтому получим Р(2,3,2,1,1,1)=


Задача 7
. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней она дает сыну по 1 фрукту. Сколькими способами это может быть сделано.


Решение. Р(2,3)=


Задача 8
. Сколькими способами можно положить 28 различных открыток в 4 одинаковых конверта так, чтобы в каждом конверте было по 7 открыток?


Решение. Пометим конверты цифрами 1,2,3,4, тогда число различных раскладок равно Р(7,7,7,7)= . Вычислять это значение не будем, так как оно очень большое.


Сотрем пометки. Теперь конверты можно произвольно переставлять друг с другом, не меняя результата расклада (теперь они не отличаются друг от друга). Так как число различных перестановок четырех конвертов равно Р4
=4!,
то число различных раскладов уменьшается в Р4
=4!
и поэтому оно равно .


Задача 9
. Сколькими способами можно усадить за стол трех мальчиков и трех девочек так, чтобы никакие две девочки не сидели рядом?


Решение. 3!∙3!=36 способами


6. Итог урока


- Что такое перестановки без повторений?


- По какой формуле находится число перестановок без повторений?


Урок 9. Сочетания


Цели:


· познакомить учащихся с сочетаниями без повторений и с повторениями;


· закрепить новые формулы с помощью решения задач.


Оборудование:
аншлаги с формулами


Ход урока


1. Сообщение темы и целей


2. Домашнее задание на карточках


1) Из 20 учащихся кружка математики четверых необходимо отправить на олимпиаду. Сколькими способами можно составить команду?


Решение:


3) В вазе стоят 10 белых и 5 красных роз. Сколькими способами можно выбрать из вазы букет, состоящий из двух красных и одной белой розы?


Решение: · = = 100.


3) Сколько существует различных треугольников, длины сторон которых принимают значения 5, 6, 7, 8, 9? Сколько из них равносторонних, равнобедренных и разносторонних?


4. Повторение


1) Назовите формулу размещений без повторений, размещений с повторениями, перестановок без повторений и перестановок с повторениями;


2) Назовите правила произведения и суммы.


5. Работа по новой теме


5.1. Понятие «сочетаний без повторений»


Задача: рассмотрим все возможные способы составления букетов, в которых по-разному сочетаются три розы из данных пяти роз разного цвета, например: белая, красная, черная, желтая и чайная.


Введем определение:


Сочетаниями без повторений
из n
элементов по т
элементов называются соединения, каждое из которых состоит из m
элементов, взятых из данных n
элементов.


Число сочетаний из п
элементов по m
обозначают и читают «С
из n
по m
».


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


Число сочетаний без повторений равно:


Понятие «сочетаний с повторениями»


- Число сочетаний
с повторениями из nэлементов по mвыражается через число сочетаний без повторений.


- Назовите формулу числа сочетаний без повторений.


Найдем число сочетаний с повторениями из четырех элементов А, Б, В, Г по три элемента:



























ААА
АБВ
БББ
ГГГ
ААБ
АБГ
ББВ
ВВВ
ААВ
АВВ
ББГ
ВВГ
ААГ
АВГ
БВВ
ВГГ
АББ
АБГ
БВГ
ГГГ

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


Формула числа сочетаний из mэлементов по nэлементов с повторениями имеет вид:



Решим предыдущую задачу с помощью этой формулы.



Сочетание с повторениями из mэлементов по nэлементов может содержать любой элемент сколько угодно раз от 1 до nвключительно, либо совсем не содержать его. Во всех случаях два соединения не считаются различными сочетаниями, если они отличаются друг от друга только порядком расположения элементов.


6. Первичное закрепление


Давайте сначала выясним, чем отличаются размещения от сочетаний? В сочетаниях порядок элементов не важен, а размещениях – важен!


Задача 1
. Из 15 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?


Решение: каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идет о сочетаниях из 15 элементов по 3. Следовательно, по формуле получаем


Задача 2.
В магазине «Филателия» продается 8 различных марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них 3 набора?


Решение:


Задача 3
. На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если :


а) словарь нужен ему обязательно;


б) словарь ему не нужен?


Решение:


а)


б)


Задача 4
. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется выделить четырех мальчиков и трех девочек. Сколькими способами это можно сделать?


Решение:


Задача 5
. На тренировках занимаются 10 баскетболистов. Сколько различных стартовых пятерок может образовать тренер?


Решение.


Задача 6
. Сколько наборов из семи пирожных можно составить, если в продаже имеется четыре сорта пирожных?


Решение. наборов


Задача 7
. Сколько существует различных треугольников, длины сторон которых принимают значения: 8, 10, 12 и 14 см? Сколько среди них равносторонних, равнобедренных, разносторонних?


Решение: число различных треугольников равно числу сочетаний с повторениями из четырех элементов по три: .


Из них количество разносторонних треугольников равно числу сочетаний без повторений их четырех элементов по три, т.е.. Количество равносторонних треугольников – 4, а равнобедренных треугольников: 20 – 4 – 4=12.


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


Решение.


Задача 9
. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток? 8 открыток? 8 различных открыток?


Решение. 293 930 способами.




6. Итог урока


- Что нового вы сегодня узнали на уроке?


- Чем отличаются сочетания от размещений? (сочетания – порядок не важен, размещения – порядок важен!)


Урок 10. Урок-практикум. Подготовка к контрольной работе


Цели:


· подготовить учащихся к контрольной работе с помощью решения задач и повторения некоторых теоретических вопросов;


Оборудование: карточки с задачами.


Ход урока


1. Сообщение темы и целей


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


2. Домашнее задание


Подготовиться к контрольной работе


3. Практикум


Теоретические вопросы


Заполнить пропуски:


1. Если некоторый объект А можно выбрать mспособами, а другой объект В можно выбрать nспособами, то выбор «либо А, либо В» можно осуществить … способами. (m+n)


2. Кортежи длины k
, составленные из элементов п
-множества, называют размещениями … из п
элементов по k
. (с повторениями)


3. Два … из п
элементов по т
отличаются друг от друга хотя бы одним элементом. (сочетания)


Решение задач


Решить задачи:


1. «Вороне где-то Бог послал кусочек сыра», колбасы, хлеба и шоколада. «На ель Ворона взгромоздясь, позавтракать совсем уж было собралась, да призадумалась»: если есть кусочки по очереди, то из скольких вариантов придется выбирать?


2. Сколькими способами можно из 25 учащихся выбрать 5 для участия в школьном марафоне?


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


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


5. Из 12 солдат нужно в разведку послать 5. Сколькими способами это можно сделать?


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


7. Назовем симпатичными числа, в записи которых используют только нечетные числа. Сколько существует четырехзначных симпатичных чисел?


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


9. «Проказница Мартышка, Осел, Козел и косолапый Мишка затеяли сыграть квартет». Сколькими способами они могут распределить четыре имеющихся у них инструмента?


10. «Проказница Мартышка, Осел, Козел и косолапый Мишка затеяли сыграть квартет». На складе 12 музыкальных инструментов. Мишке поручили принести со склада 8 любых инструментов. Сколько вариантов выбора есть у мишки?


11. Гера, Афина и Афродита попросили Париса не только назвать самую красивую из них, но и указать, кто «на втором и третьем местах». Сколько есть вариантов ответа?


12. Из 15 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?


13. В магазине «Филателия» продается 8 различных наборов марок, посвященных «Дню Победы». Сколькими способами можно сформировать из них 3 набора?


14. Сколько существует способов составить расписание уроков на один день из 6 предметов?


15. Алфавит племени тумба-юмба состоит из букв А, У, С. Словом является любая последовательность из 4 букв. Сколько слов в языке этого племени?


16. Сколькими способами можно выложить в ряд красный, зеленый, черный, синий кубики?


17. Из колоды в 36 карт вынимают 5 карт. Найдите число всех возможных вариантов выбора.


18. В классе 27 учеников, из которых нужно выбрать троих: первый ученик должен решить задачу, второй – сходить за мелом, третий – пойти дежурить в столовую. Сколькими способами это можно сделать?


Ответы и решения к задачам


1. Р
n
=4!=24


2.


3.


4.


5.


6.


7. нечетные цифры: 1, 3, 5, 7, 9



8.


9. Р
n
=n!=
4!=24


10.


11. 6 способов


12.


13.


14. Рn
=6!=720


15.


16. Pn
=5!=120


17.


18.


Урок 11: Контрольная работа по теме «Комбинаторные задачи»


Цели:


· Проверить знания, умения, навыки по всему курсу с помощью контрольной работы с разноуровневыми заданиями;


Оборудование: карточки с заданиями.


Ход урока


1. Сообщение темы и целей


2. Контрольная работа по вариантам


I
вариант


Заполнить пропуски:


1. Задачи, в которых идет речь о тех или иных комбинациях объектов, называются (комбинаторными).


2. Если объект А можно выбрать m
способами и если после каждого такого выбора объект В можно выбрать п
способами, то выбор пары (А, В) в указанном порядке можно осуществить способами. (
m
∙п)


3. Произведение всех чисел от 1 до nназывается (факториалом)


4. Число размещений с повторениями находится по формуле: ()


5. Сочетаниями … из n
элементов по т
элементов называются соединения, каждое из которых состоит из m
элементов, взятых из данных n
элементов. (без повторений)


6. Формула числа сочетаний из mэлементов по nэлементов с повторениями имеет вид: … ()


Решить задачи:


1. Сколько всевозможных двузначных чисел можно записать, используя цифры 7, 4, 5?


2. Сколькими способами можно из 6 человек составить комиссию, состоящую из двух человек?


3. В соревновании участвуют 10 человек. Сколькими способами могут распределиться между ними места?


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


5. Сколько различных словарей необходимо переводчику, чтобы он мог переводить с любого из 5 языков – русского, английского, немецкого, французского, испанского – на любой другой из этих языков?


6. Пять человек обменялись друг с другом фотографиями. Сколько всего фотографий было?


7. На плоскости отмечены 6 точек. Каждые две точки соединили отрезком. Сколько получилось отрезков?


II
вариант


Заполнить пропуски
:


1. Задачи, в которых идет речь о тех или иных комбинациях объектов, называются (комбинаторными).


2. Если объект А можно выбрать m
способами и если после каждого такого выбора объект В можно выбрать п
способами, то выбор пары (А, В) в указанном порядке можно осуществить способами. (
m
∙п)


3. Произведение всех чисел от 1 до nназывается (факториалом)


4. Число размещений с повторениями находится по формуле: ()


5. Сочетаниями … из n
элементов по т
элементов называются соединения, каждое из которых состоит из m
элементов, взятых из данных n
элементов. (без повторений)


6. Формула числа сочетаний из mэлементов по nэлементов с повторениями имеет вид: ()


Решить задачи:


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


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


3. Пять человек пожали друг другу руки. Сколько было рукопожатий?


4. За свои рисунки ученик получил две положительные оценки. Какими они могут быть? Сколько вариантов?


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


6. В понедельник в пятом классе 5 уроков. Сколькими способами можно составить расписание на понедельник?


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


Ответы и решения








I
вариант
II
вариант

1.


2.


3.


4. Pn
=4!=24


5. Pn
=5!=120


6. Pn
=5!=120


7.


1.


2. Pn
=5!=120


3.


4. положительные оценки: 4, 5.


22
=4


5. Рn
=3!=6


6. Pn
=5!=120


7.



Литература


1. Гнеденко Б. В., Журбенко, И. Г. Теория вероятностей и комбинаторика //Математика в школе. – 2007. - №6. – с. 67-70.


2. Гусев В. А. Внеклассная работа по математике в 5-8 классах. /Под. ред. С. И. Шварцбурга. - М.: Просвещение, 1977. – 288с.


3. Дихтярь М., Эргле Е. Исторические комбинаторные задачи и комбинаторные модели //Математика. – 2007. - №14. – с. 23-24.


4. Математика: Учебник для 5 кл. общеобразоват. учреждений / Г. В. Дорофеев, С. Б. Суворова, И. Ф. Шарыгин и др.; под ред. Г. В. Дорофеева, И. Ф. Шарыгина. – 8-е изд. - М.: Просвещение, 2006. – 302с.


5. Нурк Э. Р., Тельгман А. Э. Математика: Учеб. для 5 кл. сред. шк. – 4-е изд., дораб. – М.: Просвещение, 1994. – 304с.


6. Овсянникова Л.В. Факультативный курс по математике //Начальная школа. – 2005. - №9. – с. 29-33.


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


8. Перельман Я. И. Занимательные задачи и опыты. - Д.: ВАП, 1994. – 527с.


9. Семеновых А. Комбинаторика //Математика. – 2004. - №15. – с. 28-32.


10. Семеновых А. Комбинаторика //Математика. – 2004. - №16. – с. 19-22.


11. Семеновых А. Комбинаторика //Математика. – 2004. - №17. – с. 22-27


12. Стойлова Л. П. Математика: Учебник для студентов отделений и факультетов начальных классов средних и высших педагогических учебных заведений. - М.: Издательский центр «Академия», 1997. – 464с.


13. Цыганов Ш. Комбинаторика от А до Я //Математика. – 2001. - №26. – с. 9-23.


14. http://combinatorica.narod.ru/second.htm

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Элементы комбинаторики

Слов:7060
Символов:55798
Размер:108.98 Кб.