close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Методический комментарий, разбор решения задач, сюжетов,
проектов, заданий занятия кружка
Глава III
Комбинаторика
Введение
После многолетней борьбы комбинаторика появилась (точнее восстановилась) в школе
и сдвигается в младшие классы. Чем раньше школьники приучаются к комбинаторным
подсчетам, тем легче они им даются. У автора был случай, когда ему пришлось развлекать
школьников 2-4 классов в течение двух часов. Через полчаса они легко решали
комбинаторные задачи (с небольшими числовыми данными), которые были трудны
первокурсникам университета. Чем меньше теории человек знает, тем более он открыт к
восприятию простейших естественных способов пересчета. Вот почему мы рекомендуем
не стремиться к обобщениям, точным формулировкам и общим формулам, а приучать
детей в каждой задаче строить рассуждение (на самом деле строить конструкцию) заново.
Единственно, что может оказаться полезным – это ввести в оборот «стандартные задачи»,
выбрать которые учитель может сам по своему вкусу.
Во введении рассказывается о древнем происхождении комбинаторики, о некоторых
комбинаторных задачах, которые уже стали легендарными. Знакомство с этими задачами,
рассказ о том, как они решались, должно быть интересно ученикам и, возможно,
подогреет интерес к решению комбинаторных задач.
§ 1. Правило произведения
Правило произведения, с которым происходит знакомство в этом параграфе,
пронизывает всю комбинаторику. На первом этапе нужно избегать ограничений на выбор
вариантов.
Подсчитываем число вариантов.
Центральное рассуждение этого раздела – подсчет числа событий при их независимом
повторении – является необычайно важным. Оно будет повторяться в дальнейшем
многократно. Самое опасное – приучить школьников пользоваться готовой формулой.
Они должны быть готовы к тому, что в ответе появится степень, но при решении каждой
задачи они должны рассуждать с самого начала.
Обратите внимание на слово независимые события. Его можно пока оставить без
должного внимания и вернуться к нему, когда появятся ограничения, хотя какие-то
ограничения уже встречаются в следующих разделах (например, чередование гласных и
согласных, четности и т. п.). Можно предложить ученикам привести примеры
независимых и зависимых событий при повторении.
Подсчитываем число слов
Хотя в этом разделе в основном речь идет о подсчете числа слов, важно подчеркнуть и
обратить внимание учеников, что слова могут быть заменены любыми предметами
n сортов, которыми нужно заполнить k мест.
Подсчитываем число делителей.
Подсчет числа делителей с комбинаторной точки зрения не выходит за рамки
применения правила произведения. Однако мы считаем важным включить этот вопрос,
соединяющий разложение на множители с задачами на подсчет вариантов.
Несмотря на то, что в этом разделе используется только правило произведения, он,
судя по опыту, является непростым и может считаться выходящим за рамки обязательного
минимума.
Вокруг теории
1. 10  15 = 150.
2. 35.
3. 5.
4. ( k  1)( l  1) .
Ответы и комментарии к заданиям
1.
30  25  20 = 1500.
3.
2) 440; 4) 32; 6)320; 8)562.
В общем виде ответ и ход решения можно записать так: 1) mn, 2) mn + mn = 2mn, 3)
(m + n)2, 4) m + n, 5)(m + n)2 – (m + n), 6) n  (m + n), 7) (m + n)2 – m2, 8) n2 + m(m – 1).
4.
1) 4  3 = 12, 2) 2  3 = 6, 3) 4  3  2 = 24, 4) 4  2  4  3 = 96.
Обратите внимание учеников, что в задаче 4) в квадратики можно вставлять цифры
независимо друг от друга. Можно было подумать, что одинаковые квадратики заменяют
одинаковые цифры. Такие неточности очень характерны для комбинаторики, и не нужно
их избегать. Надо объяснить, что, начиная решать задачу, необходимо уточнить условие
задачи, если его можно понимать по-разному. Полезно разобрать все возможные случаи.
Если в квадратики вставлять одинаковые цифры, то ответ изменится: 4  3  2 = 24.
Возможная ошибка: увидев в выражении знак «+», ученик может начать складывать (а не
перемножать) число вариантов.
1) 216; 3) 8; 5) 144; 7) 612 .
5.
6. Ответ: 35.
7.
1) 310; 3) 53 (берем ученика и выбираем ему класс).
8.
1) 106; 3) 74; 5) 10·9·8·7·6·5 =
10 !
.
4!
2015. Число трехбуквенных слов – 203; число фраз из 5 слов: (203)5 = 2015.
9.
a) 1) 48; 2) 36; 3) 12; 4) 18; 5) 6; 6) 8; 7) 9; 8) 8; 9) 3; в) 1) 4·3·3·3=108; 2) 81;
11.
3) 27; 4) 54; 5) 16; 6) 16; 7) 6; 8) 36; 9) 6.
12. В разложении примера б) на множители опечатка. Должно быть:
f 2  ( x  1)( x  4) ( x  1)  ( x  1)( x  1)( x  2) ( x  2) ( x  1) . Кроме того,
4
2
2
2
2
2
2
2
3
в примере 5) опечатка в нумерации: первое и третье условия относятся к многочлену а), а
второе и четвертое – к многочлену б).
б) 1) 35; 2) 7; 3) 9; 4) 14; 5) 27 и 16.
В 1) достаточно рассмотреть самый большой делитель, раскладывающийся на
линейные множители (при этом нужно не пропустить многочлены ( x  2) и ( x  2) ,
2
которые
также
являются
произведением
линейных
2
множителей):
( x  1)( x  1)( x  2)( x  2)( x  2)( x  2) .
Каждый из множителей может входить или не входить в это произведение, причем хоть
один множитель входит обязательно, т.е. мы можем записать этот делитель в виде
( x  1) ( x  1) ( x  2) ( x  2) ,
k
l
s
t
где
0  k  1, 0  l  1, 0  s  2, 0  t  2 ,
при
этом k , l , s , t не могут быть равны нулю одновременно. Всего таких делителей должно
быть 2·2·3·3–1=35.
§2. Перестановки
Ставим по местам
Перестановки по своему смыслу – это составление упорядоченных наборов из
элементов одного и того же множества. Если выбор элементов происходит независимо
друг от друга, то мы оказываемся в ситуации применения правила произведения, только
умножаем одинаковые числа и получаем в ответе степень. В классической комбинаторике
это называлось размещениями с повторениями, однако мы не рекомендуем употребление
этого термина. Типичные ситуации: число последовательностей двоичных символов (да –
нет, плюс – минус, верно – неверно, азбука Морзе, 0 – 1 и т. п.), составление слов с
фиксированным числом букв при независимом их употреблении.
Несложной комбинацией принципа составления перестановок с принципом
произведения являются задачи, в которых появляются ограничения на использование
объектов на определенных местах. Например, перечисляя количество четырехзначных
чисел, мы должны учесть, что на первом месте не должно быть нуля и поэтому ответ
будет не 104, а 9  103.
Типичные ситуации: рассадка людей по местам, составление последовательностей
различных карточек и т. п. Тот же принцип произведения приводит к известному
выражению типа n (n – 1)  …  (n – k + 1) …3·2·1=n!, т.е. при вычислении числа
перестановок возникает важное понятие факториала.
Переставляем буквы
Перестановки являются частным случаем размещения. В размещениях число
размещаемых объектов может быть меньше числа мест. Классическое размещение связано
с идеей действительного выбора, «взятия» навсегда объекта из данного множества и
«помещения» его на определенное место (отсюда этимология термина размещение).
В этом разделе ученик впервые знакомится с понятием рекурсии, когда
новый член последовательности вычисляется через предыдущие.
Вокруг теории
1. 6!
2. Произведение всех натуральных чисел от 1 до k : 1·2·3·…·(k-1)· k.
3. n  15 .
4. 100А.
Ответы и комментарии к заданиям
1. Ответ: 5!
6. Ответ: 3!
9.
1) 6·3·3·3=162(взяли сначала любую цифру, а потом чередуем четность, цифры
могут повторяться). Сравните с числом шестизначных чисел с тем же условием;
2) 6543=360;
3) 3543=180 (начинаем с конца или берем половину чисел
предыдущей задачи);
4) 43=12 (две последние цифры 2 и 5 определены однозначно);
5) 64=1296
12. Ответ: 476533=7560.
13. Надо условиться, как записывать перестановки трех символов. Их общее число равно
6. Частый способ записи:
x

a
y
b
z
 , где a,b,c – перестановка букв x, y, z. Можно
c 
прямо писать строчку (a, b, c), что мы и сделаем.
1) Все 6 перестановок; 2) Только «тождественная» перестановка (x, y, z), которая
ничего не меняет; 3) (x, y, z) и (x, z, y); 4) (x, y, z) и (y, x, z,); 5) (x, y, z) и (z, y, x);
6) (x, y, z), (y, z, x) и (z, x, y).
Последняя задача труднее остальных. Можно заметить, что каждая из 6 перестановок
либо совсем не меняет многочлен, либо меняет его знак (четные и нечетные
перестановки).
§3. Треугольник Паскаля
Выбираем два элемента из n
Подсчет числа сочетаний (числа k-элементных подмножеств n-элементного
множества).
достаточно трудно.
Основная идея классического способа подсчета числа сочетаний
k
состоит в переходе от упорядоченных наборов к неупорядоченным (от размещений A n к
k
сочетаниям C n ) с помощью формулы типа C nk  k !  A nk . Поэтому рекомендуем начинать с
выбора двух элементов, в этом случае задача становится более понятной: сначала
выбираем первый элемент – n способов, из оставшихся элементов выбираем еще один
элемент – (n–1) способ.
Всего получаем n ( n  1) способ выбора. Но так как в задаче порядок выбора не имеет
значения, то вариантов выбора будет вдвое меньше, т.е. C n 
2
n ( n  1)
.
2
Выбираем k элементов из n
Теперь можно перейти к выбору трех элементов из n и получить формулу:
Cn 
3
n ( n  1)( n  2)
3!
и ее другой записи C n 
, а затем и к общей формуле C n 
k
n!
k
k !( n  k )!
n ( n  1)( n  2)...( n  k  1)
k!
. Изложение темы в учебнике, делающее акцент на
решение «модельных» задач, а не на доказательство формул, позволяет достаточно
продуктивно использовать отводимое время на развитие комбинаторного мышления
учащихся.
Комбинаторика представлена в учебнике весьма богатым набором заданий, которые
смогут обеспечить любой вкус и любой исходный уровень учащихся.
Составляем треугольник Паскаля
О треугольнике Паскаля уже шла речь, когда учащиеся знакомились с формулами
сокращенного умножения и биномом Ньютона. В этом разделе также рассматривается
«модельная задача» о нахождении коэффициентов в разложении бинома ( x  1) и ее
5
обобщение ( x  1) . Учащиеся знакомятся с биномиальными коэффициентами и их
n
k
связи с числом сочетаний C n .
Вокруг теории
1. C n 
2
2. C n 
3
n ( n  1)
.
2
n ( n  1)( n  2)
.
3!
s
3. Сумма чисел в строке с номером s равна 2 . Коэффициенты в разложении бинома
( x  1) расположены в строке с номером s : ( x  1)  x  sx
s
s
S
s 1
 ...  sx  1 . Если
