Центральный биномиальный коэффициент

Последовательность чисел ((2n) выберите (n))

Треугольник Паскаля, строки с 0 по 7. Числа в центральном столбце — центральные биномиальные коэффициенты.

В математике n- й центральный биномиальный коэффициент — это частный биномиальный коэффициент

${\displaystyle {2n \choose n}={\frac {(2n)!}{(n!)^{2}}}{\text{ for all }}n\geq 0.}$

Они называются центральными, поскольку они появляются точно в середине четных строк в треугольнике Паскаля . Первые несколько центральных биномиальных коэффициентов, начинающихся с n = 0, следующие:

1 , 2 , 6 , 20 , 70 , 252 , 924, 3432, 12870, 48620, ...; (последовательность A000984 в OEIS )

Комбинаторные интерпретации и другие свойства

Центральные биномиальные коэффициенты дают число возможных назначений n -сторонних спортивных команд из 2 n игроков, принимая во внимание сторону игровой площадки.

Центральный биномиальный коэффициент — это число расположений, в которых имеется равное количество двух типов объектов. Например, когда , биномиальный коэффициент равен 6, и имеется шесть расположений двух копий A и двух копий B : AABB , ABAB , ABBA , BAAB , BABA , BBAA . ${\displaystyle {\binom {2n}{n}}}$ ${\displaystyle n=2}$ ${\displaystyle {\binom {2\cdot 2}{2}}}$

Тот же центральный биномиальный коэффициент — это также число слов длины 2 n , составленных из A и B , в которых при чтении слева направо никогда не бывает больше B , чем A , в любой точке. Например, когда , существует шесть слов длины 4 , в которых каждый префикс имеет по крайней мере столько же копий A , сколько и B : AAAA , AAAB , AABA , AABB , ABAA , ABAB . ${\displaystyle {\binom {2n}{n}}}$ ${\displaystyle n=2}$

Число множителей 2 в равно числу единиц в двоичном представлении n . ^[1] Как следствие, 1 является единственным нечетным центральным биномиальным коэффициентом. ${\displaystyle {\binom {2n}{n}}}$

Производящая функция

Обычная производящая функция для центральных биномиальных коэффициентов имеет вид Это можно доказать с помощью биномиального ряда и соотношения , где — обобщенный биномиальный коэффициент . ^[2] $${\displaystyle {\frac {1}{\sqrt {1-4x}}}=\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}=1+2x+6x^{2}+20x^{3}+70x^{4}+252x^{5}+\cdots .}$$ $${\displaystyle {\binom {2n}{n}}=(-1)^{n}4^{n}{\binom {-1/2}{n}},}$$ ${\displaystyle \textstyle {\binom {-1/2}{n}}}$

Центральные биномиальные коэффициенты имеют экспоненциальную производящую функцию , где I ₀ — модифицированная функция Бесселя первого рода . ^[3] $${\displaystyle \sum _{n=0}^{\infty }{\binom {2n}{n}}{\frac {x^{n}}{n!}}=e^{2x}I_{0}(2x),}$$

Производящая функция квадратов центральных биномиальных коэффициентов может быть записана в терминах полного эллиптического интеграла первого рода : ^[4]

${\displaystyle \sum _{n=0}^{\infty }{\binom {2n}{n}}^{2}x^{n}={\frac {2}{\pi }}K(4{\sqrt {x}}).}$

Асимптотический рост

Асимптотическое поведение можно описать довольно точно: ^[5] $${\displaystyle {2n \choose n}={\frac {4^{n}}{\sqrt {\pi n}}}\left(1-{\frac {1}{8n}}+{\frac {1}{128n^{2}}}+{\frac {5}{1024n^{3}}}+O(n^{-4})\right).}$$

Связанные последовательности

Тесно связанные каталонские числа C _n задаются формулой:

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={2n \choose n}-{2n \choose n+1}{\text{ for all }}n\geq 0.}$

Небольшим обобщением центральных биномиальных коэффициентов является их рассмотрение в виде , с соответствующими действительными числами n , где — гамма-функция , а — бета-функция . ${\displaystyle {\frac {\Gamma (2n+1)}{\Gamma (n+1)^{2}}}={\frac {1}{n\mathrm {B} (n+1,n)}}}$ ${\displaystyle \Gamma (x)}$ ${\displaystyle \mathrm {B} (x,y)}$

Степени двойки, делящие центральные биномиальные коэффициенты, задаются последовательностью Гулда , n- й элемент которой представляет собой число нечетных целых чисел в строке n треугольника Паскаля.

Возведение в квадрат производящей функции дает Сравнение коэффициентов дает Например, (последовательность A000302 в OEIS ). $${\displaystyle {\frac {1}{1-4x}}=\left(\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}\right)\left(\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}\right).}$$ ${\displaystyle x^{n}}$ $${\displaystyle \sum _{k=0}^{n}{\binom {2k}{k}}{\binom {2n-2k}{n-k}}=4^{n}.}$$ ${\displaystyle 64=1(20)+2(6)+6(2)+20(1)}$

Число путей решетки длиной 2 n , начинающихся и заканчивающихся в начале координат, равно (последовательность A002894 в OEIS ). $${\displaystyle \sum _{k=0}^{n}{\binom {2k}{k}}{\binom {2n-2k}{n-k}}{\binom {2n}{2k}}={\binom {2n}{n}}\sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}^{2}}$$

Другая информация

Половина центрального биномиального коэффициента (для ) (последовательность A001700 в OEIS ) видна в теореме Вольстенхолма . ${\displaystyle \textstyle {\frac {1}{2}}{2n \choose n}={2n-1 \choose n-1}}$ ${\displaystyle n>0}$

Согласно гипотезе Эрдёша о бесквадратности , доказанной в 1996 году, ни один центральный биномиальный коэффициент с n > 4 не является бесквадратным .

${\displaystyle \textstyle {\binom {2n}{n}}}$это сумма квадратов n -й строки Треугольника Паскаля: ^[3]

${\displaystyle {2n \choose n}=\sum _{k=0}^{n}{\binom {n}{k}}^{2}}$

Например, . ${\displaystyle {\tbinom {6}{3}}=20=1^{2}+3^{2}+3^{2}+1^{2}}$

Эрдёш широко использует центральные биномиальные коэффициенты в своем доказательстве постулата Бертрана .

Еще одним примечательным фактом является то, что степень деления числа 2 равна n . ${\displaystyle (n+1)\dots (2n)}$

Смотрите также

• Центральный трехчленный коэффициент

Ссылки

1. Sloane, N. J. A. (ред.). "Последовательность A000120". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
2. Стэнли, Ричард П. (2012), Перечислительная комбинаторика , т. 1 (2-е изд.), Cambridge University Press, Пример 1.1.15, ISBN 978-1-107-60262-5
3. Sloane, N. J. A. (ред.). "Последовательность A000984 (Центральные биномиальные коэффициенты)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
4. Sloane, N. J. A. (ред.). "Последовательность A002894". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
5. Люк, Юделл Л. (1969). Специальные функции и их приближения, т. 1. Нью-Йорк, США: Academic Press, Inc. стр. 35.

• Коши, Томас (2008), Каталонские числа с приложениями , Oxford University Press, ISBN 978-0-19533-454-8.

Внешние ссылки

• Центральный биномиальный коэффициент в PlanetMath .