Permutacje i cykle

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Mr Joker
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 lis 2016, o 17:54
Płeć: Mężczyzna
Lokalizacja: Wielkopolska

Permutacje i cykle

Post autor: Mr Joker » 16 maja 2020, o 19:44

Hej, mam takie oto zadania:

2. Dowolny cykl \(\displaystyle{ (k _{1}k_{2}...k_{m})}\) można przedstawić jako iloczyn transpozycji
\(\displaystyle{ (k_{1}k_{m}) (k_{1}k_{m-1})... (k_{1}k_{2})}\). Udowodnij to indukcyjnie.

3. Dla każdej wartości \(\displaystyle{ m = 1,2,3,4,5,6 }\) znajdź permutację należąca do \(\displaystyle{ S_{6}}\) mającą rząd \(\displaystyle{ m}\). Jeśli to możliwe – unikaj cykli!

4. a) Podaj przykład permutacji z \(\displaystyle{ S_{5}}\) mającej rząd \(\displaystyle{ 6}\).

b) Podaj przykłady permutacji z \(\displaystyle{ S_{7}}\) o rzędach \(\displaystyle{ 10}\) i \(\displaystyle{ 12}\).


Niestety, udało mi się rozwiązać to.
3. Tak to sobie wymyśliłem
a) \(\displaystyle{ m=1}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 1 2 3 4 5 6} = (1)(2)(3)(4)(5)(6) }\)
b) \(\displaystyle{ m=2}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 6 4 5 2 3 1} = (16)(24)(35) }\)
c) \(\displaystyle{ m=3}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 3 4 5 6 1 2} = (135)(246) }\)
d) \(\displaystyle{ m=4}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 6 5 4 1 2 3} = (1634)(25) }\)
e) \(\displaystyle{ m=5}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 1 5 4 2 6 3} = (25634)(1) }\)
f) \(\displaystyle{ m=6}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 5 1 6 2 3 4} = (25634) }\)

Czy 3 zadanie mam dobrze? Pomożecie z resztą?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

a4karo
Użytkownik
Użytkownik
Posty: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Permutacje i cykle

Post autor: a4karo » 16 maja 2020, o 20:02

Wsk: `10=5\cdot 2,\ 12=3\cdot 4`

Mr Joker
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 lis 2016, o 17:54
Płeć: Mężczyzna
Lokalizacja: Wielkopolska

Re: Permutacje i cykle

Post autor: Mr Joker » 16 maja 2020, o 20:13

Poprawione zadanie 3. Czy teraz jest OK?

a) \(\displaystyle{ m=1}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 1 2 3 4 5 6} = (1)(2)(3)(4)(5)(6) }\)
b) \(\displaystyle{ m=2}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 3 2 1 4 5 6} = (13) }\)
c) \(\displaystyle{ m=3}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 5 2 3 4 6 1} = (156) }\)
d) \(\displaystyle{ m=4}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 3 4 2 1 5 6} = (1324) }\)
e) \(\displaystyle{ m=5}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 4 2 6 5 3 1} = (14536) }\)
f) \(\displaystyle{ m=6}\), np. \(\displaystyle{ {1 2 3 4 5 6 \choose 6 5 4 1 3 2} = (162534) }\)

Co do zad. 4 będzie ok?
a) \(\displaystyle{ m=6}\), np. \(\displaystyle{ {1 2 3 4 5 \choose 4 3 2 5 1} = (145)(23) }\)
b) \(\displaystyle{ m=10}\), np. \(\displaystyle{ {1 2 3 4 5 6 7 \choose 3 1 5 6 7 4 2} = (13572)(46) }\)
\(\displaystyle{ m=12}\), np. \(\displaystyle{ {1 2 3 4 5 6 7 \choose 3 6 7 5 2 4 1} = (137)(2645) }\)

matmatmm
Użytkownik
Użytkownik
Posty: 1859
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 73 razy
Pomógł: 262 razy

Re: Permutacje i cykle

Post autor: matmatmm » 16 maja 2020, o 22:22

Na pierwszy rzut oka wszystkie przykłady masz dobrze. Wyjaśnij, gdzie pojawia się problem w dowodzie indukcyjnym.

Mr Joker
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 lis 2016, o 17:54
Płeć: Mężczyzna
Lokalizacja: Wielkopolska

Re: Permutacje i cykle

Post autor: Mr Joker » 17 maja 2020, o 07:12

Nie mam pojęcia co z tym zrobić

Dodano po 6 godzinach 7 minutach 27 sekundach:
Pomożecie? To dość pilne :)

5. Wykaż, że każda permutacja z \(\displaystyle{ S_{6} }\) ma rząd \(\displaystyle{ 1,2,3,4,5 lub 6}\). Uwaga : w ogólnym przypadku grupa \(\displaystyle{ S_{n}}\) może mieć elementy rzędu \(\displaystyle{ >n}\)

2. Dowolny cykl \(\displaystyle{ (k _{1}k_{2}...k_{m})}\) można przedstawić jako iloczyn transpozycji
\(\displaystyle{ (k_{1}k_{m}) (k_{1}k_{m-1})... (k_{1}k_{2})}\). Udowodnij to indukcyjnie.

Jan Kraszewski
Administrator
Administrator
Posty: 26409
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4417 razy

Re: Permutacje i cykle

Post autor: Jan Kraszewski » 17 maja 2020, o 15:06

Możemy pomóc, ale nie zrobić za Ciebie. Np. zacznij dowód indukcyjny.

JK

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3962
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 386 razy

Re: Permutacje i cykle

Post autor: arek1357 » 17 maja 2020, o 15:22

Może niepotrzebnie się wtrącam , ale irytujące jest dla mnie stwierdzenie, że: "każdy cykl możemy przedstawić jako iloczyn takowych transpozycji"...

Prawidłowo powinno być tak, że każdy taki cykl możemy przedstawić za pomocą iloczynu takichże permutacji:

\(\displaystyle{ (k_{1},k_{2},...,k_{m})= \prod_{i=2}^{m}p_{i} }\)

gdzie:

\(\displaystyle{ p_{i}=(k_{1},k_{i})(k_{2})(k_{3})...(k_{i-1})(k_{i+1})...(k_{m})}\)

To jest mylne pójście na skróty...

Niestety te permutacje mylone są z zależnymi transpozycjami...

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9004
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1939 razy

Re: Permutacje i cykle

Post autor: Dasio11 » 17 maja 2020, o 17:58

Na czym właściwie polega różnica między tym, co Cię irytuje, a tym, co sam napisałeś?

a4karo
Użytkownik
Użytkownik
Posty: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Permutacje i cykle

Post autor: a4karo » 17 maja 2020, o 18:26

Ani chybi użycie słowa "takowych" zamiast "takichże". Bo pisanie `(k_1)` jako permutacji, która nic nie robi jest totalnie pozbawione sensu.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3962
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 386 razy

Re: Permutacje i cykle

Post autor: arek1357 » 17 maja 2020, o 21:18

Na czym właściwie polega różnica między tym, co Cię irytuje, a tym, co sam napisałeś?
A tak jest pewna różnica bo mi czy Tobie nie zrobi żadnej różnicy ale dla tego kto się uczy tego różnica jest kolosalna uwierz mi , bardzo często uczący się algebry nie mogą skumać na czym polega takie składanie cykli o części wspólnej i nie mogą tego należycie rozkminić, a po moim rozpisaniu dopiero im się oczy otwierają, uwierz mi że tak jest , miałem kiedyś taki przypadek, że musiałem gościowi coś takiego wyjaśnić a skumał wtedy gdy rozpisałem mu w ten sposób co wyżej...Możliwe Dasio , że tego nie dostrzegasz ale dydaktycznie moja rozpiska jest dużo lepsza...

A4karo tyś czasem nie powinien wykładać gramatyki lub filologii polskiej??

Chętnie zapiszę się na kurs ...

Mr Joker
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 lis 2016, o 17:54
Płeć: Mężczyzna
Lokalizacja: Wielkopolska

Re: Permutacje i cykle

Post autor: Mr Joker » 20 maja 2020, o 20:11

Pomóżcie zacząć i spróbuję dokończyć :) Nie mam kompletnie pomysłu

ODPOWIEDZ