Оценки

[wpoms.]

Исаак решал по порядку шесть заданий олимпиады. Каждое задание оценивалось от `0` до `10` баллами. Он никогда не получал за следующее задание больше, чем за любое предыдущее. Сколько разных последовательностей оценок могло получиться?

@темы: Комбинаторика

Comments

[vyv2]

Число последовательностей начинающихся с 0 равно 1 : (0,0,0,0,0,0).
Число последовательностей начинающихся с 1 равно 1 : (1,0,0,0,0,0).
Число последовательностей начинающихся с 2 равно сумме двух предыдущих `1+1=2=2^1`: (2,0,0,0,0,0);(2,1,0,0,0,0).
Число последовательностей начинающихся с 3 равно сумме 3-х предыдущих `1+1+2=4=2^2``: (3,0,0,0,0,0);(3,1,0,0,0,0);(3,2,0,0,0,0);(3,2,1,0,0,0).
И т.д.
Число последовательностей начинающихся с 4 равно сумме 4-х предыдущих `1+1+2+4=8=2^3``: (4,0,0,0,0,0);...,(4,3,2,1,0,0).
Число последовательностей начинающихся с 5 равно сумме 5-и предыдущих `1+1+2+4+8=16=2^4``: (5,0,0,0,0,0);...,(5,4,3,2,1,0).
Число последовательностей начинающихся с 6 равно сумме 6-и предыдущих `1+1+2+4+8+16=32=2^5``: (6,0,0,0,0,0);...,(6,5,4,3,2,1).
Число последовательностей начинающихся с 7 равно сумме 7-и предыдущих , умноженное на число сочетаний `C_6 (5)=C_6 (1)=6`, т.е. 32*6=192.
Число последовательностей начинающихся с 8 равно сумме 7-и предыдущих , умноженное на число сочетаний `C_7 (5)=C_7 (2)=21`, т.е. 32*21=672.
Число последовательностей начинающихся с 9 равно сумме 7-и предыдущих , умноженное на число сочетаний `C_8 (5)=C_8 (3)=46`, т.е. 32*46=1472.
Число последовательностей начинающихся с 10 равно сумме 7-и предыдущих , умноженное на число сочетаний `C_9 (5)=C_9 (4)=116`, т.е. 32*116=3712.
Общее число последовательностей : `2^6+2^5(C_6 (1)+C_7 (2)+C_8 (3)+C_9 (4))=32*(2+6+21+46+116)=6112`
Прошу проверить.

[Гость]

Ответ: `8008`

`F(n, k) = sum_{i=0}^n F(i, k-1)`, при этом `F(n, k) = F(n-1, k) + F(n, k-1)`. Нужно вычислить `F(10, 6)`

[vyv2]

Гость

У вас при `k=1` получается`F(n,1) = F(n-1, 1) ` . Странно.

[Гость]

Обычно можно не указывать очевидное. В данном случае это "граничные" значения, которые задаются или могут быть элементарно вычислены. В данном случае речь может идти или о `F(n, 1)` или `F(n, 0)`.

[vyv2]

Обычно можно не указывать очевидное.

Нет, пожалуйста, укажите это ваше "очевидное" граничное условие.
Меня в вашем ответе смущает, то что не учитывается смена алгоритма при `n>k`

[Гость]

Можно, например, считать, что `F(n, 1) = n + 1`.

[vyv2]

Я согласен с вашем ответом. Моя ошибка состояла в том, что я неправильно понял условие: " Он никогда не получал за следующее задание больше, чем за любое предыдущее.", заменив его на следующее: " Он всегда получал за следующее задание меньше, чем за любое предыдущее."