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ć?
Średnia liczba punktów stałych w permutacji zbioru n-elementowego
Średnia liczba punktów stałych w permutacji zbioru n-elementowego
Ostatnio zmieniony 28 mar 2023, o 00:01 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
-
- 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
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.
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.
Re: Średnia liczba punktów stałych w permutacji zbioru n-elementowego
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?
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?
-
- 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
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:
Dodano po 15 godzinach 41 minutach 26 sekundach:
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)!\).