Числа сочетаний (цэ изэн пока)

Предположим, что для упорядоченной четвёрки верно, что тогда

И наоборот, если то

То есть, упорядоченные четвёрки с условием находятся во взаимно-однозначном соответствии с упорядоченными четвёрками с условием Посчитаем количество четвёрок со свойством Заметим, что является целым числом из промежутка Для каждого числа из этого диапазона посчитаем количество разбиений числа в сумму двух различных натуральных слагаемых, меньших Тогда всего таких четвёрок будет

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

Наша задача эквивалентна тому, чтобы найти число способов расставить три одинаковые фигуры на одной линии (диагонали, горизонтали, вертикали) и одну не на этой линии или расставить одинаковые фигуры на одной линии. Всего у нас различных линий. Число способов расставить фигуры на одну линию равно Тогда итоговый ответ равен

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

Первое решение.

Выложим в ряд орехи и грибы — сделать это можно способами. Далее рассмотрим позиции между выложенными орехами и грибами и по краям от них — получим 14 мест для ягод. Остаётся выложить их туда способами.

Второе решение.

Сначала объединим орехи и грибы в неягоды, откуда получим 13 неягод и 11 ягод. Далее назовём нейтроном пару (неягода, ягода).

Если на крайней левой позиции в ряду лежит неягода, то 11 ягод образуют нейтроны, поскольку рядом с ними не могут находиться другие ягоды, и левее каждой точно есть неягода. Отсюда имеем 11 нейтронов и 2 дополнительные неягоды. В итоге получаем способов поставить эту неягоду, то есть 78 расстановок.

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

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

Если среди чисел есть ноль, то задача тривиальна. В противном случае можно считать, что последовательные числа положительные, потому что знак тут роли не играет. Рассмотрим число сочетаний для натурального и неотрицательного целого Как известно, при любых и оно целое. Распишем его: Заметим, что в числителе находится произведение последовательных чисел, а в знаменателе — то есть мы получили требуемое.

Чем задается прямоугольник на доске? Четырьмя сторонами, идущими по границам клеток: верхней, нижней, правой и левой. Сколько способов выбрать нижнюю и верхнюю стороны? Столько же, сколько выбрать две горизонтальные линии, идущие по границе клеток, из 11 линий (так как 10 горизонтальных полосок из клеток, у которых всего 11 горизонтальных линий сетки), а это . Аналогично, способов выбрать левую и правую границу. Границы выбираем независимо, поэтому ответ . .

Первое решение.

Три точки из данных можно выбрать способами.

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

Значит, всего есть треугольник.

Второе решение.

Выбрать по одной точке на каждой стороне можно способами.

Выбрать две точки на одной стороне и одну точку на другой можно способами.

Значит, всего есть треугольник.

Множество всех последовательностей длины состоит из последовательностей. Это множество разбивается на три непересекающихся между собой подмножества:

1.

Последовательностей, не содержащих

2.

Последовательностей, содержащих но не содержащих двух подряд идущих таких букв.

3.

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

Чтобы решить задачу, нужно найти число последовательностей во втором подмножестве и вычесть его из числа

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

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

В итоге получаем

Будем следить за центром квадрата. При выборе меньшего квадрата две его границы остаются на месте, две — смещаются на одну клетку. Следовательно, центр смещается на полклетки влево-вверх, влево-вниз, вправо-вверх или вправо-вниз. За операций центр должен вернуться в исходное положение, поэтому сделает по передвижений влево и вправо ( способов) и по столько же перемещений вверх и вниз. Так как мы должны скомбинировать все подходящие способы передвигать квадрат по вертикали и по горизонтали, ответом будет

Давайте для начала докажем вспомогательную лемму: произведение подряд идущих чисел делится на

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

Но количество способов - целое число, поэтому числитель делится на знаменатель. Лемма доказана.

Так как то можно представить в виде произведения подряд идущих чисел на следующих чисел на последних чисел:

