Średnia liczba punktów stałych w permutacji zbioru n-elementowego

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
KonradZ
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 27 mar 2023, o 23:01
Płeć: Mężczyzna
wiek: 19

Średnia liczba punktów stałych w permutacji zbioru n-elementowego

Post autor: KonradZ »

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ć?
Ostatnio zmieniony 28 mar 2023, o 00:01 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
FasolkaBernoulliego
Użytkownik
Użytkownik
Posty: 157
Rejestracja: 23 sty 2020, o 16:16
Płeć: Mężczyzna
wiek: 30
Podziękował: 14 razy
Pomógł: 18 razy

Re: Średnia liczba punktów stałych w permutacji zbioru n-elementowego

Post autor: FasolkaBernoulliego »

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.
KonradZ
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 27 mar 2023, o 23:01
Płeć: Mężczyzna
wiek: 19

Re: Średnia liczba punktów stałych w permutacji zbioru n-elementowego

Post autor: KonradZ »

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?
3a174ad9764fefcb
Użytkownik
Użytkownik
Posty: 287
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 40
Podziękował: 3 razy
Pomógł: 41 razy

Re: Średnia liczba punktów stałych w permutacji zbioru n-elementowego

Post autor: 3a174ad9764fefcb »

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)!\).
ODPOWIEDZ