Matematyka.pl

Niech \(\displaystyle{ S= \{ 1,...,n \}}\) oraz \(\displaystyle{ k \in S}\). Udowodnić, że istnieje dokładnie \(\displaystyle{ kn^{n-1}}\) funkcji \(\displaystyle{ f: S \to S}\) takich, że dla dowolnego \(\displaystyle{ s \in S}\) istnieje \(\displaystyle{ j \geq 0}\) takie, że \(\displaystyle{ f^{j} (s) \leq k }\) (\(\displaystyle{ j }\) ta iteracja \(\displaystyle{ f}\)).

Troszkę trzeba nad tym zadaniem się pochylić, prowadzi ono do kilku ciekawych spostrzeżeń, otóż można na to popatrzeć pod kątem szukania funkcji,
które po pewnej skończonej ilości iteracji zbiegają się do jakiegoś podzbioru i tak to zadanie zaczynałem.

Otóż interesują nas funkcje f takie, że:

\(\displaystyle{ f:N=\left\{ 1,2,...k,k+1,k+2,...,n\right\} \rightarrow N-K=\left\{ 1,...,k\right\} }\)

Najpierw policzmy funkcje wszystkie:

\(\displaystyle{ f:K=\left\{ 1,2,...,k\right\} \rightarrow N}\)

Jest ich oczywiście:

\(\displaystyle{ n^k}\)

Mamy do udowodnienia, że wszystkich funkcji:

\(\displaystyle{ f: N-K=\left\{ k+1,k+2,...,n\right\} \rightarrow K=\left\{ 1,2,...,k\right\} }\)

jest:

\(\displaystyle{ k \cdot n^{n-k-1}}\)

Jest to o tyle ciekawe, że mamy policzyć ile jest funkcji, których "basenem" przyciągania jest właśnie zbiór \(\displaystyle{ K}\)
Funkcji, które po pewnej ilości złożeń wylądują w zbiorze \(\displaystyle{ K}\) - tak właśnie treść zadania można tłumaczyć...

Pokażę najpierw jak do tego podchodziłem na początku, otóż:

Najpierw próbowałem dzielić zbiór \(\displaystyle{ N-K}\) na niepuste podzbiory. Pokażę tu na przykładzie o co mi biegało:

\(\displaystyle{ K=\left\{ 1,2,3\right\} }\)

\(\displaystyle{ N-K=\left\{ 4,5,6\right\} }\)

Teraz dzielę \(\displaystyle{ N-K}\) na podzbiory, zbiór \(\displaystyle{ K}\) jest basenem przyciągania:

1) \(\displaystyle{ \left\{ .\right\} \rightarrow \left\{ ..\right\} \rightarrow \left\{ 1,2,3\right\} }\)

2) \(\displaystyle{ \left\{ ..\right\} \rightarrow \left\{ .\right\} \rightarrow \left\{ 1,2,3\right\} }\)

3) \(\displaystyle{ \left\{ \right\} \rightarrow \left\{ .\right\} \rightarrow \left\{ .\right\} \rightarrow \left\{ 1,2,3\right\} }\)

4) \(\displaystyle{ \left\{ ...\right\} \rightarrow \left\{ 1,2,3\right\} }\)

Teraz zliczam przypadki i funkcje według podziału:

w 1) jest możliwości:

\(\displaystyle{ 3 \cdot 2^1 \cdot 3^2=54}\) ponieważ tam gdzie kropeczki wstawiam wszystkie kombinacje:\(\displaystyle{ 4,5,6}\)

Jest trzy kombinacje potem zliczam funkcje z pierwszego zbioru do drugiego: \(\displaystyle{ 2^1}\) i z drugiego do trzeciego: \(\displaystyle{ 3^2}\)

Mnożę to i wychodzi:\(\displaystyle{ 54}\)

W ten sam sposób w 2) mam:

\(\displaystyle{ 3 \cdot 3^1=9}\)

w 3):

\(\displaystyle{ 3^3=27}\)

w 4):

\(\displaystyle{ 3! \cdot 3^1=18}\)

Po dodaniu wychodzi \(\displaystyle{ 108}\)

Sprawdzam, czy zgadza się ze wzorem:

\(\displaystyle{ k \cdot n^{n-k-1}=3 \cdot 6^{6-3-1}=108}\)

Co oczywiście jest prawdą i naprowadziło mnie to na wzór taki:

\(\displaystyle{ \sum_{r=1}^{n-k} \sum_{x_{1}+x_{2}+...+x_{r}+k=n}^{} x_{2}^{x_{1}} \cdot x_{3}^{x_{2}} \cdot ... \cdot x_{r}^{x_{r-1}} \cdot k^{x_{r}} \cdot \frac{(n-k)!}{x_{1}! \cdot x_{2}! \cdot ... \cdot x_{r}!} }\)

I to miało by być równe:

\(\displaystyle{ k \cdot n^{n-k-1}}\)

Nie zauważyłem tu sensownego dowodu więc zmieniłem podejście do zadania (może ktoś się pokusi)...

Najpierw troszkę inaczej sformułowałem treść zadania:

A mianowicie:

Ułożyłem troszkę inne zadanie:

Ile jest funkcji:

\(\displaystyle{ f: N=\left\{ 1,2,3,...,n \right\} \rightarrow N \cup B=\left\{ a_{1},a_{2},...,a_{k}\right\} , N \cap B=\emptyset}\)

Takich, że:

Dla każdego:

\(\displaystyle{ A \subset N}\)

\(\displaystyle{ f(A)}\) nie zawiera się w \(\displaystyle{ A}\)

