Подготовка учащихся олимпиадам информатике. Задача 7. Сколько последовательностей {a1, a2, …, a8}, состоящих из +1 и –1, обладают тем свойством, что a1 + a2 + … + a8 = 0, а все их частичные суммы a1, a1 + a2, …, a1 + a2 + … + a8 неотрицательны?
Подготовка учащихся олимпиадам информатике
Задача 7 (8 баллов). Сколько последовательностей {a1, a2, …, a8}, состоящих из +1 и –1, обладают тем свойством, что a1 + a2 + … + a8 = 0, а все их частичные суммы a1, a1 + a2, …, a1 + a2 + … + a8 неотрицательны?
Решение задач 7.Подготовка учащихся олимпиадам информатике.
Первый способ. Задачу можно решить методом полного перебора, который дает следующие 14 вариантов:
+1+1+1+1-1-1-1-1, +1+1+1-1+1-1-1-1, +1+1+1-1-1+1-1-1, +1+1+1-1-1-1+1-1, +1+1-1+1+1-1-1-1, +1+1-1+1-1+1-1-1,
+1+1-1+1-1-1+1-1, +1+1-1-1+1+1-1-1, +1+1-1-1+1-1+1-1, +1-1+1+1+1-1-1-1, +1-1+1+1-1+1-1-1, +1-1+1+1-1-1+1-1,
+1-1+1-1+1+1-1-1, +1-1+1-1+1-1+1-1.
Второй способ. Можно показать, что количество последовательностей, удовлетворяющих условию задачи, определяется
четвертым числом Каталана. Само число Каталана выражается формулой C(n) = (2n)!/n!/(n+1)!. C(4) = (2⋅4)!/4!/(4+1)! =
(8)!/4!/(5)! = 1⋅2⋅3⋅4⋅5⋅6⋅7⋅8/1⋅2⋅3⋅4/1⋅2⋅3⋅4⋅5 = 5⋅6⋅7⋅8/1⋅2⋅3⋅4⋅5 = 7⋅2 = 14.
Ответ: 14.
