Točno
7. studenoga 2022. 23:46 (2 godine)

Dokaži kombinatornim argumentom:

\begin{enumerate} \item $$\binom{n}{k} = \binom{n}{n-k}$$ \item $$\sum_{k=0}^n \binom{n}{k} = 2^n$$ \item $$\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$$ \end{enumerate}

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Ocjene: (1)



Komentari:

Patrlk, 29. studenoga 2022. 23:41

Ok evo me nazad sa malo više znanja i pročitao sam zadatak.

2. 2^n označava broj podskupova skupa sa n stvari. (Hoćemo li ili nećemo uzeti broj u skup , n puta)

Sve podskupove možemo također dobiti ako od n elemenata uzmemo k elemenata od k = 0 do k = n.

3. U razredu sa n + 1 učenika stavimo jednog učenika kao predsjednika. I sad želimo poslat k učenika u ravnatelja. To možemo napravit tako da uzmemo k učenika od svih učenika bez predsjednika ili uzmemo k - 1 učenika sa predsjednikom.

Patrlk, 8. studenoga 2022. 22:52

Aha. Vjerovatno bi trebao počet malo više čitat.

MatesV13, 8. studenoga 2022. 21:02

Pa... ok, uistinu vrijedi, samo je to algebarski dokaz, ne kombinatornim argumentom XD

Dokaz kombinatornim argumentom bi išao nekako ovako: recimo da želim izabrati grupu od k natjecatelja iz razreda s n učenika. Mogu direktno izabrati k natjecatelja na \binom{n}{k} načina, ili mogu izabrati grupu od n-k koji neće ići na natjecanje na \binom{n}{n-k} načina. Sada bi na natjecanju još trebalo pokazati bijekciju između tih načina (tj. svaki način koji bira grupu natjecatelja postoji jedinstven način koji bira nenatjecatelje i obratno) da bude skroz formalno.

Više o dokazivanju kombinatornim argumentom ima ovdje: https://mnm.hr/wp-content/uploads/2015/10/Dokazivanje_kombinatornim_argumentom.pdf