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

Рекурренты в комбинаторике и числа Фибоначчи f(n)

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела количество способов, исходов, слагаемых

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#80741

Есть $4n$ отрезков длины $x 1$ , $x 2$ , …, $x 4n$ , где $x = 1 1$ , $x =2 2$ , а при $k> 2$ выполнено $x = x + x k k−1 k−2$ . Сколькими способами эти отрезки можно разбить на четвёрки так, чтобы из отрезков каждой четвёрки можно было составить четырёхугольник?

Источники: Высшая проба - 2024, 11.4 (см. olymp.hse.ru)

Показать ответ и решение

Из отрезков $a< b< c< d$ можно сложить четырехугольник тогда и только тогда, когда $a+ b+ c> d$ . Рассмотрим четверку $xs < xi < xj < xk$ , заметим, что $xk =xk−1+ xk−2 = 2xk−2 +xk−3 > xk−2+xk−3+ xk−4$ , следовательно, $xj = xk−1$ , иначе проверяемое неравенство не выполнено. Аналогично, можно показать, что $xi =xk−2$ .

Назовем последовательность $4n {xi}i=1$ интересной. Таким образом, необходимо посчитать количество способов выбрать в интересной последовательности $n$ пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной тройки.

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

Посчитаем количество хороших последовательностей. Существует $C22n$ способов выбрать индексы двум единичкам, после этого останется $2n− 2$ возможных индекса, следовательно, существует ровно $C22n−2$ способов выбрать индексы для двух двоек. Продолжая ставить каждому из чисел в соответствие два индекса, получим что общее количество способов сделать это, равно $(2n)!∕2n$ . Осталось заметить, что каждая перестановка чисел в хорошей последовательности не меняет набор разбиение интересной последовательности, следовательно, каждое разбиение было посчитано $n!$ раз (количество перестановок длины $n$ ), а значит общее количество разбиений равно

(2n)!= --(2n)!---= (2n− 1)!! 2nn! 2⋅4⋅...⋅2n

Ответ:

$(2n− 1)!!$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#102018

Дан прямоугольник $2×n.$ Сколькими способами его можно разрезать на доминошки, состоящие из $2$ клеток?

Показать ответ и решение

Обозначим за $A n$ количество способов разрезать прямоугольник $2× n$ на доминошки. Давайте по индукции докажем, что $A = F . n n+1$ Для $n= 1,2$ очевидно. Теперь переход. Посмотрим на левую верхнюю крайнею клетку прямоугольника $2 ×n.$ Ее содержит вертикальная или горизонтальная доминошка. Если доминошка вертикальная, то остается только разрезать прямоугольник $2×(n− 1),$ а по предположению способов это сделать равно $Fn.$ Если же доминошка будет горизонтальной, то и под ней должна быть горизонтальная, а значит, останется только разрезать прямоугольник $2× (n− 2),$ а опять же по предположению количество способов это сделать равно $Fn−1.$ Следовательно, количество способов разрезать $2×n$ равно $Fn−1+ Fn = Fn+1,$ что и требовалось.

Ответ:

$F n+1$ число Фибоначчи

Ошибка.
Попробуйте повторить позже

Задача 3#102021

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

Показать ответ и решение

Обозначим $X n$ — число растений на $n−$ й год. Ясно, что $X = 0 0$ и $X = 1. 1$ Для $n ≥2$ имеет место соотношение $X = X + 3X n n−1 n−2$ (три черенка от растений, который растут хотя бы $2$ года и все имеющиеся растений за прошлые года). Характеристическое уравнение линейного рекуррентного соотношения имеет вид $2 q − q− 3= 0,$ откуда $1±√13- q = 2 .$ Таким образом,

(1 − √13)n ( 1+ √13)n Xn =A ---2-- + B --2---

Из начальных условий $A +B = 0$ и $(1− √13)A+ (1 +√13)B =2.$ Поскольку $A= −B,$ то $− 2√13A = 2,$ то есть $A = −√1-. 13$ Итак,

1 ((1+ √13)n (1− √13)n) Xn = √13 ---2-- − ---2--