Warunek ten jest gwarancją, że basenem przyciągania zbioru \(\displaystyle{ N}\) jest zbiór \(\displaystyle{ B}\)

Można to interpretować, że funkcje są nieporządkami na dowolnym podzbiorze: \(\displaystyle{ A \subset N}\)

I teraz nasunęła mi się rekurencja:

\(\displaystyle{ f(n,k)=k^n+k^{n-1} {n \choose 1}f(1,n-1)+k^{n-2} {n \choose 2} f(2,n-2)+...+k {n \choose n-1} f(n-1,1) }\)

Wytłumaczę dlaczego tak dla:

\(\displaystyle{ N= n=3, |B|=k}\)

Otóż mamy obliczyć:

\(\displaystyle{ f(3,k)}\)

Najpierw zliczamy ilość funkcji:

\(\displaystyle{ {1,2,3} \rightarrow B}\)

jest ich:

\(\displaystyle{ k^3}\)

Potem zliczam:

(*) \(\displaystyle{ \left\{ x,y\right\} \rightarrow B, x,y=1,2,3}\)

oraz:

(**) \(\displaystyle{ \left\{ .\right\} \rightarrow \left\{ 1,2,3\right\} }\)

Warto zauważyć, że przypadków (*) i (**) jest:

\(\displaystyle{ k^2 \cdot {3 \choose 1} f(1,2)}\)

funkcji:

\(\displaystyle{ \left\{ .\right\} \rightarrow \left\{ 1,2,3\right\} }\)

które nie są stałe na podzbiorze: \(\displaystyle{ {.}}\) jest dokładnie:

\(\displaystyle{ f(1,2)}\)

Ostatni przypadek:

\(\displaystyle{ \left\{ ..\right\} \rightarrow \left\{1,2,3 \right\} }\) - jest: \(\displaystyle{ f(2,1)}\) wyborów jest: \(\displaystyle{ {3 \choose 2} }\)

oraz:

\(\displaystyle{ \left\{ .\right\} \rightarrow B}\) - jest: \(\displaystyle{ k^1}\)

Co daje w trzecim przypadku:

\(\displaystyle{ k \cdot {3 \choose 2}f(2,1) }\)

Więc zliczając będzie:

\(\displaystyle{ f(3,k)=k^3+k^2 {3 \choose 1} f(1,2)+k^1 {3 \choose 2} f(2,1)}\)

Więc wzór:

\(\displaystyle{ f(n,k)=k^n+k^{n-1} {n \choose 1} f(1,n-1)+k^{n-2} {n \choose 2} f(2,n-2)+...k {n \choose n-1} f(n-1,1)=k \cdot (n+k)^{n-1}}\)

Lub zakładając w pierwszym kroku indukcyjnym prawdziwość dla:

\(\displaystyle{ f(x,r), x<n}\)

gdzie:

\(\displaystyle{ f(x,r)=r \cdot \left( x+r\right)^{x-1} }\)

\(\displaystyle{ f(n,k)=k^n+ {n \choose 1}(n-1)n^0k^{n-1}+ {n \choose 2}(n-2)n^1k^{n-2}+ {n \choose 3}(n-3)n^2k^{n-3}+...+{n \choose n-1}1 \cdot n^{n-2} \cdot k}\)

Winien być prawdziwy co można sprawdzić indukcją...

Więc trzeba udowodnić, że:

\(\displaystyle{ k^n+ {n \choose 1}(n-1)n^0k^{n-1}+ {n \choose 2}(n-2)n^1k^{n-2}+ {n \choose 3}(n-3)n^2k^{n-3}+...+{n \choose n-1}1 \cdot n^{n-2} \cdot k=k \cdot (n+k)^{n-1}}\)

Zauważmy, że trzeba wykazać iż:

\(\displaystyle{ k^{n-1}+ {n \choose 1}(n-1)k^{n-2}+ {n \choose 2}(n-2)nk^{n-3}+ {n \choose 3}(n-3)n^2k^{n-4}+...+ {n \choose n-1}n^{n-2}=}\)

\(\displaystyle{ =n^{n-1}+ {n-1 \choose 1}n^{n-2}k^1+ {n-1 \choose 2}n^{n-3}k^2+...+ {n-1 \choose n-2}nk^{n-2}+k^{n-1}=(n+k)^{n-1} }\)

Jest tu i tu tyle samo wyrazów i wystarczy zauważyć, że:

Pierwszy wyraz strony lewej jest równy ostatniemu wyrazowi strony prawej,
Drugi wyraz strony prawej to przedostatni wyraz strony lewej
itd....

Czyli wystarczy udowodnić, że:


\(\displaystyle{ {n \choose r}(n-r) \cdot n^{r-1}k^{n-r-1}= {n-1 \choose n-r-1}n^rk^{n-r-1} }\)

Lub prościej:


\(\displaystyle{ {n \choose r}(n-r) \cdot n^{r-1}= {n-1 \choose r}n^r /:n^{r-1} }\)

mamy do udowodnienia:


\(\displaystyle{ {n \choose r}(n-r)= {n-1 \choose r}n }\)

lub:

\(\displaystyle{ \frac{n!(n-r)}{(n-r)! \cdot r!}= \frac{(n-1)! \cdot n}{(n-r-1)! \cdot r!} }\)

równoważnie:

\(\displaystyle{ \frac{n!(n-r)}{(n-r-1)!(n-r)} = \frac{n!}{(n-r-1)!} }\)

a co jest prawdą wobec tego wzór indukcyjny i rekurencja są prawdziwe cnd...