kolejne permutacje idą mi na przemian, nie wiem dlaczego, nie umiem udowodnić

2012.08.20 00:57 kolejne permutacje idą mi na przemian, nie wiem dlaczego, nie umiem udowodnić

Czasem potrzebuję w prosty sposób - mając pod ręką tylko papier i długopis, albo i tego nie - przejrzeć wszystkie permutacje na jakimś zbiorze. Ja wtedy stosuję taki sposób.
Dajmy na to, że chcę przejrzeć wszystkie permutacje zbioru (1, 2, 3, 4). Robię taki (w tym przypadku dwudziestoczteroelementowy) ciąg ciągów czteroliczbowych:

Jak widać, każdy kolejny czteroelementowy ciąg tworzę na podstawie poprzedniego tak, że pierwszą (z lewej) liczbę zwiększam o jeden modulo cztery. Kiedy ta liczba zmienia się z wartości maksymalnej z powrotem w jeden, to kolejną, drugą (z lewej) liczbę zwiększam o jeden modulo trzy (trochę jak w liczniku wody w łazience, tylko tam wszystkie pozycje mają to samo modulo). Kiedy ta druga liczba zmienia się z wartości maksymalnej z powrotem w jeden, to kolejną, trzecią (z lewej) liczbę zwiększam o jeden modulo dwa. Kiedy ta trzecia liczba miałaby się zmienić z wartości maksymalnej z powrotem w jeden, to już jest koniec. Zauważcie, że przejrzenie tych dwudziestu czterech ciągów liczb nie wymaga dużej pamięci - bo trzeba pamiętać tylko poprzednią liczbę.
Każdy z tych czteroliczbowych ciągów można zmienić w permutację na zbiorze (1, 2, 3, 4) w sposób, który przedstawię na przykładzie ciągu 1 3 2 1. Zaczynam od tego, że mam cztery liczby do brania - 1, 2, 3, 4. Na początek wszystkie są wolne (niewykorzystane). Najpierw ustalam, jaka będzie wartość mojej permutacji dla argumentu 1 (po kolei idę z argumentami). W tym celu patrzę, jaka jest pierwsza (pierwsza, bo jestem przy argumencie 1) liczba czteroliczbowego ciągu - jest to jeden. To znaczy, że moja permutacja przeprowadza argument 1 w pierwszą (to "pierwszą" wzięło się z tego pierwszego "1" z czteroliczbowego ciągu) wolną liczbę z tych czterech liczb do brania. Pierwsza wolna liczba do brania to 1, więc moja permutacja dla argumentu 1 daje wartość 1. Ponieważ z liczb do brania (tych 1, 2, 3, 4) wziąłem 1, to teraz to 1 jest już wykorzystane, a niewykorzystane do brania zostały 2, 3 i 4. Teraz ustalam, jaka będzie wartość mojej permutacji dla argumentu 2 (po kolei idę z argumentami). W tym celu patrzę, jaka jest druga (druga, bo jestem przy argumencie 2) liczba czteroliczbowego ciągu (przypominam, ciągu 1 3 2 1) - jest to trzy. To znaczy, że moja permutacja przeprowadza argument 2 w trzecią (to "trzecią" wzięło się z tego "3" z czteroliczbowego ciągu) wolną liczbę z tych liczb do brania. Trzecia wolna liczba do brania to 4, więc moja permutacja dla argumentu 2 daje wartość 4. Teraz, jak z liczb do brania zabrałem 4, zostały tam już tylko dwie liczby do brania - 2 i 3. Teraz ustalam, jaka będzie wartość mojej permutacji dla argumentu 3 (po kolei idę z argumentami). W tym celu patrzę, jaka jest trzecia (trzecia, bo jestem przy argumencie 3) liczba czteroliczbowego ciągu (przypominam, ciągu 1 3 2 1) - jest to dwa. To znaczy, że moja permutacja przeprowadza argument 3 w drugą (to "drugą" wzięło się z tego "2" z czteroliczbowego ciągu) wolną liczbę z tych liczb do brania. Druga wolna liczba to 3, więc moja permutacja dla argumentu 3 daje wartość 3. Teraz, jak z liczb do brania zabrałem 3, została tam już tylko jedna liczba do brania - 2. Teraz ustalam, jaka będzie wartość mojej permutacji dla argumentu 4 (po kolei idę z argumentami). W tym celu patrzę, jaka jest czwarta (czwarta, bo jestem przy argumencie 4) liczba czteroliczbowego ciągu (przypominam, ciągu 1 3 2 1) - jest to jeden. To znaczy, że moja permutacja przeprowadza argument 4 w pierwszą (to "pierwszą" wzięło się z tego "1" z czteroliczbowego ciągu) wolną liczbę z tych liczb do brania. Jest już tylko jedna niewykorzystana liczba do brania, jest to - pamiętamy - 2. Więc moja permutacja dla argumentu 4 daje wartość 2. W efekcie czteroliczbowy ciąg 1 3 2 1 przemieniłem w permutację (1→1, 2→4, 3→3, 4→2).
Łatwo udowodnić (a przynajmniej na chłopski rozum uzasadnić), że przy takim sposobie przerabiania tych moich czteroliczbowych ciągów w permutację każdy ciąg da jakąś permutację i że każda permutacja powstanie z któregoś z tych ciągów. A ponieważ te czteroelementowe ciągi tworzy się w głowie łatwo (żeby stworzyć kolejny wystarczy pamiętać poprzedni, nie trzeba pamiętać wszystkich dotychczasowych), więc da się tym sposobem łatwo przejrzeć wszystkie permutacje bez potrzeby pamiętania, jakie permutacje już przejrzałem i bez ryzyka, że którąś pominę. Bardzo praktyczne.
Tak wytwarzane permutacje idą w pewnej kolejności, i ostatnio zauważyłem, że ta kolejność jest ciekawa - na przemian idą permutacje parzyste i nieparzyste. Zobaczcie zresztą. Dla ciągu 1 1 1 1 dostaję permutację (1→1, 2→2, 3→3, 4→4). Ta permutacja jest identycznością, więc można ją na transpozycje rozłożyć na przykład tak, że jest iloczynem transpozycji 1↔2 i 1↔2 - więc jest parzysta. Kolejny ciąg, ciąg 2 1 1 1, daje permutację (1→2, 2→1, 3→3, 4→4). Można ją rozłożyć na transpozycje tak, że jest transpozycją 1↔2 - więc jest nieparzysta (a mówiłem - na przemian idzie: parzysta, nieparzysta, parzysta, nieparzysta). Kolejny ciąg, 3 1 1 1, daje permutację (1→3, 2→1, 3→2, 4→4). Tę permutację można przedstawić jako iloczyn transpozycji 1↔3 i 1↔2 - więc jest ona parzysta (a mówiłem - na przemian idzie: parzysta, nieparzysta, parzysta, nieparzysta). No i tak jest chyba zawsze - a przynajmniej ile sprawdzałem, to zawsze tak było. Bardzo ciekawie - ale mi się nie udało - byłoby udowodnić - że permutacje znajdowane w ten sposób zawsze będą iść na przemian: parzysta-nieparzysta-parzysta-nieparzysta... Udowodnijcie to, proszę, bo ja nie umiem.

komentarze:

powrot na strone glowna

RSS