Количество способов, исходов, слагаемых

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

Попробуем понять, какие числа представляются в таком виде, а какие — нет. Если рассмотреть числа от до то с помощью небольшого перебора мы понимаем, что все, кроме и представимы в нужном виде.

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

Число мы можем получить, если взять четвёрок и троек. Числа и мы получить не сможем, потому что вычитая из мы получаем не больше, чем Число мы получаем из четвёрок и троек. Число мы получим из четвёрок и троек. Число мы не получим, потому что нельзя убрать из сколько-то четвёрок или троек, чтобы число уменьшилось на Число мы наберём из четвёрок и троек. Числа и из четвёрок, троек и четвёрок, троек. из четвёрок и троек, из четвёрок и троек. Число — из четвёрок и троек, — из четвёрок и троек.

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

Раскладываем пароль "по слоям": цифра + заглавная + строчная и смотрим, какие ограничения есть по замене в каждой позиции. Цифр две, поэтому одну из них можно заменить произвольно на любой знак из . Если менять заглавную T, то только на заглавную: вариантов. Строчные можно на любые, это ещё вариантов. Итого вариантов.

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

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

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

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

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

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

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

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

Число способов рассадки, когда Андрей и Боря сидят рядом, равно (достаточно объединить их в одного человека двумя способами). Способов рассадки, при которых и Андрей-Боря, и Вася-Гриша окажутся рядом, равно Поэтому они могут сесть способами.

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

Заметим, если наше слово заканчивается на то перед стоит Пусть нужных нам слов длины — Чтобы получить нужное нам слово длины мы или к любому слову длины добавим в конце (таким образом получим все возможные слова с окончанием ), или к любому слову длины добавим в конце (таким образом получим все возможные слова с окончанием ). Получается, что значит, равно девятому числу Фибоначчи, что равно

Заметим, что НЕ отмеченных точек у нас отмеченные точки мы можем ставить во все промежутков между ними и ещё в места по краям, значит всего нужно выбрать вариантов из

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

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

Таким образом, разбиение чисел на пары из условия задачи однозначно определяет правильную скобочную последовательность, поэтому построенное отображение инъективно. При этом, нетрудно видеть, что оно и сюръективно: данную правильную скобочную последовательность разобьем на пары открывающих/закрывающих скобок, и соответственно разобьем числа от до на пары. Если при таком построении нарушилось условие задачи, то существует набор чисел такой, что в разбиение одновременно входят пары и но тогда подпоследовательность скобок с номерами не является правильной, что противоречит построению. Биективность доказана.

Переведем задачу на язык последовательностей: необходимо найти число последовательностей натуральных чисел где В одной из предыдущих задач мы поняли, что числа Каталана можно представить путями из в по линиям сетки, и не переступающими за Ясно, что если имеется подобный путь, и для каждого значения по от до мы выделим наибольшее значение по лежащее на пути до момента включительно, и прибавим к нему единицу, то мы получим последовательность из нашего условия. Разумеется, она будет неубывающей, и ее -ый элемент не будет превосходить И наоборот, по последовательности можно построить путь по решетке из в не пересекающий Его первый шаг всегда направо, а дальше для от 2 до сделаем последовательность из шага наверх и одного шага вправо. Из свойства последовательности, на своем пути мы ни разу не пересекли Ясно, что в конце мы находимся в точке с координатой по оси ниже прямой  – остается сделать необходимое число шагов, чтобы попасть в точку

Нетрудно видеть, что построенные отображения являются взаимно обратными. Значит, у нас есть биекция между двумя множествами объектов, откуда их размеры равны. Поэтому искомое количество способов из условия задачи равно

Скажем, что самый высокий школьник имеет номер следующий по росту — и так далее. Мы хотим расставить числа от до в таблицу так, чтобы в каждой ячейке число было больше, чем в ячейке выше и в ячейке левее неё. Давайте, вновь, рассмотрим пути Дика (пути по линиям сетки, не поднимающиеся выше ) из в Построим отображение, сопоставляющее пути Дика расстановку чисел в таблице: если в пути мы идём направо, то запишем номер хода в первую строку, а если вверх, то в нижнюю строку. Условие того, что каждое число больше, чем сосед слева, выполнено по построению, а условие того, что каждое число во второй строке больше, чем сосед сверху, равносильно тому, что в любой момент времени число шагов вверх не превосходит число шагов направо. Поэтому отображение возвращает правильную расстановку чисел в таблице, а обратное отображение возвращает путь Дика. Поскольку между множествами путей Дика и расстановок чисел в таблице существует биекция, их мощности совпадают, и ответом является

Давайте для начала в качестве леммы посмотрим на такую задачу, а потом решим исходную задачу.

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

Доказательство. Скажем, что самый высокий школьник имеет номер следующий по росту — и так далее. Мы хотим расставить числа от до в таблицу так, чтобы в каждой ячейке число было больше, чем в ячейке выше и в ячейке левее неё. Давайте, вновь, рассмотрим пути Дика (пути по линиям сетки, не поднимающиеся выше ) из в Построим отображение, сопоставляющее пути Дика расстановку чисел в таблице: если в пути мы идём направо, то запишем номер хода в первую строку, а если вверх, то в нижнюю строку. Условие того, что каждое число больше, чем сосед слева, выполнено по построению, а условие того, что каждое число во второй строке больше, чем сосед сверху, равносильно тому, что в любой момент времени число шагов вверх не превосходит число шагов направо. Поэтому отображение возвращает правильную расстановку чисел в таблице, а обратное отображение возвращает путь Дика. Поскольку между множествами путей Дика и расстановок чисел в таблице существует биекция, их мощности совпадают, и ответом является

______________________________________________________________________________________________________________________________________________________

Посмотрим теперь на таблицу из леммы. Покажем как из такой таблицы получить расстановки учеников Анатолия и Василия. Вычеркнув из нее числа от до получим первую “таблицу” — расстановку учеников Анатолия. Если вычеркнуть, наоборот, числа от до повернуть “таблицу” на и заменить каждое число на то получим вторую “таблицу” — расстановку учеников Виталия. Ясно, что такое отображение биективно, поскольку очевидно как построить к нему обратное. Количество расстановок, тем самым, равно

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

Замечание. Поиск в глубину по корневому дереву осуществляется следующим образом: мы идём каждый раз влево-вниз, пока не придём в лист, затем поднимаемся до ближайшей вершины с более чем одним потомком, «отрезаем» рёбра и вершины, по которым мы прошли дважды, и вновь идём всегда влево-вниз до листа, после чего повторяем алгоритм, пока не сотрём весь граф.

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

Найдём сначала количество троек натуральных чисел. Пусть

где — целые неотрицательные числа. Тогда получаем

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

Из полученных уравнений получаем систему

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

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

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

а) Каждый день есть вариантов, кто пойдет дежурить, поэтому вариантов на дней ровно .

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

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

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

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

е) Если Василий дежурит в первый день, то Юрий может дежурит только в - день. Для следующего человека останется дня и варианта, для четвертого дня, а для последнего останется последний день. Итого: .

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

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

Итого:

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

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

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

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

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

Рассмотрим как могут выглядеть квадратики .

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

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