Сколькими способами в упорядоченных N ячейках можно расположить k (или от 0 до k) шаров так, чтобы: 1) не было двух соседних шаров.
2) не было трёх соседних шаров.

Предыдущий
вопрос Следующий
вопрос

1) Для случая, когда нельзя иметь два соседних шара, можно построить последовательность из 2 возможных элементов: шар и пустое место. Для этого случая число способов будет равно числу способов переставить k шаров и (N-k) пустых мест: C(N, k) k! (N-k)!.

2) Для случая, когда нельзя иметь три соседних шара, можно рассмотреть следующие возможные комбинации: ШПШ, ПШП, ШППШ.
Таким образом, число способов расположить шары и пустые места будет равно сумме числа способов для каждой из комбинаций: C(N-2, k) + C(N-2, k-1) + C(N-2, k-2).

Аналогичные формулы могут быть выведены для других комбинаций шаров и пустых ячеек в зависимости от условия.