bulgakov

25. Как растут и убывают биномиальные коэффициенты

Числа (n0),(n1),…,(nn)\dbinom n0,\dbinom n1,\dots,\dbinom nn сначала растут, доходят до середины и затем убывают в обратном порядке. Секрет в отношении соседних коэффициентов: (nk):(nk−1)=n−k+1k\dbinom nk:\dbinom n{k-1}=\dfrac{n-k+1}{k}. Пока это число больше единицы, коэффициенты растут; когда меньше — убывают. Наибольший коэффициент стоит в середине строки: (n⌊n/2⌋)\dbinom n{\lfloor n/2\rfloor}.

Что пригодится из прошлого: сочетания — формула (nk)=n!k!(n−k)!\dbinom nk=\dfrac{n!}{k!(n-k)!}; треугольник Паскаля — на нём видно «горку»; свойства сочетаний — симметрия строки. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Горка в треугольнике Паскаля

Посмотрите на строки 99 и 1010 треугольника:

 9: 1 9 36 84 126 126 84 36 9 1
10: 1 10 45 120 210 252 210 120
    45 10 1

Строка растёт к середине и затем спадает. У строки 1010 пик один — 252252. У строки 99 два одинаковых числа в середине — 126126 и 126126. Нарисуем строку 99 полосками:

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  █

Горка симметрична — это знакомое свойство (nk)=(nn−k)\dbinom nk=\dbinom n{n-k}. Нужно объяснить два факта: почему горка одна (нет «ям» внутри) и почему вершина в середине.

Теорема

Если nn — чётное число, то

(n0)<(n1)<⋯<(nn2)>(nn2+1)>⋯>(nn).\binom n0<\binom n1<\cdots<\binom n{\frac n2}>\binom n{\frac n2+1}>\cdots>\binom nn.

Если nn — нечётное число, то

(n0)<(n1)<⋯<(nn−12)=(nn+12)>⋯>(nn).\binom n0<\binom n1<\cdots<\binom n{\frac{n-1}2}=\binom n{\frac{n+1}2}>\cdots>\binom nn.

Следствие. При фиксированном nn наибольшее значение (nk)\dbinom nk равно (n⌊n/2⌋)\dbinom n{\lfloor n/2\rfloor}. Здесь ⌊n/2⌋\lfloor n/2\rfloor — целая часть n/2n/2: наибольшее целое число, не превосходящее n/2n/2.

Доказательство

Чтобы сравнить два соседних числа, найдём их отношение. Для 1≤k≤n1\le k\le n

(nk)(nk−1)=n!k! (n−k)!n!(k−1)! (n−k+1)!=(k−1)! (n−k+1)!k! (n−k)!=n−k+1k.\frac{\dbinom nk}{\dbinom n{k-1}}=\frac{\dfrac{n!}{k!\,(n-k)!}}{\dfrac{n!}{(k-1)!\,(n-k+1)!}} =\frac{(k-1)!\,(n-k+1)!}{k!\,(n-k)!}=\frac{n-k+1}{k}.

Сократили n!n!, затем k!=k⋅(k−1)!k!=k\cdot(k-1)! и (n−k+1)!=(n−k+1)⋅(n−k)!(n-k+1)!=(n-k+1)\cdot(n-k)!.

Теперь определим, когда дробь больше единицы:

n−k+1k>1  ⟺  n−k+1>k  ⟺  k<n+12.\frac{n-k+1}{k}>1\iff n-k+1>k\iff k<\frac{n+1}{2}.

Значит:

  • при k<n+12k<\dfrac{n+1}2 отношение больше 11, и последовательность (nk)\dbinom nk возрастает;
  • при k>n+12k>\dfrac{n+1}2 отношение меньше 11, и последовательность убывает;
  • при k=n+12k=\dfrac{n+1}2 отношение равно 11: соседние коэффициенты равны. Такое возможно только при нечётном nn, когда n+12\dfrac{n+1}2 — целое число.

Чётное nn. Число n+12\dfrac{n+1}2 — «половинка» между n2\dfrac n2 и n2+1\dfrac n2+1. Условие k<n+12k<\dfrac{n+1}2 для целого kk означает k≤n2k\le\dfrac n2 (число n+12\dfrac{n+1}2 лежит между n2\dfrac n2 и n2+1\dfrac n2+1). Значит, до k=n2k=\dfrac n2 включительно коэффициенты растут: (nn/2)\dbinom n{n/2} больше предыдущего. После этого убывают.

