Основы комбинаторики

каждого выбора объекта а1 объект а2 можно выбрать n2 различными

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

клеток следующей таблицы:

1 2

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

«е», «ч», «н», «о», «с», «т», «ь»?
Пусть ак - к

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

и черную ладью так, чтобы они не били друг друга?

быть сделан n1 = 64 способами. Независимо от выбора этого

поля белая ладья бьет 15 полей, поэтому для черной ладьи остается 64-15 =49 полей: n2 = 49.
Ответ: число расстановок ладей равно 64 · 49 = 3136.

«комбинаторика»?

различны, то, переставляя их, можно было бы получить 13! слов.

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

нечетные? Сколько существует четырехзначных чисел, в записи которых есть хотя

бы одна четная цифра?

может быть сделан nк =5 способами (к =1, 2, 3,

4) а количество четырехзначных чисел, у которых все цифры нечетные, равно 5·5·5·5 = 625.

различными способами, а объект b можно выбрать

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

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

друг к другу?

a2b2,
где можно считать, что а ≤ b.
Выберем первую кость -

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

n элементов, называется размещением из n элементов по k элементов

и обозначается через Аn .

k

n элементов и обозначается через Рn .

Аn =n (n-1)...(n - к + 1)
k
где 1 ≤

к ≤ n.

элементов, на второе - любой из (n - 1) оставшихся

и т.д. После выбора элементов на(k-1)-е место останется n-(к-1) = n-к+1 элемен-

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

n

k

(n-к)! (n-к)!

k

цифр 0, 1,2, ..., 9 при условии, что цифры в

записи числа не повторяются?

первом случае остальные пять цифр можно выбирать из множества {1,2,

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

5

4

4

5

4

Пушкина так, чтобы том 2 стоял рядом с томом 1

и справа от него?
Ответ: 9!

n элементов (к≤n), называется сочетанием из n элементов по к

элементов и обозначается через Сn .

k

k! упорядоченных выборок объема k, поэтому

Откуда

(4)

и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку,

состоящую из вратаря, двух защитников и трех нападающих?

защитников -
способом, нападающих –

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

ни одной пары параллельных прямых и ни одной тройки прямых,

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

пары прямых, т.е. . Аналогично, каждый треугольник определяется

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

экзамена по комбинаторике надо составить 4 варианта по 7

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

После этого останется 21 задача, так что второй вариант можно

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

. Но так как варианты

равноправны, то полученное число надо разделить на 4!
Ответ: =

, если 0≤к≤n;
2°.

, если 0≤к≤n+1;
3°.

с номером п входит в качестве слагаемого в два соседних

числа следующей строки, то
Sn+1 = 2Sn .
Следовательно, т.к. S0=1.

и (a + b) = а +3а

b + 3ab +b .

получится известное нам свойство 3° чисел , а если

взять а=1, b = -1, то получим еще одно комбинаторное равенство:

= а + b + с + 3(а b +

а с + b а + b с + с а + c b ) + 6abc.

(1 + x)
коэффициенты при х и х

равны.

и только том случае, когда они занимают клетки, равноудаленные от

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

12 = n-5, т.е. n= 17.
Ответ: n = 17.

(1 +

х +х ) .

=
Так как уравнение 5k2 + 9к3

=19 имеет только одно решение в неотрицательных числах k2=2, k3 = 1, то коэффициент при х равен

. Тогда

Рассмотрим

k-е слагаемое (0≤k≤30):

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

для поступающих в вузы. /под ред. Г.Н. Яковлева - M.: Наука,

1988.
2. Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.
3. Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. — Киров, 1994.

выпуклом 2004-угольнике?
Сколько различных натуральных решений имеет неравенство
n+m≤2004?
4. Чему равен

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

«параллелограмм»?
2(4). Сколькими способами можно переставлять буквы слова «раз-­

мещение» так, чтобы три буквы «е» не шли подряд?
3(3). Решите уравнение

4(3). Известно, что никакие три диагонали выпуклого восьмиуголь­ника не пересекаются в одной точке. Найдите число точек пе­ресечения диагоналей.
5(4). Сколькими способами можно поставить на шахматную доску белого и черного слонов так, чтобы они не били друг друга?
6(5). Найдите сумму всех трехзначных чисел, которые можно напи­сать с помощью цифр 1, 2, 3, 4, 5 (любую из цифр можно ис­пользовать несколько раз).
7(5). Докажите тождество


8(6).Сколькими способами можно распределить 12 различных книг по четырем полкам так, чтобы на каждой полке ока­залась ровно три книги?
9(6). Сколькими способами можно распределить 12 одинако­вых книг по четырем полкам так, чтобы на каждой полке была хотя бы одна книга?
В задачах №8 и №9 все полки разные.
10(6). В выпуклом восьмиугольнике проведены все диагона­ли, причем известно, что никакие три диагонали не пере­секаются в одной точке. На сколько частей разделится восьмиугольник?
11(6). Найдите наибольший коэффициент многочлена (1 + 2х) .
12(6). Найдите коэффициент при х в разложении по степе ням х
1+(1+x)+…+(1+x) .