Pokazać że odwzorowanie jest bijekcją

[pc]

Proszę pokazać że odwzorowanie \(\displaystyle{ B: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}}\) jest bijekcją:
\(\displaystyle{ B(n,m)= {n+m+1 \choose 2} +n}\)

Jeszcze napiszę jak rozpisałem ten symbol, bo być może pomyliłem się w tym:
\(\displaystyle{ \frac{(n+m+1)!}{2!((n+m+1)-2)!} = \frac{(n+m+1)!}{4(n+m-1)}}\)

Niestety oprócz tego prostego rozpisania nie wiem w jaki sposób dalej postępować, znam ogólne warunki suriekcji i injekcji, ale nie wiem jak je tutaj zastosować.

[Jan Kraszewski]

Źle rozpisałeś symbol, ma być

\(\displaystyle{ B(n,m)=\frac{(n+m)(n+m+1)}{2}+n}\).

JK

[pc]

Hm, a z jakiej definicji tutaj korzystasz?
W wikipedii jest taka:
\(\displaystyle{ {n \choose k} = \frac{n!}{k!(n-k)!}}\)

[Jan Kraszewski]

I z takiej korzystam (tak, jak i Ty). Natomiast zupełnie nie wiem, skąd to
\(\displaystyle{ \frac{(n+m+1)!}{4(n+m-1)}}\)
wziąłeś.

JK

[pc]

faktycznie pomyliłem się, 2! = 2, a nie 4
\(\displaystyle{ \frac{(n+m+1)!}{2(n+m-1)}}\)
Czy teraz jest prawidłowo?

-- 11 grudnia 2009, 12:39 --

Bo nie do końca wiem skąd się wzięło to co napisałeś powyżej. Mógłbym prosić o lepsze rozpisanie tego?

[Jan Kraszewski]

Zgubiłeś silnię.

\(\displaystyle{ \frac{(n+m+1)!}{2!((n+m+1)-2)!} = \frac{(n+m+1)!}{2(n+m-1)!}}\)

JK

[pc]

I teraz... w jaki sposób pokazać że jest to bijekcja?

[Jan Kraszewski]

Różnowartościowość np. tak.

Weź rosnącą funkcję pomocniczą \(\displaystyle{ f:\mathbb{N} \rightarrow \mathbb{N}}\), \(\displaystyle{ f(k)=\frac{(k+1)k}2}\). Zauważ, że \(\displaystyle{ f(n+m)\le B(n,m)<f(n+m+1)}\).
Jeśli zatem \(\displaystyle{ B(n,m)=B(a,b)}\), to musi być \(\displaystyle{ n+m=a+b}\) i już łatwo skończyć.

To, że jest "na" też można pokazać korzystając funkcji pomocniczej.

JK