Springen naar inhoud

Stelling cyclus


  • Log in om te kunnen reageren

#1

Jekke

    Jekke


  • >250 berichten
  • 997 berichten
  • Ervaren gebruiker

Geplaatst op 18 maart 2008 - 20:24

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

met bijhorend bewijs:
LaTeX

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:
LaTeX

en dan wil ik de samenstellingen verder uitwerken:
LaTeX
LaTeX

wie kan me zeggen waar ik fout interpreteer?

Veranderd door HolyCow, 18 maart 2008 - 20:25


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

dirkwb

    dirkwb


  • >1k berichten
  • 4172 berichten
  • Moderator

Geplaatst op 18 maart 2008 - 20:45

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

met bijhorend bewijs:
LaTeX

Gebruik het principe van volledige inductie om dit te bewijzen: dat gaat een stuk makkelijker.
Quitters never win and winners never quit.

#3

eendavid

    eendavid


  • >1k berichten
  • 3751 berichten
  • VIP

Geplaatst op 18 maart 2008 - 20:54

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.

#4

Phys

    Phys


  • >5k berichten
  • 7556 berichten
  • VIP

Geplaatst op 20 maart 2008 - 13:20

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

met bijhorend bewijs:
java script:void(0);

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 -

#5

Jekke

    Jekke


  • >250 berichten
  • 997 berichten
  • Ervaren gebruiker

Geplaatst op 21 maart 2008 - 13:55

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:

LaTeX

in dat opzicht zou ik denken dat:

LaTeX





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures