§ 1. Примеры комбинаторных задач и общие принципы комбинаторики

Составление слова из восьми букв можно представить как заполнение буквами клеток следующей таблицы: Составление слова из восьми букв можно представить как заполнение буквами клеток следующей таблицы: На первое место можно поставить любую из восьми букв, на второе - любую из семи оставшихся и т.д. вплоть до заполнения единственным способом клетки 8 последней оставшейся буквой. Число способов заполнения таблицы будет равно 8·7·6·5·4·3·2·1=8! На первое место можно поставить любую из восьми букв, на второе - любую из семи оставшихся и т.д. вплоть до заполнения единственным способом клетки 8 последней оставшейся буквой. Число способов заполнения таблицы будет равно 8·7·6·5·4·3·2·1=8! Напомним, что символом п! (читается «эн факториал») обозначается произведение всех натуральных чисел от 1 до п: n!=1·2·...·(n-1)·n. Напомним, что символом п! (читается «эн факториал») обозначается произведение всех натуральных чисел от 1 до п: n!=1·2·...·(n-1)·n. Ответ: n!= (n -1) п. Ответ: n!= (n -1) п.

Пусть множество А ={a 1,...,а т } состоит из т элементов, а множество В = {b 1,...,b n } - из n элементов. Рассмотрим множество, состоящее из всевозможных упорядоченных пар (а,b), где элемент а принадлежит множеству А, а элемент b принадлежит множеству В (такое множество называется декартовым произведением множеств А и В и обозначается A×В). Иными словами, рассматривается множество, элементами которого являются «карточки» вида Пусть множество А ={a 1,...,а т } состоит из т элементов, а множество В = {b 1,...,b n } - из n элементов. Рассмотрим множество, состоящее из всевозможных упорядоченных пар (а,b), где элемент а принадлежит множеству А, а элемент b принадлежит множеству В (такое множество называется декартовым произведением множеств А и В и обозначается A×В). Иными словами, рассматривается множество, элементами которого являются «карточки» вида Слово «упорядоченные» в определении А×В особенно важно, когда в А и В есть одинаковые элементы. Например, если А = В = {a,б,...,я} Слово «упорядоченные» в определении А×В особенно важно, когда в А и В есть одинаковые элементы. Например, если А = В = {a,б,...,я} русский алфавит, то элементы А×В можно считать словами, а ax и xa - разные слова! русский алфавит, то элементы А×В можно считать словами, а ax и xa - разные слова! аb

Правило произведения: множество A×В содержит тn элементов. Правило произведения: множество A×В содержит тn элементов. Доказательство этого утверждения почти очевидно, т.к. все элементы-карточки можно расположить в виде прямоугольной таблицы, в которой т строк и n столбцов. Доказательство этого утверждения почти очевидно, т.к. все элементы-карточки можно расположить в виде прямоугольной таблицы, в которой т строк и n столбцов.

Множество А×В×С, состоящее из упорядоченных троек, содержит тnр элементов (р - число элементов в множестве С). Действительно, карточек вида abc 1 столько, сколько элементов в А×В, т.е. тn, столько же карточек вида abc 2 и т.д. В этом случае А× В×С можно представить в виде прямоугольного параллелепипеда. Множество А×В×С, состоящее из упорядоченных троек, содержит тnр элементов (р - число элементов в множестве С). Действительно, карточек вида abc 1 столько, сколько элементов в А×В, т.е. тn, столько же карточек вида abc 2 и т.д. В этом случае А× В×С можно представить в виде прямоугольного параллелепипеда.

Множество А 1 ×А 2 ×...×А р состоит элементов, где n1- число элементов в А 1, n 2 - в А 2 и т.д. Доказывается это утверждение индукцией по р аналогично рассмотренному выше переходу от p=2 к p=3. Множество А 1 ×А 2 ×...×А р состоит элементов, где n1- число элементов в А 1, n 2 - в А 2 и т.д. Доказывается это утверждение индукцией по р аналогично рассмотренному выше переходу от p=2 к p=3.

Пусть объект а 1 можно выбрать n 1, различными способами, после каждого выбора объекта а 1 объект а 2 можно выбрать n 2 различными способами,..., после каждого выбора объектов а 1, а2,..., а p -1 объект а p можно выбрать n р различными способами. Тогда количество способов, которыми можно выбрать а 1, а 2,..., а p равно n 1 n 2...n p. Пусть объект а 1 можно выбрать n 1, различными способами, после каждого выбора объекта а 1 объект а 2 можно выбрать n 2 различными способами,..., после каждого выбора объектов а 1, а2,..., а p -1 объект а p можно выбрать n р различными способами. Тогда количество способов, которыми можно выбрать а 1, а 2,..., а p равно n 1 n 2...n p.

Доказательство: если А к - множество состояний, из которых выбирается объект а к, то n к - число элементов множества А к (k=1,2,...,р), и мы получаем известную нам формулировку правила умножения. Доказательство: если А к - множество состояний, из которых выбирается объект а к, то n к - число элементов множества А к (k=1,2,...,р), и мы получаем известную нам формулировку правила умножения.

Пусть а 1 - первая буква слова, тогда ее можно выбрать 8 способами, т.е. n 1 = 8; вторую букву а 2 можно выбрать 7 способами, т.е. n 2 = 7 и т.д. По правилу умножения число всех комбинаций равно Пусть а 1 - первая буква слова, тогда ее можно выбрать 8 способами, т.е. n 1 = 8; вторую букву а 2 можно выбрать 7 способами, т.е. n 2 = 7 и т.д. По правилу умножения число всех комбинаций равно 8·7·... ·2·1. 8·7·... ·2·1.

Пример 2. Сколько четырехбуквенных «слов» можно составить из карточек «в», «е», «ч», «н», «о», «с», «т», «ь»? Пример 2. Сколько четырехбуквенных «слов» можно составить из карточек «в», «е», «ч», «н», «о», «с», «т», «ь»?

Пусть а к - к -я буква слова (к =1,2,3,4). Тогда n 1 = 8,n 2 = 7, n 3 =6, n А = 5 и по правилу произведения сразу получаем ответ: Пусть а к - к -я буква слова (к =1,2,3,4). Тогда n 1 = 8,n 2 = 7, n 3 =6, n А = 5 и по правилу произведения сразу получаем ответ: 8·7·6·5 = ·7·6·5 = Ответ: Ответ: 1680.

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

Выбор объекта а 1 - поля для белой ладьи - может быть сделан n 1 = 64 способами. Независимо от выбора этого поля белая ладья бьет 15 полей, поэтому для черной ладьи остается =49 полей: n 2 = 49. Выбор объекта а 1 - поля для белой ладьи - может быть сделан n 1 = 64 способами. Независимо от выбора этого поля белая ладья бьет 15 полей, поэтому для черной ладьи остается =49 полей: n 2 = 49. Ответ: число расстановок ладей равно 64 · 49 = Ответ: число расстановок ладей равно 64 · 49 = 3136.

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

Очевидно, что на каждой горизонтали и на каждой вертикали должна стоять только одна ладья. Будем расставлять ладьи последовательно, начиная с первой горизонтали. На первой горизонтали 8 клеток, и первую ладью можно поставить на любую из них. Когда мы будем ставить вторую ладью, то на второй горизонтали ей будут доступны 7 клеток и т.д. По правилу произведения получаем, что всего таких позиций 8! Очевидно, что на каждой горизонтали и на каждой вертикали должна стоять только одна ладья. Будем расставлять ладьи последовательно, начиная с первой горизонтали. На первой горизонтали 8 клеток, и первую ладью можно поставить на любую из них. Когда мы будем ставить вторую ладью, то на второй горизонтали ей будут доступны 7 клеток и т.д. По правилу произведения получаем, что всего таких позиций 8!

Если же считать ладьи различными (как в примере 3), то число перестановок ладей равно Если же считать ладьи различными (как в примере 3), то число перестановок ладей равно 64 · 49 · 36 · 25 · 16 · 9 · 4 · 1 = (8!)² 64 · 49 · 36 · 25 · 16 · 9 · 4 · 1 = (8!)² Действительно, для первой ладьи можно выбрать любое поле доски размером 8×8, вторая ладья фактически ставится на квадратную доску 7×7 (мы удалили одну горизонталь и одну вертикаль и «сдвинули» оставшиеся части доски) и т.д. Действительно, для первой ладьи можно выбрать любое поле доски размером 8×8, вторая ладья фактически ставится на квадратную доску 7×7 (мы удалили одну горизонталь и одну вертикаль и «сдвинули» оставшиеся части доски) и т.д. Зафиксируем одну из таких расстановок различных ладей. Число перестановок ладей на выделенных полях равно 8! (результат примера Зафиксируем одну из таких расстановок различных ладей. Число перестановок ладей на выделенных полях равно 8! (результат примера 1). Если мы считаем ладьи одинаковыми, то (8!)² позиций разбиваются на классы по 8! позиций в каждом, и все позиции данного класса будут одинаковыми. Поэтому число перестановок одинаковых ладей равно 1). Если мы считаем ладьи одинаковыми, то (8!)² позиций разбиваются на классы по 8! позиций в каждом, и все позиции данного класса будут одинаковыми. Поэтому число перестановок одинаковых ладей равно (8!)² /8!= 8!, что совпадает с ранее полученным ответом. (8!)² /8!= 8!, что совпадает с ранее полученным ответом.

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

В слове «комбинаторика» 13 букв. Если бы все они были различны, то, переставляя их, можно было бы получить 13! слов. Но в нашем слове буквы к, о, и, а встречаются по два раза. Обозначим их к1,к2,о1,о2,и1,и2,а1,а2. Ясно, что слова, отличающиеся перестановкой букв к1ик2 - одинаковые, так что 13! Слов разбиваются на пары одинаковых. Следовательно, если мы не различаем к1 и к2, то число всех слов будет равно 13!/2!. Но эта совокупность также разбивается на пары одинаковых с точки зрения буквы о слов и т.д. В слове «комбинаторика» 13 букв. Если бы все они были различны, то, переставляя их, можно было бы получить 13! слов. Но в нашем слове буквы к, о, и, а встречаются по два раза. Обозначим их к1,к2,о1,о2,и1,и2,а1,а2. Ясно, что слова, отличающиеся перестановкой букв к1ик2 - одинаковые, так что 13! Слов разбиваются на пары одинаковых. Следовательно, если мы не различаем к1 и к2, то число всех слов будет равно 13!/2!. Но эта совокупность также разбивается на пары одинаковых с точки зрения буквы о слов и т.д. 13! 13! 13! 13! Ответ: = =. Ответ: = =. 2!2!2!2! 16 2!2!2!2! 16

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

Всего нечетных цифр пять, поэтому выбор к-й цифры числа может быть сделан n к =5 способами (к =1, 2, 3, 4) а количество четырехзначных чисел, у которых все цифры нечетные, равно 5·5·5·5 = 625. Всего нечетных цифр пять, поэтому выбор к-й цифры числа может быть сделан n к =5 способами (к =1, 2, 3, 4) а количество четырехзначных чисел, у которых все цифры нечетные, равно 5·5·5·5 = 625.

Все четырехзначные числа, а их =9000, делятся на две группы: те, в записи которых все цифры нечетные, и те, в записи которых есть хотя бы одна четная цифра. Следовательно, количество чисел второго типа равно =8375. Все четырехзначные числа, а их =9000, делятся на две группы: те, в записи которых все цифры нечетные, и те, в записи которых есть хотя бы одна четная цифра. Следовательно, количество чисел второго типа равно =8375. Ответ: Ответ: 8375.

1) Если множество А состоит из т элементов, а множество В из n элементов, причем, эти множества не имеют общих элементов (т.е. А В = 0), то их объединение A U В, т.е. совокупность всех элементов из А и В, содержит т + n элементов. 1) Если множество А состоит из т элементов, а множество В из n элементов, причем, эти множества не имеют общих элементов (т.е. А В = 0), то их объединение A U В, т.е. совокупность всех элементов из А и В, содержит т + n элементов.

2) Если объект а можно выбрать т различными способами, а объект b можно выбрать n различными способами, причем результаты выбора объектов а и b никогда не совпадают, то выбор либо а, либо b» можно осуществить т + n различными способами. 2) Если объект а можно выбрать т различными способами, а объект b можно выбрать n различными способами, причем результаты выбора объектов а и b никогда не совпадают, то выбор либо а, либо b» можно осуществить т + n различными способами.

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

Выбор пары костей это выбор двух карточек вида a 1 b 1, a 2 b 2, Выбор пары костей это выбор двух карточек вида a 1 b 1, a 2 b 2, где можно считать, что а b. где можно считать, что а b. Выберем первую кость - это можно сделать 28 способами, из них в 7 случаях кость окажется дублем, т.е. кость вида aa, а в 21 случае кость вида ab, а < b. В первом случае вторую кость можно выбрать 6 способами, а число способов выбора пары костей по правилу произведения равно 7 · 6 = 42. Выберем первую кость - это можно сделать 28 способами, из них в 7 случаях кость окажется дублем, т.е. кость вида aa, а в 21 случае кость вида ab, а < b. В первом случае вторую кость можно выбрать 6 способами, а число способов выбора пары костей по правилу произведения равно 7 · 6 = 42. Во втором случае вторую кость можно выбрать 12 способами 6 костей вида a| * и 6 костей вида *| а,а число способов выбора пары равно 21·12 = 252. Во втором случае вторую кость можно выбрать 12 способами 6 костей вида a| * и 6 костей вида *| а,а число способов выбора пары равно 21·12 = 252. Следовательно по правилу суммы всего получается = 294 способа выбора упорядоченной пары. Следовательно по правилу суммы всего получается = 294 способа выбора упорядоченной пары. Ответ: 147 пар. Ответ: 147 пар.

Пример 8. Найти число подмножеств множества А, состоящего из n элементов. Пример 8. Найти число подмножеств множества А, состоящего из n элементов.

Пусть А = {а 1,а 2,...,а n }, тогда с каждым подмножеством X множества A можно связать карточку-паспорт вида Пусть А = {а 1,а 2,...,а n }, тогда с каждым подмножеством X множества A можно связать карточку-паспорт вида n-1 n n-1 n В этом паспорте в к-й клетке стоит 1, если а к Є Х, 0 – если а к Є X. Ясно, что по каждому подмножеству X однозначно строится паспорт, но верно и обратное: каждый паспорт однозначно определяет множество X. В частности, паспорт из нулей соответствует пустому множеству, а паспорт из единиц - В этом паспорте в к-й клетке стоит 1, если а к Є Х, 0 – если а к Є X. Ясно, что по каждому подмножеству X однозначно строится паспорт, но верно и обратное: каждый паспорт однозначно определяет множество X. В частности, паспорт из нулей соответствует пустому множеству, а паспорт из единиц - множеству А. множеству А. Но число таких паспортов по правилу произведения равно 2, т.к. каждая клетка может быть заполнена двумя способами независимо от того, как заполняются другие клетки. Но число таких паспортов по правилу произведения равно 2, т.к. каждая клетка может быть заполнена двумя способами независимо от того, как заполняются другие клетки. Ответ: 2. Ответ: … 1 1

§ 2. Размещения и перестановки § 2. Размещения и перестановки

Определение. Всякая упорядоченная выборка объема k из множества, состоящего из n элементов, называется размещением из n элементов по k элементов и обозначается через А n. Определение. Всякая упорядоченная выборка объема k из множества, состоящего из n элементов, называется размещением из n элементов по k элементов и обозначается через А n.

Определение. Размещение из n элементов по n называется перестановкой из n элементов и обозначается через Р n. Определение. Размещение из n элементов по n называется перестановкой из n элементов и обозначается через Р n.

Справедлива формула Справедлива формула А n =n (n-1)...(n - к + 1) А n =n (n-1)...(n - к + 1) где 1 к n.

На первое место в выборке можно поместить любой из n элементов, на второе - любой из (n - 1) оставшихся и т.д. После выбора элементов на(k-1)-е место останется n-(к- 1) = n-к+1 элемен- На первое место в выборке можно поместить любой из n элементов, на второе - любой из (n - 1) оставшихся и т.д. После выбора элементов на(k-1)-е место останется n-(к- 1) = n-к+1 элемен- 1 2 k-1 k 1 2 k-1 k тов, любой из которых можно поместить на к- е место. По правилу произведения получаем тов, любой из которых можно поместить на к- е место. По правилу произведения получаем А n = (n-1)...(n - к + 1) А n = (n-1)...(n - к + 1) В частности, В частности, Р n =A n =n(n-1)… ·2·1 = n!(2) Р n =A n =n(n-1)… ·2·1 = n!(2) …

A n = n(n - 1)...(n - k+1)·(n-k)!= n! (n-к)! (n-к)! (n-к)! (n-к)!

P n =A n P n-k P n =A n P n-k

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

Последней цифрой искомого числа может быть 0 или 5. В первом случае остальные пять цифр можно выбирать из множества {1,2,..., 9} Последней цифрой искомого числа может быть 0 или 5. В первом случае остальные пять цифр можно выбирать из множества {1,2,..., 9} 9! 9! и число вариантов равно А 9 = = Если число и число вариантов равно А 9 = = Если число 4! 4! oканчивается цифрой 5, то в качестве первой цифры можно взять любую из восьми цифр 1, 2, 3, 4, 6, 7, 8, 9 - нельзя использовать 0, т.к. число должно быть шестизначным. Цифры со второй по четвертую можно выбрать oканчивается цифрой 5, то в качестве первой цифры можно взять любую из восьми цифр 1, 2, 3, 4, 6, 7, 8, 9 - нельзя использовать 0, т.к. число должно быть шестизначным. Цифры со второй по четвертую можно выбрать A 8 = 1680 различными способами. Следовательно, по правилу произведения имеется 8·A 8 чисел, оканчивающихся цифрой 5. По правилу суммы находим, сколько существует чисел, удовлетворяющих условию задачи. A 8 = 1680 различными способами. Следовательно, по правилу произведения имеется 8·A 8 чисел, оканчивающихся цифрой 5. По правилу суммы находим, сколько существует чисел, удовлетворяющих условию задачи. А 9 +8·A 8 = А 9 +8·A 8 = Ответ: Ответ:

Пример 10. Сколькими способами можно расставить на книжной полке десятитомник Пушкина так, чтобы том 2 стоял рядом с томом 1 и справа от него? Пример 10. Сколькими способами можно расставить на книжной полке десятитомник Пушкина так, чтобы том 2 стоял рядом с томом 1 и справа от него? Ответ: 9! Ответ: 9!

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

Определение. Всякая неупорядоченная выборка объема к из множества, состоящего из n элементов (кn), называется сочетанием из n элементов по к элементов и обозначается через С n. Определение. Всякая неупорядоченная выборка объема к из множества, состоящего из n элементов (кn), называется сочетанием из n элементов по к элементов и обозначается через С n.

Из любого набора,содержащего к элементов, можно с помощью перестановок получить k! упорядоченных выборок объема k, поэтому Из любого набора,содержащего к элементов, можно с помощью перестановок получить k! упорядоченных выборок объема k, поэтому Откуда (4) (4)

Пример 11. Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, двух защитников и трех нападающих? Пример 11. Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, двух защитников и трех нападающих?

Вратаря можно выбрать способами, защитников - Вратаря можно выбрать способами, защитников - способом, нападающих – способом, нападающих – способами. Всего, по правилу произведения, существует 2 · 21 · 120 = 5040 способов выбора стартовой шестерки. способами. Всего, по правилу произведения, существует 2 · 21 · 120 = 5040 способов выбора стартовой шестерки. Ответ: Ответ: 5040.

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

Число точек пересечения прямых равно числу способов выбора Число точек пересечения прямых равно числу способов выбора неупорядоченной пары прямых, т.е.. Аналогично, каждый треугольник определяется тройкой прямых, поэтому общее число треугольников равно. неупорядоченной пары прямых, т.е.. Аналогично, каждый треугольник определяется тройкой прямых, поэтому общее число треугольников равно. Ответ: и. Ответ: и.

Пример 13. Для проведения письменного экзамена по комбинаторике надо составить 4 варианта по 7 задач в каждом. Сколькими способами можно разбить 28 задач на 4 варианта? Пример 13. Для проведения письменного экзамена по комбинаторике надо составить 4 варианта по 7 задач в каждом. Сколькими способами можно разбить 28 задач на 4 варианта?

Задачи для первого варианта можно выбрать способами. После этого останется 21 задача, так что второй вариант можно составить способами. Для третьего варианта задачи можно выбрать способами, а для четвертого - = 1 способом. Задачи для первого варианта можно выбрать способами. После этого останется 21 задача, так что второй вариант можно составить способами. Для третьего варианта задачи можно выбрать способами, а для четвертого - = 1 способом.

По правилу произведения получаем число. Но так как варианты равноправны, то полученное число надо разделить на 4! По правилу произведения получаем число. Но так как варианты равноправны, то полученное число надо разделить на 4! Ответ: = Ответ: =

Свойства чисел : Свойства чисел : 1°., если 0кn; 1°., если 0кn; 2°., если 0кn+1; 2°., если 0кn+1; 3°. 3°.

Свойство 1° Свойство 1°

Свойство 2° Свойство 2°

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

Свойство 3° Свойство 3° Положим Положим Так как каждое число строки с номером п входит в качестве слагаемого в два соседних числа следующей строки, то Так как каждое число строки с номером п входит в качестве слагаемого в два соседних числа следующей строки, то S n+1 = 2S n. S n+1 = 2S n. Следовательно, т.к. S 0 =1. Следовательно, т.к. S 0 =1.

§ 4. Бином Ньютона

(a + b) =a +2ab + b и (a + b) = а +3а b + 3ab +b. (a + b) =a +2ab + b и (a + b) = а +3а b + 3ab +b.

Доказательство. Если, не приводя подобные члены, перемножить n скобок (а + b), то получится сумма, состоящая из слагаемых вида a b, k=0,1,…,n. Для данного k слагаемое a b получается только в том случае, если в каких-то к скобках мы возьмем b, a остальных (n - k) скобках - a. Следовательно, число слагаемых вида a b будет равно числу способов, которыми можно выбрать (без учета порядка выбора) k скобок из n скобок, т.е.. Утверждение доказано. Доказательство. Если, не приводя подобные члены, перемножить n скобок (а + b), то получится сумма, состоящая из слагаемых вида a b, k=0,1,…,n. Для данного k слагаемое a b получается только в том случае, если в каких-то к скобках мы возьмем b, a остальных (n - k) скобках - a. Следовательно, число слагаемых вида a b будет равно числу способов, которыми можно выбрать (без учета порядка выбора) k скобок из n скобок, т.е.. Утверждение доказано.

Если в формуле (5) взять а =b = 1, то получится известное нам свойство 3° чисел, а если взять а=1, b = -1, то получим еще одно комбинаторное равенство: Если в формуле (5) взять а =b = 1, то получится известное нам свойство 3° чисел, а если взять а=1, b = -1, то получим еще одно комбинаторное равенство:

Формула (6) называется полиномиальной. Например, Формула (6) называется полиномиальной. Например, (а + b + с) = а + b + с + 3(а b + а с + b а + b с + с а + c b ) + 6abc. (а + b + с) = а + b + с + 3(а b + а с + b а + b с + с а + c b ) + 6abc.

Пример 14. Найти n, если известно, что в разложении (1 + x) Пример 14. Найти n, если известно, что в разложении (1 + x) коэффициенты при х и х равны. коэффициенты при х и х равны.

В n-й строке треугольника Паскаля два коэффициента равны в том и только том случае, когда они занимают клетки, равноудаленные от крайних. Действительно, треугольник Паскаля симметричен:, а при движении от края к середине строки коэффициенты возрастают: при В n-й строке треугольника Паскаля два коэффициента равны в том и только том случае, когда они занимают клетки, равноудаленные от крайних. Действительно, треугольник Паскаля симметричен:, а при движении от края к середине строки коэффициенты возрастают: при и при и при

Следовательно, равно тогда и только тогда, когда 12 = n-5, т.е. n= 17. Следовательно, равно тогда и только тогда, когда 12 = n-5, т.е. n= 17. Ответ: n = 17. Ответ: n = 17.

Пример 15. Найти коэффициент при х в разложении Пример 15. Найти коэффициент при х в разложении (1 + х +х ). (1 + х +х ).

В силу формулы (6) В силу формулы (6) = Так как уравнение 5k 2 + 9к 3 =19 имеет только одно решение в неотрицательных числах k 2 =2, k 3 = 1, то коэффициент при х равен Так как уравнение 5k 2 + 9к 3 =19 имеет только одно решение в неотрицательных числах k 2 =2, k 3 = 1, то коэффициент при х равен

2) Обозначим через. Тогда 2) Обозначим через. Тогда Рассмотрим k-е слагаемое (0k30): Рассмотрим k-е слагаемое (0k30): Такое слагаемое будет содержать х, если для некоторого т выполняется равенство 5k + 4m = 19. Ясно, что это возможно только при k=3 и т=1. Следовательно, коэффициент при х равен = Такое слагаемое будет содержать х, если для некоторого т выполняется равенство 5k + 4m = 19. Ясно, что это возможно только при k=3 и т=1. Следовательно, коэффициент при х равен =12180.