Подставлять сюда $7$ и считать, что получится, очень не хочется, так что удобнее получить ответ через рекурренту.

Ответ:

$97$

Ошибка.
Попробуйте повторить позже

Задача 4#102023

Обозначим через $A n$ количество несамопересекающихся ломаных из $n$ звеньев, начинающихся в точке $(0,0),$ каждое звено которых совпадает с одним из векторов $r= (1,0),$ $u =(0,1),$ $d= (0,−1).$ Выразите $An$ через $An−1$ и $An−2.$

Показать ответ и решение

Разобьём ломаные на три вида, обозначим их соответствующими буквами:

1.: $R n$ — количество ломаных из $n$ звеньев, в которых последний шаг направо.
2.: $Ln$ — количество ломаных из $n$ звеньев, в которых последний шаг налево.
3.: $Un$ — количество ломаных из $n$ звеньев, в которых последний шаг вверх.

В силу симметрии ясно, что $Ln = Rn.$ Также единственная возможность для самопересечения — это после шага направо пойти налево, поскольку мы не можем опуститься вниз. Тогда напишем рекуррентное соотношение:

Rn = Un−1+ Rn−1, Un = Un−1+ 2Rn−1

А поскольку $Ln = Rn$

An =Un +2Rn, Un+1 = An

Тогда

An = Un+ 2Rn = Un−1+ 2Rn−1+ 2(Un−1+ Rn−1)=

= 2An− 1+Un−1 =2An−1 +An−2

Получаем ответ $An =2An−1+ An−2.$

Ответ:

$A = 2A +A n n− 1 n− 2$

Ошибка.
Попробуйте повторить позже

Задача 5#102024

Некоторые клетки доски $2× n$ красятся в красный цвет так, чтобы ни одна красная клетка не имела соседей по стороне того же цвета. Обозначим через $An$ количество таких раскрасок с четным числом красных клеток, через $Bn$ — с нечетным числом. Чему может быть равно $An − Bn?$

Показать ответ и решение

Разделим доски на два типа: обычные $F n$ — доски $2×n$ и $G n$ — доски $2× n$ с удаленной угловой клеткой. Дополнительно найдем $Cn$ и $Dn$ — количества правильных раскрасок $Gn$ в четное и нечетное число цветов. Клетки будем нумеровать буквой $a$ или $b,$ соответствующей строке и числами от $1$ до $n$ — столбцы. Множество таких раскрасок разбивается на три подмножества: $an$ закрашена, $bn$ закрашена и ни одна из клеток $an,$ $bn$ не закрашена. Если закрашена $an,$ то $an−1$ и $bn$ не закрашены. Среди остальных клеток правильным образом должно быть закрашено нечетное количество, таким образом, в первом и втором случаях число раскрасок равно $Dn−1.$ Если же обе клетки $an,bn$ не закрашены, то остальные должны быть раскрашены в четное количество, то есть в $An−1.$ Таким образом, $An =An −1+2Dn−1.$ Аналогично

Bn =Bn−1 +2Cn−1

Cn = An−1+ Dn−1

Dn = Bn−1+ Cn−1

Пусть $Pn = An− Bn$ и $Qn =Cn − Dn.$ Тогда $Pn = Pn−1− 2Qn−1,$ $Qn = Pn−1− Qn−1.$ Ясно, что $P1 = −1$ и $Q1 = 0.$ Находим последовательно первые несколько членов ${Pn}$ и ${Qn}:$ $(−1,−1,1,1,−1)$ и $(0,−1,0,1,0).$ Далее последовательности периодичны. Таким образом, $Pn ∈ {±1}.$

Ответ:

$±1$

Ошибка.
Попробуйте повторить позже

Задача 6#102025

Сколько имеется $2016$ -значных чисел, у которых все цифры принадлежат множеству ${1,2,3,4,5}$ и любые две соседние цифры отличаются на $1?$

Показать ответ и решение

Разобьём числа на пять видов по последней цифре, обозначим их соответствующими символами:

