6369. Kombinacije i kombinacije sa ponavljanjem

Definicija: za $n\in\mathbb{N} ,$ $k\in\mathbb{N}\cup\{0\} ,$ $k\le n$ je $\binom nk=\frac{n!}{k!\,(n-k)!}$ („ $n$ nad $k$ ”). Posle skraćivanja sa $(n-k)!$ zgodniji oblik je $\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}$ ( $k$ činilaca u brojiocu); npr. $\binom73=\frac{7\cdot6\cdot5}{3\cdot2\cdot1}=35 .$ Kako je $k\ge1 ,$ broj $\binom n{k-1}$ je definisan. Raspisujemo levu stranu:

\binom n{k-1}+\binom nk=\frac{n!}{(k-1)!\,(n-k+1)!}+\frac{n!}{k!\,(n-k)!}

Svodimo na zajednički imenilac $k!\,(n-k+1)! :$ prvi razlomak proširujemo sa $k$ (jer je $k\cdot(k-1)!=k!$ ), a drugi sa $n-k+1$ (jer je $(n-k+1)(n-k)!=(n-k+1)!$ ):

=\frac{n!\cdot k+n!\cdot(n-k+1)}{k!\,(n-k+1)!}=\frac{n!\,(n+1)}{k!\,(n+1-k)!}=\frac{(n+1)!}{k!\,\bigl((n+1)-k\bigr)!}=\binom{n+1}k

Smisao: $k$ -točlane podskupove skupa $\{a_1,\ldots,a_{n+1}\}$ delimo na one koji sadrže $a_{n+1}$ (ostalih $k-1$ biramo od $n :$ $\binom n{k-1}$ ) i one koji ga ne sadrže ( $\binom nk$ ). Primer: $\binom42+\binom43=6+4=10=\binom53 .$

Time je dokazano da je $\binom n{k-1}+\binom nk=\binom{n+1}k .$

Započni učenje

Privatni časovi

501.b

Beleške

Slični zadaci

Slični zadaci