Литература Литература 1.Кутасова А.Д., Пиголкина Т.С, Чехлов В.И., Яковлева Т.Х., Пособие по математике для поступающих в вузы. /под ред. Г.Н. Яковлева - M.: Наука, Кутасова А.Д., Пиголкина Т.С, Чехлов В.И., Яковлева Т.Х., Пособие по математике для поступающих в вузы. /под ред. Г.Н. Яковлева - M.: Наука, Виленкин Н.Я. Популярная комбинаторика. М.: Наука, Виленкин Н.Я. Популярная комбинаторика. М.: Наука, Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. Киров, Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. Киров, 1994.

Контрольные вопросы Контрольные вопросы Сколько делителей у числа 2004 ? Сколько делителей у числа 2004 ? Сколько диагоналей в выпуклом угольнике? Сколько диагоналей в выпуклом угольнике? Сколько различных натуральных решений имеет неравенство Сколько различных натуральных решений имеет неравенство n+m2004? n+m2004? 4.Чему равен коэффициент при х y в выражении (х + у) 4.Чему равен коэффициент при х y в выражении (х + у) после раскрытия скобок? после раскрытия скобок? 5.С помощью соответствующей строки треугольника Паскаля выпишите формулу для вычисления (а-b). 5.С помощью соответствующей строки треугольника Паскаля выпишите формулу для вычисления (а-b).

Задачи Задачи 1(3). Сколько различных слов можно получить, переставляя буквы в слове «параллелограмм»? 1(3). Сколько различных слов можно получить, переставляя буквы в слове «параллелограмм»? 2(4). Сколькими способами можно переставлять буквы слова «раз-­ мещение» так, чтобы три буквы «е» не шли подряд? 2(4). Сколькими способами можно переставлять буквы слова «раз-­ мещение» так, чтобы три буквы «е» не шли подряд? 3(3). Решите уравнение 3(3). Решите уравнение 4(3). Известно, что никакие три диагонали выпуклого восьмиуголь­ника не пересекаются в одной точке. Найдите число точек пе­ресечения диагоналей. 4(3). Известно, что никакие три диагонали выпуклого восьмиуголь­ника не пересекаются в одной точке. Найдите число точек пе­ресечения диагоналей. 5(4). Сколькими способами можно поставить на шахматную доску белого и черного слонов так, чтобы они не били друг друга? 5(4). Сколькими способами можно поставить на шахматную доску белого и черного слонов так, чтобы они не били друг друга? 6(5). Найдите сумму всех трехзначных чисел, которые можно напи­сать с помощью цифр 1, 2, 3, 4, 5 (любую из цифр можно ис­пользовать несколько раз). 6(5). Найдите сумму всех трехзначных чисел, которые можно напи­сать с помощью цифр 1, 2, 3, 4, 5 (любую из цифр можно ис­пользовать несколько раз). 7(5). Докажите тождество 7(5). Докажите тождество 8(6).Сколькими способами можно распределить 12 различных книг по четырем полкам так, чтобы на каждой полке ока­залась ровно три книги? 8(6).Сколькими способами можно распределить 12 различных книг по четырем полкам так, чтобы на каждой полке ока­залась ровно три книги? 9(6). Сколькими способами можно распределить 12 одинако­вых книг по четырем полкам так, чтобы на каждой полке была хотя бы одна книга? 9(6). Сколькими способами можно распределить 12 одинако­вых книг по четырем полкам так, чтобы на каждой полке была хотя бы одна книга? В задачах 8 и 9 все полки разные. В задачах 8 и 9 все полки разные. 10(6). В выпуклом восьмиугольнике проведены все диагона­ли, причем известно, что никакие три диагонали не пере­секаются в одной точке. На сколько частей разделится восьмиугольник? 10(6). В выпуклом восьмиугольнике проведены все диагона­ли, причем известно, что никакие три диагонали не пере­секаются в одной точке. На сколько частей разделится восьмиугольник? 11(6). Найдите наибольший коэффициент многочлена (1 + 2х). 11(6). Найдите наибольший коэффициент многочлена (1 + 2х). 12(6). Найдите коэффициент при х в разложении по степе ням х 12(6). Найдите коэффициент при х в разложении по степе ням х 1+(1+x)+…+(1+x). 1+(1+x)+…+(1+x).