1.: $Nn 1$ — количество чисел из $n$ знаков, которые кончаются на $1.$
2.: $n N 2$ — количество чисел из $n$ знаков, которые кончаются на $2.$
3.: $n N 3$ — количество чисел из $n$ знаков, которые кончаются на $3.$
4.: $n N 4$ — количество чисел из $n$ знаков, которые кончаются на $4.$
5.: $Nn5$ — количество чисел из $n$ знаков, которые кончаются на $5.$

Тогда напишем рекуррентные соотношения:

(|| Nn+1= Nn ||||| 1n+1 2n n ||{ N2 = N1 +N 3 || Nn3+1= Nn2 +Nn4 ||||| Nn4+1= Nn3 +Nn5 ||( Nn+1= Nn 5 4

Ясно, что $Nn = Nn 1 5$ и $Nn = Nn 2 4$ (например, можно построить биекцию, заменив $1$ на $5$ и $2$ на $4).$ Тогда давайте по индукции доказывать, что при $n= 2k$ — $Nn = Nn =3k−1 1 5$ и $Nn =Nn = Nn = 2⋅3k−1. 2 3 4$ База очевидна, двузначные числа $21,$ $12,$ $32,$ $23,$ $43,$ $34,$ $54,$ $45.$ Теперь переход с помощью рекурренты:

(||Nn+1 = 2⋅3k−1 ||||| 1n+1 k−1 |||||N 2 = 3⋅3 {Nn+31 = 4⋅3k−1 ||||Nn+12 = 3⋅3k−1 =3k |||||Nn+2 = 6⋅3k−1 =2 ⋅3k |||( 2n+1 k−1 k N 3 = 6⋅3 =2 ⋅3

Теперь у нас спрашивают про $n =2016= 1008⋅2.$ Получаем

(| 2016 1007 |||||N1 = 3 |||{N22016= 2⋅31007 |N23016= 2⋅31007 |||||N2016= 2⋅31007 |||( 42016 1007 N5 = 3

Значит, ответ $1007 8⋅3 .$

Ответ:

$8⋅31007$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#102027

Дима и Саша занимаются двумя на первый взгляд совершенно разными делами. У Димы есть фигура “хромой король” — она умеет ходить на 1 клетку вверх или вправо, а также на $1$ клетку по диагонали вправо-вверх. Пусть $A$ — количество путей хромого короля по доске $n ×n$ из левого нижнего угла в правый верхний, которые никогда не поднимаются выше главной диагонали.

А у Саши есть бумажный квадрат $n× n$ и резак, которым он может проводить горизонтальные или вертикальные разрезы “от края до края”. Саша отметил $n − 1$ узлов клеток, лежащих внутри квадрата на его главной диагонали, и каждый очередной разрез делает по одному из отмеченных узлов, по которому еще разрез не проводился (разрез проводится от края до края того куска бумаги, на котором расположен выбранный на данном ходу узел). Пусть $B$ — количество способов так разрезать квадрат (способы отличающиеся только порядком разрезов считаются одинаковыми). Докажите, что $A = B.$

На рисунках изображены примеры всевозможных способов при $n= 3.$

$PIC$

Показать доказательство

Докажем, что оба количества способов удовлетворяют одному и тому же рекуррентному соотношению

n∑−1 a1 =1, a2 =2, an =an−1+ akan− k k=1

Для хромого короля рассмотрим первый момент на пути (не считая стартовой клетки), когда он попал на главную диагональ. Если это произошло первым же ходом, то мы получаем $a n−1$ способов. Если нет, то первый ход был направо, и далее есть $n$ вариантов, в зависимости от того, в каком столбце впервые король попал на главную диагональ. Если он туда попал в $k+1$ по счету слева столбце, то сделал он это ходом вверх, и до этой клетки добраться было $ak$ способов. С этой клетки до правой-верхней есть $an−k$ способов добраться. Так и получается искомое рекуррентное соотношение.

Для разрезов пронумеруем отмеченные узлы слева направо от $1$ до $n − 1.$ Пусть $k$ -й узел это наименьший узел, по которому разрез проходит от края до края исходного квадрата. Не умаляя общности, он проходит по вертикали. Если этот разрез прошел по $1$ узлу, то остается $an−1$ способов проделать разрезы дальше. Если по $(n− 1)$ -му, то $an−1∕2$ способов (потому что направление следующего разреза предопределено, а значит, вдвое меньше количества всех возможных способов провести дальнейшие разрезы). Если же по какому-то промежуточному узлу $2 ≤k ≤n − 2,$ то есть $ak∕2$ способов провести разрезы слева и $an−k$ способов провести разрезы справа. Не забудем умножить итоговую сумму на $2,$ поскольку первый разрез можно было провести в любом из двух направлений, и получим следующее соотношение:

n−2 an = 2(an−1+ an−1∕2+ ∑ akan−k) k=2

что с учетом $a1 =1$ упрощается до искомого соотношения.

Ошибка.
Попробуйте повторить позже

Задача 8#103200

Сколько $n$ -буквенных слов ( $n$ — натуральное) можно составить из букв $a$ и $b$ так, чтобы после каждой буквы $a$ стояла хотя бы одна буква $b?$ (Букве $a$ разрешается быть последней).

Показать ответ и решение

Пусть подходящих слов длины $n− S . n$ Тогда рассмотрим последнюю букву в нашем слове. Если она $a,$ то перед ней обязательно $b,$ значит, слов, кончающихся на $a− Sn−2.$ Слов, кончающихся на $b− Sn−1.$ То есть $Sn = Sn−2+ Sn−1.$ Значит, наш ответ совпадает с числами Фибоначчи. Для $n= 1$ слова $2,$ для $n =2$ слова $3.$ Значит, ответ $Fn+2.$

Ответ:

$F n+2$

Ошибка.
Попробуйте повторить позже

Задача 9#74089

Сколько семибуквенных слов можно составить из букв $a$ и $b$ так, чтобы после каждой буквы $a$ стояла хотя бы одна буква $b?$ (Букве $a$ разрешается быть последней.)

Показать ответ и решение

Заметим, если наше слово заканчивается на $a,$ то перед $a$ стоит $b.$ Пусть нужных нам слов длины $n$ — $S . n$ Чтобы получить нужное нам слово длины $n,$ мы или к любому слову длины $n − 1$ добавим в конце $b$ (таким образом получим все возможные слова с окончанием $b$ ), или к любому слову длины $n− 2$ добавим в конце $ba$ (таким образом получим все возможные слова с окончанием $a$ ). Получается, что $Sn = Sn−1+ Sn−2.$ $S0 =1,S1 = 2,$ значит, $S7$ равно девятому числу Фибоначчи, что равно $34.$

Ответ:

$34$

Ошибка.
Попробуйте повторить позже

Задача 10#35431

Максим поднимается по лестнице из двенадцати ступенек. Ступив на первую ступеньку, далее он может шагать вверх либо на одну ступеньку, либо на две. Сколькими способами Максим сможет подняться по лестнице?

Показать ответ и решение

Количество способов подняться на лестницу из $n$ ступенек, находясь у ее подножья и соблюдая условия задачи, обозначим через $f n$ . На первую и на вторую ступеньки Максим может попасть единственным способом, поэтому $f1 = 1,f2 = 1$ .

Пусть Максим поднимается по лестнице, в которой $n +2$ ступеньки. Если его первый шаг был на две ступеньки (с первой на третью), то ему останется преодолеть $n$ ступенек и количество способов закончить подъем равно $fn$ .

Если же первый шаг был на одну ступеньку, то количество способов закончить подъем равно $fn+1$ .

Значит, $fn+2 =fn+ fn+1$ . Это равенство позволяет, зная $f1$ и $f2$ , последовательно вычислить значение $fn$ для любого натурального $n$ . В нашем случае $f3 = 2,f4 = 3,f5 = 5$ , $f6 = 8,f7 = 13,f8 = 21,f9 = 34,f10 = 55,f11 = 89,f12 =144$ .

Ответ: 144

Ошибка.
Попробуйте повторить позже

Задача 11#74947

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

Источники: САММАТ-2022, 11.3 (см. sammat.samgtu.ru)

Показать ответ и решение

Обозначим число способов спуститься по лестнице из $k$ ступенек за $N k$ . По условию Вася может шагать на одну, две или три ступеньки вниз с текущей, поэтому $Nk =Nk− 1+Nk−2 +Nk−3.$ Учитывая, что $N0 = 1$ (у Васи один способ — стоять на месте), $N1 = 1,N2 =2,$ последовательно находим

N3 = 2+ 1+1 =4

N4 = 4+ 2+1 =7

N5 = 7+4+ 2= 13

N6 = 13+ 7+4 =24

N7 = 24+13+ 7= 44

N8 =44+ 24+13 =81

N9 = 81+44+ 24= 149

Так как на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, нужно перемножить полученные числа вариантов $N8$ и $N9,$ так что искомое число вариантов равно $81⋅149 =12069.$

Ответ: 12069

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#78846

Блоха Кузя может совершать прыжки из каждой вершины правильного тетраэдра $ABCD$ в три соседние вершины, причем выбор этих вершин случайный и равновозможный. Прыгать Кузя начала из вершины A и, совершив 2020 прыжков, опять оказалась в той же вершине. С какой вероятностью это могло произойти?

Источники: Росатом - 2020, отборочный этап (см. olymp.mephi.ru)

Показать ответ и решение

Рассмотрим некоторый промежуточный шаг в движении Кузи. Если она на этом шаге находится в точке $A$ , то вероятность попасть в $A$ на следующем шаге равна нулю. Если же она находится в любой из оставшихся точек $B,C$ или $D$ ,то вероятность попасть в $A$ на следующем шаге равна $1 3$ , так как из каждой такой точки есть три равновозможных пути, только один из которых приводит в $A$ . Пусть $pk$ — вероятность того, что на $k−$ ом шаге блоха находится в точке $A$ . Соответственно не в точке $A$ она находится с вероятностью $1− pk$ . Тогда на следующем шаге она окажется в $A$ с вероятностью

1 1 pk+1 = (1− pk)⋅3 +0 ⋅pk = (1− pk)⋅3

Таким образом, $p0 = 1$ (так как изначально блоха в точке $A$ ), $p1 =0, p2 = 13,$

( ) p3 = 1− 1 ⋅ 1= 1 − 1, ..., 3 3 3 9

Можно заметить закономерность и заключить при $n≥ 2$

p = 1− 1 +-1 ⋅⋅⋅+ (−-1)n- n 3 9 27 3n−1

Видим, что $p n$ представляет собой сумму членов геометрической прогрессии со знаменателем равным $− 1. 3$ Следовательно,

1− (−1)n−1 n−1 n pn = 1⋅----3n1−1-= 3---+n(−−11) 3 1 +3 4⋅3

32019+-1 P(A)= p2020 = 4⋅32019

Замечание. Чтобы решение было более обоснованным, формулу для $pn$ при $n≥ 2$ можно доказать методом математической индукции.

База:

(−1)2 1 p2 = 32−-1 = 3

Шаг: пусть формула верна для $n= k$ , то есть

k pk = 1− 1 +-1 ⋅⋅⋅+ (−k1)−1 3 9 27 3

Тогда

1 ( 1 1 1- (−1)k) 1 pk+1 = (1− pk)⋅3 = 1 −3 + 9 − 27 + ⋅⋅⋅− 3k−1 ⋅3 =

k+1 k+1 = 1− -1- +-1- − -1--+⋅⋅⋅+ (−1k−)1- = 1− 1 + 1-⋅⋅⋅+ (−-1)k-- 3 3⋅3 9 ⋅3 27 ⋅3 3 ⋅3 3 9 27 3

то есть формула верна и для $n= k+ 1$ . А значит, верна и при любых $n ≥2.$

Ответ:

$32019-+1 4⋅32019$

Ошибка.
Попробуйте повторить позже

Задача 13#102398

В алфавите жителей сказочной планеты АБ2020 всего две буквы: буква А и буква Б. Все слова начинаются на букву А и заканчиваются тоже на букву А. В любом слове буква А не может соседствовать с другой буквой А. Также не может идти подряд больше, чем $2$ буквы Б. Например, слова АББА, АБАБАБА, АББАБАББА являются допустимыми, а слова АББАБ, АБААБА, АБАБББА — нет. Сколько $20$ -буквенных слов в словаре этой планеты?

Источники: ПВГ - 2020, 11.5 (pvg.mk.ru))

Показать ответ и решение

Пусть $W i$ — это количество слов инопланетят, состоящих из $i$ букв.

Заметим, что единственное однобуквенное слово — это слово А. Двухбуквенных слов вообще нет, так как первая и последняя, то есть первая и вторая буквы — это А, но тогда две буквы А стоят рядом, что противоречит определению инопланетного слова. Трёхбуквенное слово тоже только одно — АБА. И четырёхбуквенное слово единственно — АББА. Таким образом,

W1 =1,W2 =0,W3 =1,W4 =1

Рассмотрим теперь какое-нибудь слово $ω$ длины $n,$ где $n >4.$ Его последняя буква — это точно буква А, так как каждое слово начинается и заканчивается буквой А. Предпоследняя буква — это Б, так как две буквы А не могут идти подряд. Есть два варианта, какой может быть буква перед Б, то есть предпредпоследняя буква слова $ω$ :

1) Это буква А. Тогда слово $ω$ имеет вид А...АБА. Рассмотрим строку из первых $n− 2$ букв этого слова. Она начинается и заканчивается на А, а так же в ней нет двух букв А подряд или трёх букв Б подряд, так как иначе $ω$ не было бы словом. А значит эта строка сама является словом.

2) Это буква Б. Тогда перед этой буквой Б стоит буква А, там как три буквы Б не могут идти подряд, и слово $ω$ имеет вид А...АББА. Аналогично случаю 1, строка, образованная первыми $n− 3$ буквами $ω$ будет являться словом.

Получается, что слово $ω$ могло быть получено либо приписыванием строки БА в конец какого-нибудь слова из $n − 2$ букв, либо приписыванием строки ББА в конец какого-нибудь слова из $n− 3$ букв. При этом, приписав в конец каждого из $Wn−2$ слов длины $n− 2$ строку БА, мы получим $Wn−2$ различных слов длины $n.$ Аналогично, приписав в конец каждого из $Wn −3$ слов длины $n − 3$ строку ББА, мы получим $Wn −3$ различных слов длины $n.$ Отсюда,

Wn = Wn−2+ Wn−3

Пользуясь этой формулой, найдем $Wi$ для $i= 5,...,20.$


$W1$	$W2$	$W3$	$W4$	$W5$	$W6$	$W7$	$W8$	$W9$	$W10$

$1$	$0$	$1$	$1$	$1$	$2$	$2$	$3$	$4$	$5$

Итак, в словаре сказочной планеты 86 20-буквенных слов.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 14#95761

Заведующая библиотекой, увидев, что $11$ томов «Малой энциклопедии козлов» стоят в беспорядке, указала на это библиотекарю. Тот в ответ заявил: «Беспорядок — небольшой, так как каждый том стоит либо на своем месте, либо на соседнем». Сколькими способами можно расставить тома энциклопедии в соответствии с этим условием?

Источники: Лига открытий - 2018

Показать ответ и решение

Пусть $F n$ — количество способов расставить ровно $n$ томов в небольшом беспорядке. Рассмотрим первый том. Если он стоит на своем месте, то остальные тома можно расставить $Fn−1$ способами. Если первый том стоит на втором месте, то на первом месте может стоять только второй том, а остальные расставляются $Fn−2$ способами. Итого, мы получаем, что $Fn = Fn−1+ Fn−2.$ Также $F1 =1$ и $F2 = 2.$ Откуда $F11 = 144.$

Ответ:

$144$


$W11$	$W12$	$W13$	$W14$	$W15$	$W16$	$W17$	$W18$	$W19$	$W20$

$7$	$9$	$12$	$16$	$21$	$28$	$37$	$49$	$65$	$86$