112828 (Методика обучения школьников основам комбинаторики, теории вероятностей и математической статистики в рамках профильной школы), страница 5

Полученный результат является одним из важнейших в комбинаторике. На нем основан вывод многих формул комбинаторики. Его называют «правилом произведения». Сформулируем это правило так. Если элемент а₁ можно выбрать n₁ способами, после каждого выбора этого элемента следующий за ним элемент а₂ можно выбрать n₂ способами … после выбора элементов а₁, а₂, …, а_k-1 элемент а_k выбирается n_k способами, то кортеж (а₁, а₂, …, а_k) можно выбрать n₁ ∙ n₂ ∙ … ∙ n_k.

Подсчитаем, например, сколько слов, содержащих 6 букв, можно составить из 33 букв русского алфавита при условии, что любые две стоящие рядом буквы различны (например, слово «корова» допускается, а слово «колосс» нет). При этом, разумеется можно писать бессмысленные слова. В этом случае на первое место у нас 33 кандидата. Но после того, как первая буква выбрана, вторую можно выбрать лишь 32 способами – ведь повторять первую букву нельзя. На третье место тоже 32 кандидата – первую букву уже можно повторить, а вторую – нельзя. Также убеждаемся, что на все места, кроме первого, имеется 32 кандидата. А так как число этих мест равно 5, то получаем ответ 33∙32∙32∙32∙32∙32=1107396236.

Задачи на непосредственное применение комбинаторных правил произведения и суммы:

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

2. Сколько чисел среди первых 100 натуральных чисел не делятся ни на 2, ни на 3, ни на 5?

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

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

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

Занятия №4, 5, 6. Размещения. Перестановки. Сочетания.

Эти занятия можно построить с использованием презентации (см. Приложение 1) по единой схеме: определение → вывод формулы (доказательство) → пример. По мере рассмотрения каждого из комбинаторных понятий целесообразно отработать с учащимися эти понятия на символическом материале. Для усвоения содержания понятия нужно рассмотреть упражнения по составлению объектов, относящихся к определенному комбинаторному понятию. Эти упражнения должны носить внутримодельный характер. Упражнения лучше давать на карточках. Систему упражнений и задач можно подобрать из.

Занятие №7. Самостоятельная работа.

В начале занятия учащиеся должны самостоятельно заполнить таблицу, представленную в презентации (слайд 23), что будет способствовать систематизации и актуализации знаний, полученных на предыдущем занятии.

Вариант 1

1. Сколькими способами можно обозначить вершины данного треугольника, используя буквы A, B, C, D, E и F?

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

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

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

5. В магазине продают кепки трёх цветов: белые, красные и синие. Наташа и Лена покупают себе по одной кепке. Сколько существует различных вариантов покупок для этих девочек?

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

Вариант 2

1. Сколькими способами можно обозначить вершины куба буквами A, B, C, D, E, F, G, K?

2. Сколькими способами можно разложить 12 различных деталей по трем ящикам?

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

4. В библиотеке Кате предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами она может выбрать из них 3 книги и 2 журнала?

5. Найти число различных способов, которыми можно записать в один ряд 6 плюсов и 4 минуса.

6. В списке класса для изучения английского языка 15 человек. Сколько существует вариантов присутствия (отсутствия) этих людей на занятии?

Занятие №8. Некоторые свойства сочетаний.

Этот вопрос можно предложить учащимся в качестве самостоятельной работы.

I.

а) Составьте всевозможные сочетания по 2 элемента без повторений из элементов множества М={а, б, в, г, д}. Для каждого из составленных подмножеств выпишите дополнения - трехэлементные подмножества оставшихся элементов - и сравните число тех и других. Какой вывод можно сделать о числах и ?

б)Из n элементов некоторого множества составлены всевозможные k-элементные подмножества и соответствующие им дополнения — (n-k) – элементные подмножества оставшихся элементов. Какой вывод можно сделать о сравнительной величине чисел и ?

в) Воспользуйтесь формулой подсчета числа сочетаний без повторений и докажите равенство = . Это равенство выражает одно из важных свойств сочетаний. Им удобно пользоваться для вычисления в случае k> n.

г) Не производя вычислений, выберите равные из следующих чисел: , , , , , , , , , , , , , .

д) Вычислите , , .

е) Множество М={а, б, в, г, д, е} разбейте всеми возможными способами на два подмножества так, чтобы в одно из них входило 2 элемента, а в другое - 4.

ж) Из 12 человек нужно составить 2 волейбольные команды по 6 человек в каждой. Сколькими способами это может быть сделано?

II. Докажите следующее свойство сочетаний:

+ + +…+ =2ⁿ.

а) Возьмите множество М={а, b, с} из трех элементов и составьте k-элементные подмножества М /k=0, 1, 2, 3/.

Каждому подмножеству поставьте в соответствие последовательность из трех цифр – единиц и нулей – следующим образом: каждому из трех элементов а, b, с поставьте в соответствие 1, если он входит в подмножество, 0 – если он в подмножество не входит. Рассмотрите таблицу

Таблица 1.

Число всех подмножеств множества М равно + + + и равно числу всех последовательностей длины три из единиц и нулей. Число таких последовательностей нетрудно подсчитать: каждое из трех мест в последовательности может быть занято 1 или 0, то есть двумя способами, а все три места – по принципу умножения – 222=2³ способами. Это число можно получить и по формуле подсчета числа размещений с повторением, таким образом, + + + =2³.

б) Проведите аналогичные рассуждения для множества из n элементов. Тогда какие изменения следует внести в таблицу? Сделайте вывод, результат запишите.

Занятие №9. Свойство сочетаний = + и треугольник Паскаля.

I. Для изучения следующего свойства сочетаний предварительно составим трехэлементные подмножества множества М={а, б, в, г, д}. Затем выберем из множества М любой элемент, например, «а» и разобьем все подмножества на два класса: не содержащие «а» и содержащие «а».

I класс: {б, в, г}, {б, в, д}, {б, г, д}, {в, г, д}

II класс: {а, б, в}, {а, б, г}, {а, б, д}, {а, в, г},

{а, в, д}, {а, г, д}.

Первый класс состоит из всевозможных сочетаний без повторений по три элемента из следующих четырех: б, в, г, д. Таких сочетаний . Каждое подмножество второго класса состоит из элемента «а» и двух элементов, выбираемых из множества следующих элементов: б, в, г, д. Очевидно, число таких подмножеств равно .

Подмножества I и II классов исчерпывают все трехэлементные подмножества множества М, что означает:

= + .

Аналогичными рассуждениями получите равенство:

= + .

Убедитесь в справедливости последнего равенства, воспользовавшись формулой подсчета числа сочетаний без повторений.

II. Составим таблицу значений при различных значениях n и k. В таблицу 2 занесем значения =1, =1, =1, =1, =2, =1. Заполните остальные строки таблицы, используя свойство сочетаний.

Займемся изучением таблицы 2.

Первые и последние элементы любой строки равны 1, так как = =1. Это равенство будем считать верным и при n=0 (пустое множество своим единственным подмножеством имеет самое себя).

Любой другой элемент таблицы 2 согласно свойству сочетаний, на основании которого составлена таблица, равен сумме двух элементов предшествующей строки: стоящего непосредственно над ним и стоящего над ним слева.

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

Исследованием свойств такой треугольной таблицы и применениями ее занимался выдающийся ученый Франции Блез Паскаль (1623 —1662). Поэтому рассматриваемую таблицу часто называют треугольником Паскаля. Хотя задолго до Паскаля этот треугольник встречался в работах итальянских и арабских математиков.