Liczba funkcji rosnących

[matematykipatyk]

Dlaczego funkcji rosnących \(\displaystyle{ f:\{1,...,k\} \rightarrow \{1,...,n\}}\) jest \(\displaystyle{ \binom{n}{k}}\) ?

[janusz47]

Co to są funkcje rosnące \(\displaystyle{ f: \{1,2,...,k \}\rightarrow \{1,2,...,n\}?}\)

[karolex123]

Wskazówka: ile jest różnowartościowych funkcji \(\displaystyle{ f:\{1,...,k\} \rightarrow \{1,...,n\}}\)

[matematykipatyk]

Różnowartościowych jest tyle ile wariacji bez powtórzeń czyli

\(\displaystyle{ V ^{k} _{n}= \frac{n!}{(n-k)!}}\)

[AiDi]

Ja może inaczej podejdę (choć w sumie nie wiem czy tak inaczej): zbiór wartości tej funkcji musi być \(\displaystyle{ k}\)-elementowy i funkcja musi być różnowartościowa by mogła być rosnąca. Na ile sposobów można wybrać \(\displaystyle{ k}\) różnych liczb z \(\displaystyle{ n}\)-elementowej przeciwdziedziny? To są nasi kandydaci na wartości funkcji. I teraz: na ile sposobów można tych kandydatów ustawić w ciąg rosnący?

[karolex123]

Ok, ja miałem takie podejście; skoro mamy \(\displaystyle{ \frac{n!}{(n-k)!}}\) funkcji różnowartościowych, to łatwo zobaczyć że permutując taki ciąg otrzymamy także ciąg różnowartościowy. Z tych \(\displaystyle{ k!}\) permutacji ciągu różnowartościowego, dokładnie jedna jest ciągiem rosnącym. Stąd ciągów rosnących mamy \(\displaystyle{ \frac{n!}{(n-k)!k!}}\)

[arek1357]

Akurat policzyłeś ilość funkcji niemalejących a nie silnie rosnących na mój gust nie powinno być punktów stałych...

[Jan Kraszewski]

Funkcje niemalejące, które nie są silnie rosnące, nie są różnowartościowe...

JK

[matematykipatyk]

Czy mógłby ktoś napisać jak należy rozwiązać to zadanie. Jak na razie gubię się w podpowiedziach.

[arek1357]

\(\displaystyle{ f(i)>i}\) - powinno być

[janusz47]

Kluczem do dowodu jest fakt, że żadne dwie wartości funkcji \(\displaystyle{ f}\) nie mogą być takie same i obraz czyli zbiór wartości funkcji ściśle rosnącej musi zawierać dokładnie \(\displaystyle{ k}\) elementów w rosnącym porządku. Stąd wynika, że liczba ściśle rosnących funkcji jest równa liczbie wyboru \(\displaystyle{ k}\) elementów spośród \(\displaystyle{ n}\) to jest \(\displaystyle{ {n\choose k}.}\)

Proszę przeprowadzić dokładny dowód metodą indukcji zupełnej, przyjmując dwa zbiory \(\displaystyle{ X, Y}\) zawierające odpowiednio \(\displaystyle{ k}\) elementów i \(\displaystyle{ n}\) elementów.

[Jan Kraszewski]

Jak na razie gubię się w podpowiedziach.

Pomysł karolexa123

Ok, ja miałem takie podejście; skoro mamy \(\displaystyle{ \frac{n!}{(n-k)!}}\) funkcji różnowartościowych, to łatwo zobaczyć że permutując taki ciąg otrzymamy także ciąg różnowartościowy. Z tych \(\displaystyle{ k!}\) permutacji ciągu różnowartościowego, dokładnie jedna jest ciągiem rosnącym. Stąd ciągów rosnących mamy \(\displaystyle{ \frac{n!}{(n-k)!k!}}\)

był naprawdę zgrabny i - jeśli wiesz, ile jest funkcji różnowartościowych - kończył dowód.

JK

[karolex123]

arek1357, czy ciąg \(\displaystyle{ \left( n\right) _{n \in \mathbb N}}\) chcemy nazwać stałym, bo każda liczba naturalna jest punktem stałym? Przede wszystkim czy nie jest on przez to ściśle rosnący??

[arek1357]

W sumie masz rację ale fajnie by było jeszcze znaleźć wzór dla funkcji takiej jak ja zaproponowałem...

[kerajs]

Czy mógłby ktoś napisać jak należy rozwiązać to zadanie. Jak na razie gubię się w podpowiedziach.

AiDi już napisał rozwiązanie: Wybierasz \(\displaystyle{ k}\) z \(\displaystyle{ n}\) wartości funkcji (takich wyborów jest \(\displaystyle{ {n \choose k}}\) ), ale takie przypisanie ich do argumentów aby funkcja była rosnąca jest tylko jedno. Stąd ilość funkcji rosnących to \(\displaystyle{ {n \choose k}}\)
Karolex także je podał (spójrz na fragment cytowany przez admina).

fajnie by było jeszcze znaleźć wzór dla funkcji takiej jak ja zaproponowałem...

To te funkcje gdzie \(\displaystyle{ f(1) \neq 1}\). Jest ich \(\displaystyle{ {n \choose k} - {n-1 \choose k-1}= {n-1 \choose k-1} \left( \frac{n}{k}-1 \right)}\)