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) * (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 * (j - 1)\] для всех j от 2 до K.

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

\[
dp[i][j] = (j - 1) * (dp[i-1][j] + dp[i-2][j]) \quad \text{для всех} \quad i \geq 3 \quad \text{и} \quad 2 \leq j \leq 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, \quad g[2] = 2, \quad g[3] = 3\]

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

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

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

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