Произведение подряд идущих чисел делится на поэтому делится на произведение факториалов

Заметим, что всего существует различных комбинаций из трёх друзей. Значит, каждая из этих троек в какой-то день была приглашена. Таким образом, искомое количество способов равно количеству способов переставить двадцать троек, то есть

Разложим на множители. Значит, либо в нашем числе есть пятерки, тройки и остальные единицы, либо в нашем числе есть пятерки, девятка, тройка и остальные единицы.

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

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

Итого вариантов.

Разложим на множители. Значит, искомые числа могут состоять из следующих цифр:

1) три двойки, две пятёрки, одна семёрка и две единицы,

2) четвёрка, двойка, две пятёрки, одна семёрка и три единицы,

3) восьмёрка, две пятёрки, одна семёрка и четыре единицы.

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

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

В третьем случае выбрать места для единиц можно способами, далее для двух пятёрок способа, оставшиеся восьмёрку и семёрку ставим двумя способами. Всего получается вариантов.

Итого вариантов.

Первое решение.

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

Давайте подумаем, какие есть варианты для остатков трёх карточек, чтобы их сумма делилась на либо все три числа должны давать разные остатки (способов выбрать так карточки так как выбрать карточку с остатком — способа, способов выбрать карточку с остатком — и способов выбрать карточку с остатком — ), либо все три остатка (тогда способов либо все три остатка 1 (тогда способов либо все три остатка (тогда способов Итого всего

Второе решение.

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

Среди данных нам чисел есть дающие остаток от деления на (они образуют множество ), числа, делящихся на (образуют ) и числа, дающих остаток от деления на ().

Сумма трёх чисел может делиться на в следующих случаях.

1.

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

2.

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

В сумме выходит способов.

Первое решение.

Пронумеруем вершины, начиная с произвольной. Заметим, что диагональ параллельна какой-то стороне тогда и только тогда, когда номера вершин в ней имеют разную чётность. Действительно, из второго очевидно следует первое, достаточно рассмотреть операцию “сдвинем одну вершину по часовой, а другую — против”, такими операциями мы будем получать параллельные отрезки и попадём в сторону (при такой операции чётность не меняется и в итоге приходим к соседним вершинам, которые имеют разную чётность). Из этой же операции получаем следствие в обратную сторону, поскольку такие операции сходятся в точку.

Нам нужно найти число непараллельных сторонам диагоналей. Так что задача сводится к поиску числа пар вершин одинаковой чётности. Число способов выбрать две вершины с чётными номерами аналогично с нечётными. Получаем всего диагоналей.

Второе решение.

Всего в -угольнике

диагоналей. Разобьем стороны на пар параллельных сторон. Несложно заметить, что если зафиксировать какую-то пару ( вершины), то оставшиеся вершины можно соединить попарно диагоналями, параллельными этой паре. Их всего будет Значит, диагоналей, параллельных какой-то стороне А непараллельных

Треугольник образуют любые три проведённые отрезка (с учётом сторон, то есть из 36 возможных), если они не исходят из одной и той же вершины Вычитая тройки отрезков от каждой вершины из всевозможных троек отрезков, получаем

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

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

Действительно, сначала рассмотрим все перестановки из человек (которых ), будем брать в команду первых из них. Тогда нам не важен порядок этих человек, то есть нужно поделить на , а также не важен порядок следующих за ними человек, то есть нужно поделить ещё на . Что здесь означает не важен порядок? Если мы его изменим, то выбранная нами команда не поменяется.

В итоге мы показали, что способов Используя эту формулу для всех типов игроков и перемножая результаты, получаем

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

Всего есть треугольников. Каждой вершине соответствует равнобедренных треугольников(с вершиной в этой точке). При этом, если взять , то получится, что каждый равносторонний треугольник мы посчитали раза. Значит, равнобедренных треугольников , а неравнобедренных —