Рекуррентные соотношения биномиальных коэффициентов в треугольнике Паскаля
Треугольник Паскаля, строки с 0 по 7. Тождество хоккейной клюшки подтверждает, например: для n = 6, r = 2: 1+3+6+10+15=35. В комбинаторике тождество хоккейной клюшки , [1] тождество рождественского чулка , [2] тождество бумеранга , тождество Ферма или теорема Чу , [3] утверждает, что если — целые числа, то н ≥ г ≥ 0 {\displaystyle n\geq r\geq 0}
( г г ) + ( г + 1 г ) + ( г + 2 г ) + ⋯ + ( н г ) = ( н + 1 г + 1 ) . {\displaystyle {\binom {r}{r}}+{\binom {r+1}{r}}+{\binom {r+2}{r}}+\cdots +{\binom {n} r}}={\binom {n+1}{r+1}}.} Название происходит от графического представления тождества в треугольнике Паскаля : когда слагаемые, представленные в сумме, и сама сумма выделены, то полученная форма смутно напоминает эти объекты (см. хоккейную клюшку , рождественский чулок ).
Формулировки Используя сигма-нотацию , тождество утверждает:
∑ я = г н ( я г ) = ( н + 1 г + 1 ) для н , г ∈ Н , н ≥ г {\displaystyle \sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r} или, что эквивалентно, зеркальное отображение путем подстановки : j → i − r {\displaystyle j\to i-r}
∑ j = 0 n − r ( j + r r ) = ∑ j = 0 n − r ( j + r j ) = ( n + 1 n − r ) for n , r ∈ N , n ≥ r . {\displaystyle \sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose n-r}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r.}
Доказательства
Доказательство функции генерации Пусть . Тогда по формуле частичной суммы геометрической прогрессии находим, что X = 1 + x {\displaystyle X=1+x}
X r + X r + 1 + ⋯ + X n = X r − X n + 1 1 − X = X n + 1 − X r x {\displaystyle X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}={\frac {X^{n+1}-X^{r}}{x}}} Далее, по биномиальной теореме мы также находим, что
X r + k = ( 1 + x ) r + k = ∑ i = 0 r + k ( r + k i ) x i {\displaystyle X^{r+k}=(1+x)^{r+k}=\sum _{i=0}^{r+k}{\binom {r+k}{i}}x^{i}}
Обратите внимание, что это означает, что коэффициент in определяется как . x r {\displaystyle x^{r}} X r + k {\displaystyle X^{r+k}} ( r + k r ) {\displaystyle {\binom {r+k}{r}}}
Таким образом, коэффициент в левой части нашего первого уравнения можно получить путем суммирования коэффициентов из каждого члена, что дает x r {\displaystyle x^{r}} x r {\displaystyle x^{r}}
∑ k = 0 n − r ( r + k r ) {\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}}
Аналогично, мы находим, что коэффициент в правой части определяется коэффициентом в , который равен x r {\displaystyle x^{r}} x r + 1 {\displaystyle x^{r+1}} X n + 1 − X r {\displaystyle X^{n+1}-X^{r}}
( n + 1 r + 1 ) − ( r r + 1 ) = ( n + 1 r + 1 ) {\displaystyle {\binom {n+1}{r+1}}-{\binom {r}{r+1}}={\binom {n+1}{r+1}}}
Поэтому мы можем сравнить коэффициенты на каждой стороне уравнения, чтобы найти, что x r {\displaystyle x^{r}}
∑ k = 0 n − r ( r + k r ) = ( n + 1 r + 1 ) {\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}={\binom {n+1}{r+1}}}
Индуктивные и алгебраические доказательства Индуктивное и алгебраическое доказательства используют тождество Паскаля :
( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) . {\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}
Индуктивное доказательство Это тождество можно доказать методом математической индукции . n {\displaystyle n}
Базовый случай
Пусть ; n = r {\displaystyle n=r}
∑ i = r n ( i r ) = ∑ i = r r ( i r ) = ( r r ) = 1 = ( r + 1 r + 1 ) = ( n + 1 r + 1 ) . {\displaystyle \sum _{i=r}^{n}{i \choose r}=\sum _{i=r}^{r}{i \choose r}={r \choose r}=1={r+1 \choose r+1}={n+1 \choose r+1}.} Индуктивный шаг
Предположим, для некоторых , k ∈ N , k ⩾ r {\displaystyle k\in \mathbb {N} ,k\geqslant r}
∑ i = r k ( i r ) = ( k + 1 r + 1 ) {\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}} Затем
∑ i = r k + 1 ( i r ) = ( ∑ i = r k ( i r ) ) + ( k + 1 r ) = ( k + 1 r + 1 ) + ( k + 1 r ) = ( k + 2 r + 1 ) . {\displaystyle \sum _{i=r}^{k+1}{i \choose r}=\left(\sum _{i=r}^{k}{i \choose r}\right)+{k+1 \choose r}={k+1 \choose r+1}+{k+1 \choose r}={k+2 \choose r+1}.}
Алгебраическое доказательство Для упрощения вычисления суммы мы используем телескопический аргумент:
∑ t = 0 n ( t k ) = ∑ t = k n ( t k ) = ∑ t = k n [ ( t + 1 k + 1 ) − ( t k + 1 ) ] = ∑ t = k n ( t + 1 k + 1 ) − ∑ t = k n ( t k + 1 ) = ∑ t = k + 1 n + 1 ( t k + 1 ) − ∑ t = k n ( t k + 1 ) = ( n + 1 k + 1 ) − ( k k + 1 ) ⏟ 0 by telescoping = ( n + 1 k + 1 ) . {\displaystyle {\begin{aligned}\sum _{t=\color {blue}0}^{n}{\binom {t}{k}}=\sum _{t=\color {blue}k}^{n}{\binom {t}{k}}&=\sum _{t=k}^{n}\left[{\binom {t+1}{k+1}}-{\binom {t}{k+1}}\right]\\&=\sum _{t=\color {green}k}^{\color {green}n}{\binom {\color {green}{t+1}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&=\sum _{t=\color {green}{k+1}}^{\color {green}{n+1}}{\binom {\color {green}{t}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&={\binom {n+1}{k+1}}-\underbrace {\binom {k}{k+1}} _{0}&&{\text{by telescoping}}\\&={\binom {n+1}{k+1}}.\end{aligned}}}
Комбинаторные доказательства
Доказательство 1 Представьте, что мы раздаем неотличимые друг от друга конфеты различимым детям. При прямом применении метода звезд и полос есть n {\displaystyle n} k {\displaystyle k}
( n + k − 1 k − 1 ) {\displaystyle {\binom {n+k-1}{k-1}}} способы сделать это. В качестве альтернативы мы можем сначала дать конфеты старшему ребенку, так что мы по сути даем конфеты детям и снова, со звездами и полосами и двойным подсчетом , мы имеем 0 ⩽ i ⩽ n {\displaystyle 0\leqslant i\leqslant n} n − i {\displaystyle n-i} k − 1 {\displaystyle k-1}
( n + k − 1 k − 1 ) = ∑ i = 0 n ( n + k − 2 − i k − 2 ) , {\displaystyle {\binom {n+k-1}{k-1}}=\sum _{i=0}^{n}{\binom {n+k-2-i}{k-2}},} что упрощается до желаемого результата, если взять и , и заметить, что : n ′ = n + k − 2 {\displaystyle n'=n+k-2} r = k − 2 {\displaystyle r=k-2} n ′ − n = k − 2 = r {\displaystyle n'-n=k-2=r}
( n ′ + 1 r + 1 ) = ∑ i = 0 n ( n ′ − i r ) = ∑ i = r n ′ ( i r ) . {\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}
Доказательство 2 Мы можем сформировать комитет из группы людей, k + 1 {\displaystyle k+1} n + 1 {\displaystyle n+1}
( n + 1 k + 1 ) {\displaystyle {\binom {n+1}{k+1}}} способами. Теперь мы раздаем номера людям . Затем мы можем разделить наш процесс формирования комитета на исчерпывающие и непересекающиеся случаи на основе члена комитета с наименьшим номером, . Обратите внимание, что есть только люди без номеров, то есть мы должны выбрать по крайней мере одного человека с номером, чтобы сформировать комитет людей. В общем, в случае , человек входит в комитет, а человек не входит в комитет. Остальная часть комитета затем может быть выбрана в 1 , 2 , 3 , … , n − k + 1 {\displaystyle 1,2,3,\dots ,n-k+1} n − k + 1 {\displaystyle n-k+1} n + 1 {\displaystyle n+1} n − k + 1 {\displaystyle n-k+1} x {\displaystyle x} k {\displaystyle k} k + 1 {\displaystyle k+1} x {\displaystyle x} x {\displaystyle x} 1 , 2 , 3 , … , x − 1 {\displaystyle 1,2,3,\dots ,x-1}
( n − x + 1 k ) {\displaystyle {\binom {n-x+1}{k}}} способами. Теперь мы можем просуммировать значения этих непересекающихся случаев и, используя двойной счет , получим n − k + 1 {\displaystyle n-k+1}
( n + 1 k + 1 ) = ( n k ) + ( n − 1 k ) + ( n − 2 k ) + ⋯ + ( k + 1 k ) + ( k k ) . {\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n-1}{k}}+{\binom {n-2}{k}}+\cdots +{\binom {k+1}{k}}+{\binom {k}{k}}.}
Смотрите также
Ссылки ^ CH Jones (1996) Обобщенные тождества хоккейной клюшки и N-мерная ходьба по блокам. Fibonacci Quarterly 34 (3), 280-288. ^ W., Weisstein, Eric. "Теорема о рождественском чулке". mathworld.wolfram.com . Получено 01.11.2016 . {{cite web }}: CS1 maint: multiple names: authors list (link)^ Меррис, Рассел (2003). Комбинаторика (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. п. 45. ИСБН 0-471-45849-X
Внешние ссылки На АОПС На StackExchange, Математика Лестница Паскаля на форуме Dyalog Chat 
![{\displaystyle {\begin{aligned}\sum _{t=\color {blue}0}^{n}{\binom {t}{k}}=\sum _{t=\color {blue}k}^{n}{\binom {t}{k}}&=\sum _{t=k}^{n}\left[{\binom {t+1}{k+1}}-{\binom {t}{k+1}}\right]\\&=\sum _{t=\color {green}k}^{\color {green}n}{\binom {\color {green}{t+1}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&=\sum _{t=\color {green}{k+1}}^{\color {green}{n+1}}{\binom {\color {green}{t}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&={\binom {n+1}{k+1}}-\underbrace {\binom {k}{k+1}} _{0}&&{\text{путем телескопирования}}\\&={\binom {n+1}{k+1}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ce84ab741d7707c5b7c8fd325a2db456d91c14c)
