Три урока комбинаторики

Методические рекомендации для учащихся

Составитель Е.В.Мочалова

Иваново 2010

Урок 1. Основные правила комбинаторики.

План.

1. Предмет комбинаторики.

2. Основные правила комбинаторики.

Общие правила комбинаторики.

В основе решения задач на комбинаторику лежат следующие два правила.

1. Правило сложения.

Если некоторые элемент A  можно выбрать m способами, а другой элемент B – n способами, исключающими друг друга, то выбор какого-нибудь одного из этих элементов (либо А, либо В) можно осуществить m+n способами.

2. Правило умножения.

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

Эти правила можно обобщить на случай любого конечного количества элементов.

Задачи.

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

Решение.

За­дача сводится к под­счету числа всех возможных групп, которые можно сос­тавить из цифр 1, 2,  3, используя каждую из цифр не более од­ного раза. Прежде всего выпишем все эти группы. При этом процесс состав­ления таких групп будем изображать в виде так называе­мого «дерева» (см. рис.). Для этого из некоторой точки С проведем три отрезка, соответствующие числу различных выборов, которые можно сделать на первом этапе (в каче­стве первого элемента группы может быть взята любая из цифр 1, 2, 3). Из конца каждого построенного отрезка про­ведем по два отрезка, что соответствует числу выборов, которые можно сделать на втором этапе, если в первый раз был выбран данный элемент (например, если в качестве первой цифры группы была взята цифра 2, то в качестве второй цифры можно взять любую из цифр 1, 3). Далее, из конца каждого из полученных отрезков проведем по отрезку, соответствующему выбору, который можно сделать на третьем этапе, если на первых двух этапах были выб­раны данные цифры.

Двигаясь всеми возможными путями из точки О к край­ней правой вершине «дерева», мы получим 6 трехзначных чисел, которые можно составить из цифр 1, 2, 3.

Это же число можно получить сразу, используя прави­ло умножения. Так как для выбора первого элемента груп­пы имеется три способа, для выбора второго — два способа, а третьего — один способ, то по правилу умножения выбор трех элементов, составляющих группу, можно произвести 3*2*1 = 6 способами.

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

Решение.

В задаче требуется найти количество трехзначных и четырехзначных чисел, которые можно составить из цифр 1, 2, 3, 4 или, что тоже самое, число способов, которыми можно составить либо трехзначное, либо четырехзначное число из этих цифр. По правилу умножения - четырехзначное число можно составить 4*3*2*1=24 способами, трехзначное число 4*3*2=24 способами. Тогда выбор либо трехзначного, либо четырех­значного числа может быть осуществлен по правилу сло­жения 24+24=48 способами. Таким образом, общее количество трехзначных и четырехзначных чисел, которые можно составить их цифр 1, 2, 3, 4, используя при составлении числа каждую цифру не более одного раза, равно 48.

Урок 2. Понятие факториала.

План

1. Понятие факториала

2. Выполнение действий с факториалами

Задачи.

1. Вычислить: а) 3!; б) 7! - 5!; в)  (7!+5!)/6!

Решение.

а) 3!= 1·2·3 = 6.

б) Так как 7! = 1·2·3·4·5·6·7 и 5! = 1·2·3·4·5, то можно вынести за скобки 5! Тогда получим  5!(6·7-1) = 5! ·41 = 1·2·3·4·5·41 = 120·41 =4920.

в)

2. Упростить выражения :

а)   б)   в)

Решение:

а) Так как  и n!=1·2·3·…·n, то 

б)

в)

Урок 3. Размещения. Перестановки. Сочетания.

План.

1. Размещения.

2.Перестановки.

3. Сочетания.

В разделе математики, который называется комбинаторикой, решаются некоторые задачи, связанные с рассмотрением мно­жеств и составлением различных комбинаций из элементов этих множеств. Например, если взять 10 различных цифр 0, 1, 2, 3, ... , 9 и составлять из них комбинации, то будем получать раз­личные числа, например, 345, 534, 1036, 5671, 45 и т. п.

Мы видим, что некоторые из таких комбинаций отличаются только порядком цифр (например, 345 и 534), другие -  входящими в них цифрами (например, 1036 и 5671), третьи разли­чаются и числом цифр (например, 345 и 45).

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

