Liczba f.rosnących i f.malejących
-
aolo23
- Użytkownik
- Posty: 307
- Rejestracja: 5 sty 2016, o 13:01
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 118 razy
- Pomógł: 2 razy
Liczba f.rosnących i f.malejących
Ile jest funkcji rosnących i malejących : \(\displaystyle{ f:X \rightarrow Y}\), gdzie \(\displaystyle{ \left| X\right| = n}\) , \(\displaystyle{ \left| Y\right| = k}\)
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Liczba f.rosnących i f.malejących
Żeby funkcja była ściśle rosnąca musi być : \(\displaystyle{ k \ge n}\), jest tylko jeden układ (spośród wszystkich permutacji) w podzbiorze zbioru \(\displaystyle{ Y, k}\) elementowym, żeby funkcja była rosnąca...
Czyli powinno być:
\(\displaystyle{ {k \choose n}}\)
Podobnie z malejącymi.
Oczywiście ciekawiej by było z funkcjami niemalejącymi...
Ja to jeszcze rozbuduję o funkcje niemalejące(nierosnące)...
Podzielmy zbiór \(\displaystyle{ A}\) o mocy \(\displaystyle{ n}\) na \(\displaystyle{ k}\) niepustych podzbiorów:
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=n}\)
\(\displaystyle{ |A_{i}|=x_{i}}\)
robimy takie przegródki żeby można było mówić o niemalejących funkcjach:
\(\displaystyle{ 1|23|45}\)
jest tu np. trzy przegródki i każda ma być niepusta liczb nie permutujemy...
jest tego:
\(\displaystyle{ {n-1 \choose k-1}}\)
I teraz ze zbioru B wybieramy podzbiór \(\displaystyle{ k}\) - elementowy
na sposobów:
\(\displaystyle{ {m \choose k}}\)
Teraz tworzymy bijekcje między.: \(\displaystyle{ A_{i}}\) a wybranymi \(\displaystyle{ k}\) - elementami zbioru \(\displaystyle{ B}\), Bijekcja jest tylko jedna.
Czyli tyle bijekcji ile podziałów zbioru\(\displaystyle{ A}\) na\(\displaystyle{ k}\) podzbiorów
mamy:
\(\displaystyle{ {n-1 \choose k-1} {m \choose k}}\)
całość obkładamy znakiem sumy:
\(\displaystyle{ \sum_{k=1}^{n}{n-1 \choose k-1} {m \choose k}}\)
I mamy wzór na wszystkie niemalejące funkcje zbioru\(\displaystyle{ A}\) w zbiór \(\displaystyle{ B}\)
Nierosnących jest tyle samo, częścią wspólną nierosnących i niemalejących jest oczywiście zbiór funkcji stałych, a jest ich - \(\displaystyle{ m}\)
Ale wszystkich funkcji jest:
\(\displaystyle{ m^n}\)
Więc pozostaje obliczyć ile jest funkcji pozostałych, czyli:
\(\displaystyle{ P=m^n-2\sum_{k=1}^{n}{n-1 \choose k-1} {m \choose k}+m}\)
Przykład:
\(\displaystyle{ A=\left\{ 1,2,3\right\} , B=\left\{ 1,2\right\}}\)
Niemalejące:
\(\displaystyle{ \left\{ 1,2,3\right\} \rightarrow 1}\)
\(\displaystyle{ \left\{ 1,2,3\right\} \rightarrow 2}\)
\(\displaystyle{ \left\{ 1,2\right\} \rightarrow 1 , \left\{ 3\right\} \rightarrow 2}\)
\(\displaystyle{ \left\{ 1\right\} \rightarrow 1 , \left\{ 2,3\right\} \rightarrow 2}\)
ściśle rosnących brak bo.: \(\displaystyle{ n>m}\) , stałych jest dwie , i dwie niemalejące...
A teraz ze wzoru:
\(\displaystyle{ \sum_{k=1}^{n}{n-1 \choose k-1} {m \choose k} , n=3, m=2}\)
mamy:
\(\displaystyle{ \sum_{k=1}^{3}{2 \choose k-1} {2 \choose k}= {2 \choose 0} {2 \choose 1}+ {2 \choose 1} {2 \choose 2}+ {2 \choose 2} {2 \choose 3}=2+2+0=4}\)
Co się zgadza z doświadczeniem...
Funkcji nierosnących będzie też cztery,czyli razem:
\(\displaystyle{ 4+4-2=6}\)
Wszystkich funkcji będzie:
\(\displaystyle{ 2^3=8}\)
więc pozostałych będzie:
\(\displaystyle{ P=8-6=2}\)
Pozostałe to:
\(\displaystyle{ \left\{ 1,3\right\} \rightarrow 1 , \left\{ 2\right\} \rightarrow 2}\)
\(\displaystyle{ \left\{ 1,3\right\} \rightarrow 2 , \left\{ 2\right\} \rightarrow 1}\)
I to na tyle...
Czyli powinno być:
\(\displaystyle{ {k \choose n}}\)
Podobnie z malejącymi.
Oczywiście ciekawiej by było z funkcjami niemalejącymi...
Ja to jeszcze rozbuduję o funkcje niemalejące(nierosnące)...
Podzielmy zbiór \(\displaystyle{ A}\) o mocy \(\displaystyle{ n}\) na \(\displaystyle{ k}\) niepustych podzbiorów:
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=n}\)
\(\displaystyle{ |A_{i}|=x_{i}}\)
robimy takie przegródki żeby można było mówić o niemalejących funkcjach:
\(\displaystyle{ 1|23|45}\)
jest tu np. trzy przegródki i każda ma być niepusta liczb nie permutujemy...
jest tego:
\(\displaystyle{ {n-1 \choose k-1}}\)
I teraz ze zbioru B wybieramy podzbiór \(\displaystyle{ k}\) - elementowy
na sposobów:
\(\displaystyle{ {m \choose k}}\)
Teraz tworzymy bijekcje między.: \(\displaystyle{ A_{i}}\) a wybranymi \(\displaystyle{ k}\) - elementami zbioru \(\displaystyle{ B}\), Bijekcja jest tylko jedna.
Czyli tyle bijekcji ile podziałów zbioru\(\displaystyle{ A}\) na\(\displaystyle{ k}\) podzbiorów
mamy:
\(\displaystyle{ {n-1 \choose k-1} {m \choose k}}\)
całość obkładamy znakiem sumy:
\(\displaystyle{ \sum_{k=1}^{n}{n-1 \choose k-1} {m \choose k}}\)
I mamy wzór na wszystkie niemalejące funkcje zbioru\(\displaystyle{ A}\) w zbiór \(\displaystyle{ B}\)
Nierosnących jest tyle samo, częścią wspólną nierosnących i niemalejących jest oczywiście zbiór funkcji stałych, a jest ich - \(\displaystyle{ m}\)
Ale wszystkich funkcji jest:
\(\displaystyle{ m^n}\)
Więc pozostaje obliczyć ile jest funkcji pozostałych, czyli:
\(\displaystyle{ P=m^n-2\sum_{k=1}^{n}{n-1 \choose k-1} {m \choose k}+m}\)
Przykład:
\(\displaystyle{ A=\left\{ 1,2,3\right\} , B=\left\{ 1,2\right\}}\)
Niemalejące:
\(\displaystyle{ \left\{ 1,2,3\right\} \rightarrow 1}\)
\(\displaystyle{ \left\{ 1,2,3\right\} \rightarrow 2}\)
\(\displaystyle{ \left\{ 1,2\right\} \rightarrow 1 , \left\{ 3\right\} \rightarrow 2}\)
\(\displaystyle{ \left\{ 1\right\} \rightarrow 1 , \left\{ 2,3\right\} \rightarrow 2}\)
ściśle rosnących brak bo.: \(\displaystyle{ n>m}\) , stałych jest dwie , i dwie niemalejące...
A teraz ze wzoru:
\(\displaystyle{ \sum_{k=1}^{n}{n-1 \choose k-1} {m \choose k} , n=3, m=2}\)
mamy:
\(\displaystyle{ \sum_{k=1}^{3}{2 \choose k-1} {2 \choose k}= {2 \choose 0} {2 \choose 1}+ {2 \choose 1} {2 \choose 2}+ {2 \choose 2} {2 \choose 3}=2+2+0=4}\)
Co się zgadza z doświadczeniem...
Funkcji nierosnących będzie też cztery,czyli razem:
\(\displaystyle{ 4+4-2=6}\)
Wszystkich funkcji będzie:
\(\displaystyle{ 2^3=8}\)
więc pozostałych będzie:
\(\displaystyle{ P=8-6=2}\)
Pozostałe to:
\(\displaystyle{ \left\{ 1,3\right\} \rightarrow 1 , \left\{ 2\right\} \rightarrow 2}\)
\(\displaystyle{ \left\{ 1,3\right\} \rightarrow 2 , \left\{ 2\right\} \rightarrow 1}\)
I to na tyle...