Znajdz interpretacje kombinatoryczna

[teczowyplacek]

\(\displaystyle{ \sum_{k=0}^{n} {n -1 \choose k - 1} n^{n-k}k! = n^{n}}\)


Probowalem wybrac to zinterpretowac na funkcjach. Znalezc jakies "kodowanie" np. wybieranie wartosci \(\displaystyle{ f}\) w punkcie \(\displaystyle{ k}\), ale nie moge stworzyc pewnych funkcji, a niektore sie powtarzaja

[Mruczek]

\(\displaystyle{ \sum_{k=0}^{n} {n -1 \choose k - 1} n^{n-k}k!= \sum_{k=0}^{n} {n \choose k} \cdot \frac{k}{n} \cdot n^{n-k}k! = \sum_{k=0}^{n} {n \choose k} k! \cdot k \cdot n^{n-k-1}}\)

Zliczamy funkcje ze zbioru \(\displaystyle{ n}\)-elementowego w ten sam zbiór \(\displaystyle{ n}\)-elementowy, które są różnowartościowe na pierwszych \(\displaystyle{ k}\) pozycjach, na pozycji \(\displaystyle{ k + 1}\) mają wartość taką samą jak na którejś z wcześniejszych \(\displaystyle{ k}\) pozycji i dowolną wartość na pozostałych późniejszych \(\displaystyle{ n - k - 1}\) pozycjach. Wartości \(\displaystyle{ k}\) pozycji różnowartościowych wybieramy na \(\displaystyle{ {n \choose k}}\) sposobów, permutujemy je na \(\displaystyle{ k!}\) sposobów, potem na \(\displaystyle{ k}\) sposobów wybieramy jedną z poprzednich \(\displaystyle{ k}\) wartości, która ma się powtórzyć, a następnie dla każdej z \(\displaystyle{ n - k - 1}\) pozostałych pozycji wybieramy dowolną wartość na \(\displaystyle{ n}\) sposobów, czyli łącznie na \(\displaystyle{ n^{n-k-1}}\) sposobów. W ten sposób zliczyliśmy wszystkie możliwe funkcje ze zbioru \(\displaystyle{ n}\)-elementowego w zbiór \(\displaystyle{ n}\)-elementowy, czyli \(\displaystyle{ n^{n}}\) funkcji, cnd.

Super zadanko!!!

[teczowyplacek]

Dziekuje bardzo, wiedzialem ze trzeba zrobic to roznowartosciowosc, ale wlasnie zabraklo mi tej \(\displaystyle{ k+1}\) pozycji czyli wybieranie jednej z tych wartosci, ktora juz uzylismy. Zadanie pochodzi z bajek kombinatorycznych