Stosując podwójne zliczanie udowodnić

[dram]

Witam.

Nie mam za bardzo pomysłu jak zabierać się do takich zadań:

Rozwiązanie algebraiczne się nie liczy - należy rozwiązać to przez wymyślenie 'historyjki'.

\(\displaystyle{ {2n \choose 2} = 2 * {n \choose 2} + n ^{2}}\)

[Peter Zof]

Mając \(\displaystyle{ 2n}\) obiektów podziel je na dwie grupki \(\displaystyle{ \mathcal{G}_1}\) oraz \(\displaystyle{ \mathcal{G}_2}\) tak aby każda z nich miała dokładnie \(\displaystyle{ n}\) obiektów. Teraz należy popatrzeć na to jak za pomocą takiej struktury opisać 2-kombinacje \(\displaystyle{ 2n}\) obiektów. Wybierając dwa obiekty z wszystkich może się zdarzyć tak, że:

(1) Oba zostały wybrane z grupy \(\displaystyle{ \mathcal{G}_1}\),
(2) Oba zostały wybrane z grupu \(\displaystyle{ \mathcal{G}_2}\),
(3) Jeden został wybrany z pierwszej, a drugi z drugiej.

Powyższe sytuacje rozbijają wszystkie możliwe wybory. Teraz na podstawie tego może uda Ci się rozwiązać problem.

[dram]

1 i 2 sytuacja którą opisałeś, to 1 składnik sumy

Drugi składnik mozna rozbić na \(\displaystyle{ {n \choose 1} {n \choose 1}}\)
I on przedstawia sytuacje 3.

Więc problem juz chyba jest rozwiązany?

[Peter Zof]

Tak, a jako że są to parami różne sytuacje to liczba wszystkich 2-kombinacji jest równa sumie 2-kombinacji z każdego przypadku