Задачи по комбинаторике - задачи с решениями

Решение:
Каждый из пяти учеников попадает ровно в один из трёх классов независимо от остальных, а распределение полностью определяется тем, в какой класс попал каждый ученик. По правилу произведения число распределений равно
[tex]3\cdot 3\cdot 3\cdot 3\cdot 3=3^5=243[/tex]

Решение:
Порядок игроков внутри каждой группы не важен, поэтому считаем сочетания. Число способов выбрать вратаря, двух защитников и трёх нападающих равно соответственно
[tex]\binom{2}{1}=2,\qquad \binom{6}{2}=15,\qquad \binom{8}{3}=56[/tex]
Эти выборы независимы, поэтому по правилу произведения число составов равно
[tex]2\cdot 15\cdot 56=1680[/tex]

Решение:
Цифра [tex]0[/tex] встречаться не может: она была бы наименьшей и должна была бы стоять на первом месте, что невозможно для семизначного числа. Значит, все цифры берутся из [tex]1,2,\dots,9[/tex].
Обратно, любой выбор [tex]7[/tex] различных цифр из [tex]1,2,\dots,9[/tex] даёт ровно одно такое число — выбранные цифры, записанные в порядке возрастания. Поэтому искомое количество равно числу способов выбрать [tex]7[/tex] цифр из [tex]9[/tex]:
[tex]\binom{9}{7}=\binom{9}{2}=\frac{9\cdot 8}{2}=36[/tex]

Решение:
Рассмотрим случаи в зависимости от позиции единственной цифры [tex]3[/tex]. Если это цифра сотен, то цифры десятков и единиц — любые из [tex]9[/tex] цифр, отличных от [tex]3[/tex]:
[tex]9\cdot 9=81[/tex]
Если это цифра десятков, то цифра сотен не может быть [tex]0[/tex] или [tex]3[/tex] ([tex]8[/tex] вариантов), а цифра единиц — любая, кроме [tex]3[/tex] ([tex]9[/tex] вариантов):
[tex]8\cdot 9=72[/tex]
Если это цифра единиц, аналогично получаем
[tex]8\cdot 9=72[/tex]
Случаи не пересекаются, поэтому количество таких чисел равно
[tex]81+72+72=225[/tex]

Решение:
В слове [tex]10[/tex] букв: М встречается [tex]2[/tex] раза, А — [tex]3[/tex] раза, Т — [tex]2[/tex] раза, а Е, И и К — по одному разу. Если бы все десять букв были различны, их можно было бы переставить [tex]10![/tex] способами.
Перестановка одинаковых букв между собой не меняет слово, поэтому каждое слово учтено среди этих перестановок ровно [tex]2!\cdot 3!\cdot 2!=24[/tex] раза. Следовательно, число различных слов равно
[tex]\frac{10!}{2!\cdot 3!\cdot 2!}=\frac{3628800}{24}=151200[/tex]

Решение:
Три точки являются вершинами треугольника тогда и только тогда, когда они не лежат на одной прямой. Поэтому все три вершины не могут лежать на одной из данных прямых, т.е. у треугольника две вершины на одной прямой и одна вершина на другой. Обратно, любая такая тройка точек даёт треугольник, так как третья точка не лежит на прямой, проходящей через две другие (прямые параллельны и различны).
Две вершины на прямой с [tex]10[/tex] точками и одна на другой прямой:
[tex]\binom{10}{2}\cdot 20=45\cdot 20=900[/tex]
Две вершины на прямой с [tex]20[/tex] точками и одна на другой прямой:
[tex]\binom{20}{2}\cdot 10=190\cdot 10=1900[/tex]
Эти случаи не пересекаются, поэтому общее число треугольников равно
[tex]900+1900=2800[/tex]

Решение:
Важно, кто в какой город едет, поэтому считаем упорядоченные тройки различных сотрудников, выбранных из всех [tex]9[/tex] (размещения). Без ограничений их число равно
[tex]9\cdot 8\cdot 7=504[/tex]
Недопустимы выборы без экономиста, т.е. когда все трое отправляемых — юристы:
[tex]5\cdot 4\cdot 3=60[/tex]
Любой другой выбор содержит хотя бы одного экономиста, поэтому искомое число равно
[tex]504-60=444[/tex]

Решение:
По формуле бинома Ньютона общий член разложения равен
[tex]T_{k+1}=\binom{7}{k}\left(2x^{4}\right)^{7-k}\left(\frac{1}{x^{3}}\right)^{k}=\binom{7}{k}\cdot 2^{7-k}\cdot x^{28-7k},\qquad k=0,1,\dots,7[/tex]
Член не содержит [tex]x[/tex] тогда и только тогда, когда [tex]28-7k=0[/tex], т.е. [tex]k=4[/tex]. Следовательно, свободный член равен
[tex]T_{5}=\binom{7}{4}\cdot 2^{3}=35\cdot 8=280[/tex]

Решение:
Выражений [tex]2^4=16[/tex], но разные выражения могут иметь равные значения, поэтому считаем непосредственно значения. Пусть [tex]S[/tex] — сумма чисел, перед которыми стоит знак минус. Тогда значение выражения равно
[tex](2+4+6+8)-2S=20-2S[/tex]
Значит, разным значениям [tex]S[/tex] соответствуют разные значения выражения, и наоборот. Запишем [tex]S=2T[/tex], где [tex]T[/tex] — сумма некоторых из чисел [tex]1; 2; 3; 4[/tex] (возможно, ни одного из них). Каждое целое число от [tex]0[/tex] до [tex]10[/tex] является такой суммой:
[tex]0; 1; 2; 3; 4; 5=1+4; 6=2+4; 7=3+4; 8=1+3+4; 9=2+3+4; 10=1+2+3+4[/tex]
Других значений нет, так как [tex]0\le T\le 10[/tex]. Следовательно, значение выражения [tex]20-4T[/tex] принимает ровно [tex]11[/tex] различных значений:
[tex]-20; -16; -12; \dots; 16; 20[/tex]

Решение:
Сначала расставим в ряд [tex]8[/tex] красных ручек; так как они одинаковые, это можно сделать единственным способом. Они образуют [tex]9[/tex] мест для синих ручек: [tex]7[/tex] промежутков между соседними красными ручками и [tex]2[/tex] места по краям.
Две синие ручки стоят рядом тогда и только тогда, когда они помещены в одно и то же место, поэтому синие ручки должны занять [tex]4[/tex] различных места из этих [tex]9[/tex]. Синие ручки одинаковые, поэтому важно лишь, какие места выбраны, и каждая допустимая расстановка получается ровно один раз:
[tex]\binom{9}{4}=\frac{9\cdot 8\cdot 7\cdot 6}{4!}=126[/tex]

Решение:
Фишка должна сместиться на [tex]7[/tex] столбцов вправо и на [tex]7[/tex] строк вверх. Каждый ход меняет на [tex]1[/tex] либо номер столбца, либо номер строки, поэтому нужно не менее [tex]14[/tex] ходов, и [tex]14[/tex] ходов достаточно.
Путь из [tex]14[/tex] ходов не может содержать ход влево или вниз: такой ход пришлось бы компенсировать дополнительным ходом вправо или вверх, и путь стал бы длиннее [tex]14[/tex] ходов.
Значит, кратчайшие пути — это в точности последовательности из [tex]7[/tex] ходов «вправо» и [tex]7[/tex] ходов «вверх» в некотором порядке (каждая из них не выходит за пределы доски). Такая последовательность определяется выбором того, какие [tex]7[/tex] из [tex]14[/tex] ходов — «вправо»:
[tex]\binom{14}{7}=3432[/tex]