Нечётное nn. Число n+12\dfrac{n+1}2 целое. До k=n−12k=\dfrac{n-1}2 включительно коэффициенты растут. При k=n+12k=\dfrac{n+1}2 отношение равно 11: (n(n−1)/2)=(n(n+1)/2)\dbinom n{(n-1)/2}=\dbinom n{(n+1)/2}. После этого убывают. □\square

Разберём на примере n=7n=7

Составим таблицу для n=7n=7: в ней отношение n−k+1k\dfrac{n-k+1}{k}, его сравнение с единицей и сравнение соседних коэффициентов (7k)\dbinom7k и (7k−1)\dbinom7{k-1}:

kk Отношение С 11 Вывод
1 77 > 1 7>17>1
2 33 > 1 21>721>7
3 5/35/3 > 1 35>2135>21
4 11 = 1 35=3535=35
5 3/53/5 < 1 21<3521<35
6 2/62/6 < 1 7<217<21
7 1/71/7 < 1 1<71<7

Отношение больше единицы при k=1,2,3k=1,2,3, равно единице при k=4=7+12k=4=\dfrac{7+1}2 (числа 3535 и 3535), меньше единицы при k=5,6,7k=5,6,7. Получилась цепочка

1<7<21<35=35>21>7>1.1<7<21<35=35>21>7>1.

Следствие: где максимум

Наибольшее число в строке nn стоит в середине: для чётного nn — единственное (nn/2)\dbinom n{n/2}, для нечётного nn — два равных числа в середине (n(n−1)/2)=(n(n+1)/2)\dbinom n{(n-1)/2}=\dbinom n{(n+1)/2}. И в том, и в другом случае это (n⌊n/2⌋)\dbinom n{\lfloor n/2\rfloor}.

  • Строка 1010: максимум (105)=252\dbinom{10}5=252.
  • Строка 99: максимум (94)=(95)=126\dbinom94=\dbinom95=126.

Смысл максимума. Число (nk)\dbinom nk — это число двоичных слов длины nn с kk единицами (или число подмножеств размера kk). Больше всего слов, где единиц примерно половина.

Частые ошибки

  • Считать, что коэффициенты растут до конца строки. После середины они убывают.
  • Искать пик не в середине. Он всегда у k≈n2k\approx\dfrac n2.
  • Забыть про нечётное nn. Там два равных числа в центре, строгого максимума нет.
  • Применять отношение n−k+1k\dfrac{n-k+1}k к k=0k=0. Отношение определено для 1≤k≤n1\le k\le n.

Проверь себя

1. Найдите наибольшее число в строке 1212 треугольника Паскаля.

Решение

n=12n=12 чётное, максимум в середине: (126)=924\dbinom{12}6=924.

2. При каких kk число (15k)\dbinom{15}{k} наибольшее?

Решение

n=15n=15 нечётное, максимум в двух средних местах: k=7k=7 и k=8k=8. (157)=(158)=6435\dbinom{15}7=\dbinom{15}8=6435.

3. Что больше: (114)\dbinom{11}4 или (115)\dbinom{11}5?

Решение

Отношение при k=5k=5: 11−5+15=75>1\dfrac{11-5+1}{5}=\dfrac75>1, значит, (115)>(114)\dbinom{11}5>\dbinom{11}4. Проверка: 462>330462>330.

4. Что больше: (3012)\dbinom{30}{12} или (3013)\dbinom{30}{13}?

Решение

Отношение при k=13k=13: 30−13+113=1813>1\dfrac{30-13+1}{13}=\dfrac{18}{13}>1, значит, (3013)>(3012)\dbinom{30}{13}>\dbinom{30}{12}. Левее середины (k<15,5k<15{,}5) числа растут.

Итог

  • (nk):(nk−1)=n−k+1k\dbinom nk:\dbinom n{k-1}=\dfrac{n-k+1}{k}.
  • Это отношение больше 11 при k<n+12k<\dfrac{n+1}2, равно 11 при k=n+12k=\dfrac{n+1}2, меньше 11 при k>n+12k>\dfrac{n+1}2.
  • Поэтому строка треугольника Паскаля сначала растёт, потом убывает; наибольший коэффициент — (n⌊n/2⌋)\dbinom n{\lfloor n/2\rfloor}.
ПрактикаЗагружаем тест…