Stelling cyclus

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer
Gebruikersavatar
Berichten: 997

Stelling cyclus

ik heb de volgende stelling: Iedere cyclus (en dus ook iedere permutatie) is te schrijven als een opeenvolging van transposities.

met bijhorend bewijs:
\((a_1,a_2,...,a_k)=(a_1,a_k)\circ (a_1,a_{k-1}) \circ \ \ ... \ \ \circ (a_1,a_3) \circ (a_1,a_2) \)
Probleem is dat ik dit bewijs niet begrijp (of dus de stelling want het bewijs duidt nogal op trivialiteit) en ik wilde het bewijs als volgt verder uitwerken maar geraak niet verder dan dit:

eerst schrijf ik in permutatienotatie:
\(\left( {\begin{array}{*{20}c} a_1 & a_2 & ... & a_{k-1} & a_k \\ a_2 & a_3 & ... & a_k & a_1\\\end{array}} \right) = \left( {\begin{array}{*{20}c} a_1 & a_k} \\ a_k & a_1\\\end{array}} \right) \circ \left( {\begin{array}{*{20}c} a_1 & a_{k-1} \\ a_{k-1} & a_1\\\end{array}} \right) \circ \ \ ... \ \ \circ \left( {\begin{array}{*{20}c} a_1 & a_3 \\ a_3 & a_1\\\end{array}} \right) \circ \left( {\begin{array}{*{20}c} a_1 & a_2 \\ a_2 & a_1\\\end{array}} \right) \)
en dan wil ik de samenstellingen verder uitwerken:
\( = \left( \left( {\begin{array}{*{20}c} a_1 & a_k} \\ a_k & a_1\\\end{array}} \right) \circ \left( {\begin{array}{*{20}c} a_1 & a_{k-1} \\ a_{k-1} & a_1\\\end{array}} \right) \right) \circ \left( {\begin{array}{*{20}c} a_1 & a_{k-2} \\ a_{k-2} & a_1\\\end{array}} \right) \circ \ \ ... \ \ \circ \left( {\begin{array}{*{20}c} a_1 & a_3 \\ a_3 & a_1\\\end{array}} \right) \circ \left( {\begin{array}{*{20}c} a_1 & a_2 \\ a_2 & a_1\\\end{array}} \right)\)
\( = \left( {\begin{array}{*{20}c} a_{k-1} \\ a_{k} \\\end{array}} \right) \circ \left( {\begin{array}{*{20}c} a_1 & a_{k-2} \\ a_{k-2} & a_1\\\end{array}} \right) \circ \ \ ... \ \ \circ \left( {\begin{array}{*{20}c} a_1 & a_3 \\ a_3 & a_1\\\end{array}} \right) \circ \left( {\begin{array}{*{20}c} a_1 & a_2 \\ a_2 & a_1\\\end{array}} \right)\)
wie kan me zeggen waar ik fout interpreteer?

Berichten: 4.246

Re: Stelling cyclus

HolyCow schreef:ik heb de volgende stelling: Iedere cyclus (en dus ook iedere permutatie) is te schrijven als een opeenvolging van transposities.

met bijhorend bewijs:
\((a_1,a_2,...,a_k)=(a_1,a_k)\circ (a_1,a_{k-1}) \circ \ \ ... \ \ \circ (a_1,a_3) \circ (a_1,a_2) \)
Gebruik het principe van volledige inductie om dit te bewijzen: dat gaat een stuk makkelijker.
Quitters never win and winners never quit.

Gebruikersavatar
Berichten: 3.751

Re: Stelling cyclus

om dirks antwoord niet volledig te verpesten (dat ik nog niet had gezien): wacht met kijken

Verborgen inhoud
van rechts naar links is makkelijker.

a1->a2;

a2->a1->a3;

a3->a1->a4;

...

a(k-1)->a1->ak;

ak->a1;



Ik geloof ook niet dat jou uitwerking klopt.

a1->a(k-1);

a(k-1)->a1->ak;(dat heb je juist)

ak->a1;



disclaimer: dit is vlug even uit mijn hoofd, en het is een tijdje geleden dat ik met deze notaties speelde.

Gebruikersavatar
Berichten: 7.556

Re: Stelling cyclus

HolyCow schreef:ik heb de volgende stelling: Iedere cyclus (en dus ook iedere permutatie) is te schrijven als een opeenvolging van transposities.

met bijhorend bewijs:

[url=http://java%20script:void(0);]java script:void(0);[/url]
Het makkelijkst is om k klein te nemen, bijv k=3:

(a1,a2,a3)=(a1,a3)(a1,a2)

Je weet dat (a1,a2) betekent: a1-> a2 en a2-> a1

Vervolgens pas je hierop toe a1->a3 en a3->a1. Samen levert dat dus

a1->a2

a2->a3

a3->a1 oftewel (a1,a2,a3) waarmee we begonnen. Begrijp je dit?

Nu kun je makkelijk k=4 nemen en nog een keer checken, en dan zul je het intuitief begrijpen. Uiteraard om het te bewijzen gebruik je inductie zoals dirk al zei.
Never express yourself more clearly than you think.

- Niels Bohr -

Gebruikersavatar
Berichten: 997

Re: Stelling cyclus

Phys schreef:Je weet dat (a1,a2) betekent: a1-> a2 en a2-> a1

Vervolgens pas je hierop toe a1->a3 en a3->a1. Samen levert dat dus

a1->a2

a2->a3

a3->a1 oftewel (a1,a2,a3) waarmee we begonnen. Begrijp je dit?
daar zit inderdaad het probleem, ik begrijp dat niet, in mijn cursus staat de volgende definitie voor een samenstelling van twee relaties S en R:
\(S \circ R = \{ (x,y)|( \exists z)((x,z) \in R \ \ \& \ \ (z,y) \in S) \} \)
in dat opzicht zou ik denken dat:
\((a_1,a_3) \circ (a_1,a_2)= \{ (a_1,a_3),(a_3,a_1) \} \circ \{ (a_1,a_2),(a_2,a_1) \}= \{ (a_2,a_3) \}\)

Reageer