1) Сколько существует последовательностей длины n, состоящих из цифр от 0 до k-1, где никакие два соседних элемента

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

1. Если n = 2, то у нас есть k * (k - 1) возможных последовательностей. Это объясняется тем, что на первой позиции может стоять любая цифра от 0 до k-1, а на второй позиции только любая цифра, кроме нуля (потому что два нуля не могут идти подряд).

2. Если n = 3, у нас также k * (k - 1) возможных последовательностей. Опять же, первая и вторая позиции могут быть любыми цифрами от 0 до k-1, а на третьей позиции нам нужно исключить два нуля подряд.

Теперь мы можем рекурсивно решить эту задачу. Предположим, что у нас есть функция f(n, k) для подсчета количества последовательностей длины n с k различными цифрами. Мы можем выразить f(n, k) через значения f(n-1, k) и f(n-2, k):

$$f(n,k)=(k-1)\ast (f(n-1,k)+f(n-2,k))$$

Пояснение: первый множитель (k - 1) соответствует количеству возможных выборов для последней цифры (исключая ноль, чтобы избежать двух нулей подряд), а слагаемые f(n-1, k) и f(n-2, k) соответствуют количеству возможных последовательностей для n-1 и n-2 длин, соответственно.

Теперь, когда у нас есть рекуррентная формула, мы можем использовать динамическое программирование для эффективного решения задачи. Мы создадим двумерный массив размером (N+1) x (K+1), где каждый элемент dp[i][j] будет содержать количество последовательностей длины i с j различными цифрами.

1. Инициализируем значения базовых случаев:

$$dp[2][j]=j\ast (j-1)$$ для всех j от 2 до K.

2. Заполним остальные значения массива dp, используя рекуррентную формулу:

$$dp[i][j]=(j-1)\ast (dp[i-1][j]+dp[i-2][j])\text{для всех}i\ge 3\text{и}2\le j\le K.$$

3. Итоговый ответ будет находиться в ячейке dp[N][K].

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

Давайте рассмотрим базовые случаи для этой задачи:

1. Если N = 1, то у нас есть две возможные последовательности: 0 и 1.

2. Если N = 2, то также есть две возможные последовательности: 00 и 01.

3. Если N = 3, то уже есть возможность появления последовательности 010, так как три единицы не должны идти подряд.

Теперь мы можем использовать аналогичную рекуррентную формулу и динамическое программирование для решения этой задачи. Пусть g(N) будет количество последовательностей длины N, где никакие три единицы не стоят рядом. Тогда:

$$g(N)=g(N-1)+g(N-2)+g(N-3)$$

Пояснение: чтобы построить последовательность длины N, мы можем либо приписать 0 к концу последовательности длины N-1, либо 01 к концу последовательности длины N-2, либо 010 к концу последовательности длины N-3.

Таким образом, мы можем использовать аналогичный подход с динамическим программированием, создав массив g размером (N+1), где каждый элемент g[i] будет содержать количество последовательностей длины i, где никакие три единицы не идут подряд. Исходное значение для этого массива будет:

$$g[1]=2,g[2]=2,g[3]=3$$

Мы будем заполнять остальные значения массива, используя рекуррентную формулу:

$$g[i]=g[i-1]+g[i-2]+g[i-3]\text{для всех}i\ge 4$$

Итоговый ответ на задачу будет находиться в ячейке g[N].

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