Składanie permutacji - powtarzalność
: 6 cze 2011, o 23:23
Rozważam taki problem: mamy dowolną permutację zbioru \(\displaystyle{ Z=\left\{ 1,2,3,..,n\right\}}\). Teraz złożymy ją z ją samą. Następnie permutację, którą otrzymamy, składamy z daną na początku, i tak w kółko. Zauważyłem, że po pewnym czasie wyniki zaczynają się powtarzać (niestety nie umiem tego udowodnić). Pytanie brzmi: czy mając daną liczbę \(\displaystyle{ n}\) możemy policzyć po ilu złożeniach, w najgorszym wypadku, wyniki zaczną się powtarzać? Dajmy taki przykład:
permutacja: \(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right)}\)
i oto co robimy:
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 7 & 5 & 6\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 7 & 5 & 6\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 5 & 6 & 7\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 5 & 6 & 7\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 6 & 7 & 5\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 6 & 7 & 5\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 7 & 5 & 6\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 7 & 5 & 6\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right)}\)
czy wszystko jest poprawne pod względem zapisu? od tej chwili wyniki zaczynają się powtarzać. Główny problem to wyznaczanie liczby na \(\displaystyle{ i}\)-tym miejscu w permutacji po \(\displaystyle{ k}\)-tym jej złożeniu tak jak w przykładzie, ale najpierw chciałem się skupić nad tym czy jest możliwe oszacowanie po ilu złożeniach, w najgorszym przypadku, wyniki zaczną się powtarzać, mając dane \(\displaystyle{ n}\). Być może niepotrzebnie, łatwiej jest rozwiązać od razu główny problem? Bo rozumiem, że jeśli na wejściu by była inna permutacja (z tym samym \(\displaystyle{ n}\)) to wyniki mogłyby zacząć się powtarzać po innej liczbie złożeń..
Jakieś wskazówki co do składania permutacji?
permutacja: \(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right)}\)
i oto co robimy:
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 7 & 5 & 6\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 7 & 5 & 6\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 5 & 6 & 7\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 5 & 6 & 7\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 6 & 7 & 5\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 6 & 7 & 5\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 7 & 5 & 6\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 7 & 5 & 6\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right)}\)
czy wszystko jest poprawne pod względem zapisu? od tej chwili wyniki zaczynają się powtarzać. Główny problem to wyznaczanie liczby na \(\displaystyle{ i}\)-tym miejscu w permutacji po \(\displaystyle{ k}\)-tym jej złożeniu tak jak w przykładzie, ale najpierw chciałem się skupić nad tym czy jest możliwe oszacowanie po ilu złożeniach, w najgorszym przypadku, wyniki zaczną się powtarzać, mając dane \(\displaystyle{ n}\). Być może niepotrzebnie, łatwiej jest rozwiązać od razu główny problem? Bo rozumiem, że jeśli na wejściu by była inna permutacja (z tym samym \(\displaystyle{ n}\)) to wyniki mogłyby zacząć się powtarzać po innej liczbie złożeń..
Jakieś wskazówki co do składania permutacji?