положить x  1 , то, с одной стороны, мы получим 2 , а с другой стороны, сумму
s
коэффициентов.
Приведем для сведения учителя несколько стандартных тождеств с числами
треугольника Паскаля, обозначенными как обычно через C nk .
1. C kk  C kk  1  C kk  2  ...  C kk  s  C kk s1 1
2. 1  C n0  2 C n1  3C n2  ...  ( n  1) C nn  ( n  2 ) 2 n 1 – доказательство этого тождества доступно сильным учащимся: его надо «перевернуть» и сложить с самим собой.
3. C n0   C n1   ...  C nn   C 2nn .
2
2
2
4. C n0 C mk  C n1 C mk  1  C n2 C mk  2  ...  C mk  n .
Тождества 3 и 4 и многие другие им подобные получаются из сравнения
коэффициентов при некоторой степени x в тождествах типа (1 + x)m (1 + x)n = (1 + x)m+n.
5. 2 C n  2 C n  2 C n  ...  2 C n  3 – это сумма коэффициентов многочлена
0
0
1
1
2
2
n
n
n
(1 + 2x)n.
Ответы и комментарии к заданиям
k 1
5. Ответ: 3) kC n  nC n 1 .
k
6. Утверждения 3, 4, 6, 7 являются верными, остальные – нет.
Сюжет 1. Шестизначные числа.
1) 18·104; 3) 9  10  8  9 (из общего числа шестизначных чисел вычитается число
5
5
чисел, не содержащих цифру 7) ; 5) 5  4  5  9  5 ; 7) 9·103; 9) 96; 11) 9·102.
6
5
5
Сюжет 3. Число одночленов
По уровню комбинаторных рассуждений, необходимых для такого подсчета, мы,
конечно, забегаем немного вперед, но как-то не хочется разрывать комбинаторику с
изучаемым алгебраическим материалом. Поэтому вопрос подсчета одночленов
разбирается в большой степени эмпирически. Будет достаточно, если ученики освоят
процесс перебора одночленов с двумя буквами.
Комбинаторная задача (если ее рассматривать в общем виде) традиционно относится к
числу трудных. В занятии математического кружка мы расскажем о ней подробно.
Мы рассматриваем простейший случай, когда k = 2, и все легко подсчитать простым
перебором вариантов, а затем от k = 2 легко перейти к k = 3, k = 4 и т.д. .
В учебнике есть ответы ко всем заданиям сюжета.
Сюжет 4. Число делителей
С подсчетом числа делителей мы уже встречались в §1 этой главы, когда изучали
правило произведения. Мы там подсчитывали число делителей многочленов. Те же
рассуждения применимы и при подсчете числа делителей у чисел.
4.
1) 11; 2) 101; 3) k+1; 4) 2(k+1); 5) 8; 6) 16; 7) 6; 8)24 6; 9) 60.
5.
1) 4; 2) 8; 3) 9; 4) 16; 5) 16.
Проект. Деление частицы
Заключительные вопросы
1)
В
( x  1)  C n x  C n x
n
k 2
0
n
k 1
1
n 1
C n2  2C n2  C n2 
разложении
 Cn x
