|
|
|
|
|
|
|
1
|
|
|
|
|
|
|
1 |
|
1
|
|
|
|
|
|
1 |
|
2 |
|
1
|
|
|
|
|
1 |
|
3 |
|
3 |
|
1
|
|
|
|
1 |
|
4 |
|
6 |
|
4 |
|
1
|
|
|
1 |
|
5 |
|
10 |
|
10 |
|
5 |
|
1
|
|
1 |
|
6 |
|
15 |
|
20 |
|
15 |
|
6 |
|
1
|
1 |
|
7 |
|
21 |
|
35 |
|
35 |
|
21 |
|
7 |
|
1
|
Triunghiul lui Pascal, rândurile de la 0 la 7. Identitatea crosei de hochei confirmă că, de exemplu pentru n=6, r=2, 1+3+6+10+15=35.
|
În combinatorică identitatea:
![{\displaystyle \sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/490832aa174af52fc1ad1a1598f6de287ce87fe3)
pentru
sau echivalent, imaginea în oglindă prin substituția
:
![{\displaystyle \sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose n-r}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3073bd8dc912836bf0ad3a5aba6804f09e15e321)
pentru
este cunoscută drept crosă de hochei,[1] Denumirea provine din reprezentarea grafică a identității pe triunghiul lui Pascal: când sunt evidențiați termenii sumați și suma însăși, forma care apare amintește vag de o crosă de hochei.
Fie
![{\displaystyle X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/173daae7db54e382ac6be423f6ad0657fc203b4e)
și
, și se compară coeficienții lui
.
Atât demonstrațiile inductive, cât și cele algebrice folosesc formula lui Pascal:
![{\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4828d956ef936f8d9533953c6e3473c7bde410d5)
Această identitate poate fi demonstrată prin inducție matematică pe n.
Cazul inițial: fie
;
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7cd5d38710299739da51b4e21e26145b4c7362d)
Pasul inductiv: se presupune că pentru un
,
![{\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46af95c610830cd9213ec18ab1331678c5065429)
Atunci
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc752b84b999235c3651124f9f2bfe26ed0aa10c)
Se folosește un argument telescopic(d) pentru a simplifica calculul sumei:
![{\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{prin telescopare}}\\&={\binom {n+1}{k+1}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08305fb20448113afa66dcc3a0f6a080b2894f7f)
Se presupune că se distribuie
bomboane care nu se pot individualiza la
copii care se individualizează. Aplicând direct metoda stele și bare(d), se obțin
![{\displaystyle {\binom {n+k-1}{k-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2f50898b606219d61c737dddccf656677f3e0bf)
moduri de a face asta. Ca alternativă, mai întâi se pot oferi
bomboane celui mai mare, astfel încât, în esență, să se dea
bomboane la
copii, și din nou cu stele și bare și dubla numărare(d), se obține
![{\displaystyle {\binom {n+k-1}{k-1}}=\sum _{i=0}^{n}{\binom {n+k-2-i}{k-2}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb8022fd832ef0399bce374b422882baa2b1184d)
care se simplifică la rezultatul dorit luând
și
și observând că
:
![{\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12d6833d72ee3bdf2fc69fc5b078357c3ff6c8f6)
se poate forma un comitet de mărimea
dintr-un grup de
oameni în
![{\displaystyle {\binom {n+1}{k+1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aeb68e1b44875b49ef2ba4c1dfaf646897a0e806)
moduri.
Acum se distribuie numerele
la
din cei
oameni. Se poate diviza asta în
cazuri disjuncte. În general, în cazul în care
,
, persoana
este în comitet, iar persoanele
nu sunt în comitet. Acest lucru se poate face în
![{\displaystyle {\binom {n-x+1}{k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6cae789f340b47a5282a2508dce814eafcd2363)
moduri. Acum se pot însuma valorile acestor
cazuri disjuncte, obținând
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/084c6e49e59500434647f3cb0e17331d6258a266)
- ^ en C.H. Jones (1996) Generalized Hockey Stick Identities and N-Dimensional Block Walking., Fibonacci Quarterly 34(3), 280-288.