Reguła Catalana
-
mol_ksiazkowy
- Użytkownik
- Posty: 13537
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3436 razy
- Pomógł: 812 razy
Reguła Catalana
Udowodnić, że \(\displaystyle{ {m+n \choose m}}\) dzieli \(\displaystyle{ {2m \choose m} {2n \choose n} }\).
-
arek1357
Re: Reguła Catalana
Wystarczy udowodnić, że:
\(\displaystyle{ \frac{\left( 2m\right)! \left( 2n\right)! }{n!m!(n+m)!} }\)
że ta liczba jest całkowita...
z twierdzenia o wykładnikach w silni wiadomo, że:
licznik:
\(\displaystyle{ w_{\left( 2m\right)!}=\left\lfloor \frac{2m}{p} \right\rfloor+\left\lfloor \frac{2m}{p^2} \right\rfloor+... \infty }\)
\(\displaystyle{ w_{\left( 2n\right)!}=\left\lfloor \frac{2n}{p} \right\rfloor+\left\lfloor \frac{2n}{p^2} \right\rfloor+... \infty }\)
mianownik:
\(\displaystyle{ w_{\left( m\right)!}=\left\lfloor \frac{m}{p} \right\rfloor+\left\lfloor \frac{m}{p^2} \right\rfloor+... \infty }\)
\(\displaystyle{ w_{\left( n\right)!}=\left\lfloor \frac{n}{p} \right\rfloor+\left\lfloor \frac{n}{p^2} \right\rfloor+... \infty }\)
\(\displaystyle{ w_{\left( m+n\right)!}=\left\lfloor \frac{m+n}{p} \right\rfloor+\left\lfloor \frac{m+n}{p^2} \right\rfloor+... \infty }\)
a podzielność wynika z nierówności, która zresztą bardzo łatwo dowieść:
\(\displaystyle{ \left\lfloor 2x \right\rfloor + \left\lfloor 2y \right\rfloor \ge \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left\lfloor x+y \right\rfloor}\)
\(\displaystyle{ \frac{\left( 2m\right)! \left( 2n\right)! }{n!m!(n+m)!} }\)
że ta liczba jest całkowita...
z twierdzenia o wykładnikach w silni wiadomo, że:
licznik:
\(\displaystyle{ w_{\left( 2m\right)!}=\left\lfloor \frac{2m}{p} \right\rfloor+\left\lfloor \frac{2m}{p^2} \right\rfloor+... \infty }\)
\(\displaystyle{ w_{\left( 2n\right)!}=\left\lfloor \frac{2n}{p} \right\rfloor+\left\lfloor \frac{2n}{p^2} \right\rfloor+... \infty }\)
mianownik:
\(\displaystyle{ w_{\left( m\right)!}=\left\lfloor \frac{m}{p} \right\rfloor+\left\lfloor \frac{m}{p^2} \right\rfloor+... \infty }\)
\(\displaystyle{ w_{\left( n\right)!}=\left\lfloor \frac{n}{p} \right\rfloor+\left\lfloor \frac{n}{p^2} \right\rfloor+... \infty }\)
\(\displaystyle{ w_{\left( m+n\right)!}=\left\lfloor \frac{m+n}{p} \right\rfloor+\left\lfloor \frac{m+n}{p^2} \right\rfloor+... \infty }\)
a podzielność wynika z nierówności, która zresztą bardzo łatwo dowieść:
\(\displaystyle{ \left\lfloor 2x \right\rfloor + \left\lfloor 2y \right\rfloor \ge \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left\lfloor x+y \right\rfloor}\)
