25. Как растут и убывают биномиальные коэффициенты
Числа сначала растут, доходят до середины и затем убывают в обратном порядке. Секрет в отношении соседних коэффициентов: . Пока это число больше единицы, коэффициенты растут; когда меньше — убывают. Наибольший коэффициент стоит в середине строки: .
Что пригодится из прошлого: сочетания — формула ; треугольник Паскаля — на нём видно «горку»; свойства сочетаний — симметрия строки. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Горка в треугольнике Паскаля
Посмотрите на строки и треугольника:
9: 1 9 36 84 126 126 84 36 9 1
10: 1 10 45 120 210 252 210 120
45 10 1
Строка растёт к середине и затем спадает. У строки пик один — . У строки два одинаковых числа в середине — и . Нарисуем строку полосками:
k=0 1 █
k=1 9 █
k=2 36 ██████
k=3 84 █████████████
k=4 126 ████████████████████
k=5 126 ████████████████████
k=6 84 █████████████
k=7 36 ██████
k=8 9 █
k=9 1 █
Горка симметрична — это знакомое свойство . Нужно объяснить два факта: почему горка одна (нет «ям» внутри) и почему вершина в середине.
Теорема
Если — чётное число, то
Если — нечётное число, то
Следствие. При фиксированном наибольшее значение равно . Здесь — целая часть : наибольшее целое число, не превосходящее .
Доказательство
Чтобы сравнить два соседних числа, найдём их отношение. Для
Сократили , затем и .
Теперь определим, когда дробь больше единицы:
Значит:
- при отношение больше , и последовательность возрастает;
- при отношение меньше , и последовательность убывает;
- при отношение равно : соседние коэффициенты равны. Такое возможно только при нечётном , когда — целое число.
Чётное . Число — «половинка» между и . Условие для целого означает (число лежит между и ). Значит, до включительно коэффициенты растут: больше предыдущего. После этого убывают.
Нечётное . Число целое. До включительно коэффициенты растут. При отношение равно : . После этого убывают.
Разберём на примере
Составим таблицу для : в ней отношение , его сравнение с единицей и сравнение соседних коэффициентов и :
| Отношение | С | Вывод | |
|---|---|---|---|
| 1 | > 1 | ||
| 2 | > 1 | ||
| 3 | > 1 | ||
| 4 | = 1 | ||
| 5 | < 1 | ||
| 6 | < 1 | ||
| 7 | < 1 |
Отношение больше единицы при , равно единице при (числа и ), меньше единицы при . Получилась цепочка
Следствие: где максимум
Наибольшее число в строке стоит в середине: для чётного — единственное , для нечётного — два равных числа в середине . И в том, и в другом случае это .
- Строка : максимум .
- Строка : максимум .
Смысл максимума. Число — это число двоичных слов длины с единицами (или число подмножеств размера ). Больше всего слов, где единиц примерно половина.
Частые ошибки
- Считать, что коэффициенты растут до конца строки. После середины они убывают.
- Искать пик не в середине. Он всегда у .
- Забыть про нечётное . Там два равных числа в центре, строгого максимума нет.
- Применять отношение к . Отношение определено для .
Проверь себя
1. Найдите наибольшее число в строке треугольника Паскаля.
Решение
чётное, максимум в середине: .
2. При каких число наибольшее?
Решение
нечётное, максимум в двух средних местах: и . .
3. Что больше: или ?
Решение
Отношение при : , значит, . Проверка: .
4. Что больше: или ?
Решение
Отношение при : , значит, . Левее середины () числа растут.
Итог
- .
- Это отношение больше при , равно при , меньше при .
- Поэтому строка треугольника Паскаля сначала растёт, потом убывает; наибольший коэффициент — .
