Uzasadnij metodami kombinatorycznymi

[Calasilyar]

Uzasadnij tożsamość metodami kombinatorycznymi:
\(\displaystyle{ {n\choose k} + {n\choose k+1} = {n+1 \choose k+1}}\)

[jarekp]

masz n+1 osób: n chińczyków i eskimosa:)

na ile sposobów możesz wybrać spośród nich k+1 osobową grupę?
na \(\displaystyle{ {n+1 \choose k+1}}\) sposobów.

Policzmy to teraz inaczej:
mamy \(\displaystyle{ {n\choose k+1}}\) grup składających się z samych chińczyków i \(\displaystyle{ {n\choose k}}\) grup składających się z eskimosa i k chińczyków.

więc \(\displaystyle{ {n\choose k} + {n\choose k+1} = {n+1 \choose k+1}}\)

[Calasilyar]

Policzmy to teraz inaczej:

Mógłbyś to rozpisać bardziej elementarnie?

[jarekp]

liczymy wybór k+1 grup na dwa sposoby:
pierwszy sposób to oczywiście \(\displaystyle{ {n+1 \choose k+1}}\)

teraz drugi sposób:
wybrane grupy możemy podzielić na dwa przypadki:
1.w grupie znajduje się eskimos i k chińczyków- tych grup jest \(\displaystyle{ {n\choose k}}\)
2.grupa składa się z samych chińczyków- takich grup jest \(\displaystyle{ {n\choose k+1}}\)

ponieważ wynik nie zależy od sposobu liczenia to \(\displaystyle{ {n\choose k} + {n\choose k+1} = {n+1 \choose k+1}}\)

[Calasilyar]

Już rozumiem, dzięki za pomoc