Matematyka.pl

Zadanie na średnią liczbę punktów stały w permutacji zbioru \(\displaystyle{ m}\)-elementowego. Mam do tego dwie wskazówki:
1. Zbadanie, wypisując wszystkie permutacje, przypadki \(\displaystyle{ n = 3, 4}\) i postaw hipotezę jaki będzie wynik (hipoteza to, że średnia ta jest równa 1).
2. Ile jest permutacji mających dokładnie k punktów stałych?

Z drugiego punktu korzystając z zasady wychodzi mi \(\displaystyle{ n! \cdot \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k!} }\). Problem mam jednak z odniesieniem tego w jakikolwiek sposób do sumy wszystkich możliwych punktów stałych danej permutacji. Wszystko co znajdowałem w Internecie dotyczyło elementów losowych i wartości oczekiwanej, co wykracza poza moją wiedzę i muszę poradzić sobie bez tego.

Szukam jakiejś podpowiedzi, z czego powinienem tu skorzystać?

Cześć, pierwszy problem który widzę to podany przez Ciebie wzór nie zależy od k, więc jak może opisywać liczbę permutacji mających dokładnie k punktów stałych? Przecież z pewnością wartość ta jest różna w zależności od k.

Jeżeli uda Ci się wyznaczyć wzór na liczbę permutacji mających dokładnie k punktów stałych, powiedzmy \(\displaystyle{ s(k)}\) to średnia liczba punktów stałych to będzie \(\displaystyle{ \sum_{k=0}^{n} k s(k) }\) podzielona przez liczbę wszystkich permutacji. Policzenie tego pewnie nie będzie oczywiste, ale nie wymaga wiedzy z rachunku prawdopodobieństwa.

Znalazłem wzór na średnią liczbę punktów stałych \(\displaystyle{ \sum _{k=1}^n\left(\frac{1}{k!}\cdot \left(\sum _{i=0}^{n-k}\frac{\left(-1\right)^i}{i!}\right)\cdot k\right) }\) wyznaczyłem go z wzoru na liczbę permutacji z \(\displaystyle{ k}\)-punktami stałymi który był równy \(\displaystyle{ \frac{n!}{k!} \cdot \sum_{i=0}^{n-k} \frac{(-1)^{i}}{i!} }\).
I tu zaczyna się problem próbowałem udowodnić, że średnia liczba punktów stałych to \(\displaystyle{ 1}\) z indukcji. Tylko raz "udało" mi się to doprowadzić do końca, co skończyło się na \(\displaystyle{ 1 \cdot \frac{1}{r+1} }\), gdzie \(\displaystyle{ r \ge n_{0}=1 }\) co nic mi nie daje. Z drugiej strony gdy próbowałem to uprościć nie doprowadzało mnie to do niczego co by ułatwiało sprawę.

Powinienem trzymać się indukcji? Czy może da się faktycznie uprościć ten wzór?

1. Wartość oczekiwana sumy zmiennych losowych jest sumą wartości oczekiwanych, dlatego wynikiem jest po prostu \(\frac1n+\frac1n+\ldots+\frac1n=n\cdot\frac1n=1\).

Dodano po 15 godzinach 41 minutach 26 sekundach:

KonradZ pisze: 27 mar 2023, o 23:58 Wszystko co znajdowałem w Internecie dotyczyło elementów losowych i wartości oczekiwanej, co wykracza poza moją wiedzę i muszę poradzić sobie bez tego.

Czyli mówiąc innymi słowami: jedynka jest punktem stałym \((n-1)!\) razy, dwójka jest punktem stałym w \((n-1)!\) permutacjach, itd. Łączna liczba punktów stałych we wszystkich permutacjach jest więc równa \(n\cdot(n-1)!\).