Число размещений из n различных элементов по k без повторений:

 =n(n-1)…(n-k+1)=n!/(n-k)!          (1)

 Число размещений из n различных элементов по k с повторениями:

=n^k.                                               (2)

Задачи.

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

Решение.

Задача сводится к нахождению числа раз­мещений (без повторений) из шести элементов по два, так как здесь существенно и то, кто будет выбран в ру­ководство месткома, и то, как распределятся обязанности между ними. Таким образом, искомое число равно

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

Решение.

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

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

P_n=n!                                   (3)

Число перестановок из n различных элементов с повторениями, которые можно сделать из k₁ элементов 1 типа, k₂ элемента-2 типа, …, k_n элемента n типа находится по формуле:

    (4)

Задачи.

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

Решение.

Рассматриваемое четырехзначное число может быть представлено как некоторая перестановка из цифр 0, 1, 2, 3, в которой первая цифра отлична от нуля. Так как число перестановок из четырех цифр равно Р₄= = 4! и из них 3! перестановок начинаются с нуля, то ис­комое количество равно

4!-3! = 3*3! = 1*2*3*3=18.

2. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение.

Речь идет об отыскании числа переста­новок с повторениями, которые можно сделать из k₁= 4 элементов первого типа (зеленых бус), k₂=5 элементов второго типа (синих бус) и k₃= 6 элементов третьего типа (красных бус). По формуле (4) получаем

Число сочетаний из n различных элементов по k без повторения:

C^k_n=n!/k!*(n-k)!                  (5)

Число сочетаний без повторений из n элементов по k равно числу сочетаний из этих же  n элементов по (n-k):

C^k_n=C^n-k_n                                                 (5’)

Число сочетаний с повторениями из n различных элементов по k

C^k_n=C^k_n+k-1=(n+k-1)!/(k! · (n-1)!)    (6)

Задачи.

1. Сколько различных правильных дробей можно составить из чисел 1, 2, 3, 5, 7, 11, 13, берущихся попарно?

Решение.

Различных пар из данных чисел, в кото­рых первый элемент меньше второго, будет, очевидно, столько, сколько можно составить сочетаний из семи эле­ментов по два. Отсюда по формуле (5) получаем искомое число

2. В кондитерском магазине продаются три сорта пирожных: наполеоны, эклеры и слоеные. Сколькими способами можно купить 9 пирожных?

Решение.

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

Вопросы и задачи для самостоятельного решения

1.       Что называется п-факториалом?

2.       Вычислите 5!; 7!.

3.       Запишите, чему равен п!.

4.       Вычислите

5.       Вычислите

6.       Вычислите

7.       Перечислите основные задачи комбинаторики.

8.       Что называется перестановками?

9.       Запишите формулу для числа перестановок из m элементов.

10.    Вычислите число перестановок из 5 предметов.

11.    Что называется размещениями?

12.    Запишите формулу числа размещений из т элементов по п.

13.    Вычислите .

14.    Что называется сочетаниями?

15.    Запишите формулу для числа сочетаний из. т элементов по п.

16.    Вычислите

17.    На 6 карточках было записано слово «победа». Их рассыпали и взяли снова только 4 карточки. Какова вероятность того, что получится слово «обед»?

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

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

20.    Сколькими способами можно поставить на книж­ную полку 15 книг так, чтобы три определенные книги ока­зались рядом?

21.    В пространстве даны 7 точек, никакие четыре из которых не лежат в одной плоскости. Сколько различных плоскостей можно провести через эти 7 точек?

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

23.    Сколько точек М (х; у) можно образовать, если абсцисса х и ордината у могут принимать значения 1, 2, 3, 4, 5, 6?

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

25.    В партии содержится 30 деталей,  из них 8 де­фектных. Сколькими способами из этой партии можно отобрать 6 деталей так, чтобы четыре из них были каче­ственные и две дефектные?

Литература

1. Мордкович А.Г. События. Вероятности. Статистическая обработка данных: Доп.параграфы к курсу алгебры 7-9 кл. общеобразоват. Учреждений / А.Г.Мордкович, П.В.Семенов. - 5-е изд.- М.: Мнемозина, 2008
2. Мордкович А.Г. Алгебра и начала математического анализа. 10 класс (профильный уровень) - М.: Мнемозина, 2010