2
n2
 ...  C n x  C n положить
( n  2)!
k
n 1
бинома
( k  2)!( n  k )!

n
2( n  2)!
( k  1)!( n  k  1)!

x  1;
( n  2)!
k !( n  k  2)!
4)
.
Вынесем ( n  2)! за скобки и приведем к общему знаменателю, воспользовавшись
тождеством ( n  k )!  ( n  k )( n  k  1)!  ( n  k )( n  k  1)( n  k  2)!
Математический кружок
Занятие 5. Подсчитываем число одночленов
Задача. Каким числом способов можно представить число n в виде упорядоченной
суммы k слагаемых?
Эту задачу можно сформулировать и таким образом:
1. Сколько есть решений xi  0 для уравнения x1 + … + xk = n?
2. Каким числом способов можно разложить n одинаковых предметов в k различных
ящиков (вместимости ящиков не ограничены)?
3. Сколько можно составить одночленов степени n из k букв (с числовым
коэффициентом 1)?
Простейшее решение задачи таково. Представим число n в виде n одинаковых
предметов (палочек) и будем ставить между палочками перегородки (рис. ). Одна
перегородка разбивает палочки на 2 множества, две перегородки – на 3 и т. д. Поставим
k – 1 перегородку. Теперь у нас есть объекты двух сортов – палочки (их n штук) и
перегородки (их k – 1 штука). Они вместе занимают n + k – 1 мест и их надо по-всякому
переставить (заметьте, что две рядом стоящие перегородки дают пустой ящик). Это
k 1
n
можно сделать C n  k  1  C n  k  1 способами.
Разумеется, это приводится для сведения учителя, а не для рассказа в классе. Для
учащихся рассуждения в учебнике приводятся, как обычно, на «модельных» примерах,
а затем указывается, как перейти к общему случаю.
3 1
1. Ответ: С 5  3 1  С 7  21 .
2.
2
а) С 13 = 286; б) С 9  84 .
3
3
Комментарий. В случае б) мы также можем воспользоваться «кружочками» и
«перегородками», только теперь перегородки не должны попадать в одно место, т.е. мест
для перегородок будет n  1 , а самих перегородок будет k  1 . В общем случае число
k 1
вариантов разбиения числа n на k слагаемых равно C n 1 .
3.
а) С 11 
3
11  10  9
6
 165 ; б) С 7 =35.
3
Вместо вычисления числа сочетаний, можно было бы воспользоваться треугольником
Паскаля.
Рекомендуем обратить внимание учащихся на то, что, хотя сама задача о разбиении
числа n на k слагаемых довольно сложная, и даже в простых случаях, с небольшими
значениями n и k , непосредственный подсчет числа слагаемых вызвал бы затруднения,
но визуализация задачи сразу делает ее доступной для понимания и вывода
соответствующей формулы.
Занятие 6. Подсчитываем число анаграмм
Составление анаграмм – это перестановки букв в слове, в котором могут быть и
одинаковые буквы.
4!
7!
9!
11!
1. а)
 6 ; б)
 420 ; в)
 15120 ; г)
 83160.
2!2!
3!2!
4!
5!2!2!
Комментарий. Если бы все буквы были различны, то число анаграмм равнялось бы числу
перестановок букв, но при наличии одинаковых букв нужно исключить случаи их
перестановок. Если в слове буква повторяется k раз, то количество анаграмм уменьшится
в k ! раз.
2. а) C12 C 8  34650 ; б) 13860; в) задачу можно переформулировать так: Пусть
4
4
k  l  m  n . Сколько раз при возведении ( a  b  c ) встретится одночлен a b c ,
или, что то же самое, сколькими способами можно «распределить» показатель n по
k l m
буквам a , b , c так, чтобы получить одночлен a b c ; г) 34650; 13860; 1980 и 924
(первые два ответа взяты из пунктов а) и б) соответственно.
n
k
l
m
1/--страниц
Пожаловаться на содержимое документа