|
|||||
| We gaan het bewijs leveren met
behulp van volledige inductie, en dat doen we door het aantal elementen
van een verzameling steeds groter te maken. inductie-aanname: Stel dat een verzameling van n - 1 elementen(1, 2, 3, ..., n -1) helemaal door transposities kan worden weergegeven. Neem nu het n-de element bij de verzameling. Bekijk een willekeurige permutatie P. Nu zijn er twee mogelijkheden: |
|||||
| 1. | Bij permutatie P komt element n op zichzelf terecht. | ||||
| 2. | Bij permutatie P komt element n op een ander element k terecht. | ||||
| Het eerste geval is
niet interessant: dan is de permutatie P precies zo op te bouwen uit
transposities als bij de kleinere verzameling zonder element n. Het tweede geval is wél interessant. Pas in dit geval twee dingen na elkaar toe: (verwissel nk) o (Permutatie P) Samen laten die n op zijn plaats (bij P gaat n naar k, daarna bij de verwisseling weer van k naar n) Dus zijn die twee samen als een aantal verwisselingen te schrijven (dat is de inductie-aanname: zonder element n) Maar dan is: (verwissel nk) o (verwissel nk) o (Permutatie P) ook een aantal verwisselingen. namelijk die blauwen plus eentje erbij. Maar dit laatste is gelijk aan Permutatie P (die beide verwisselingen heffen elkaar op). Dus is permutatie P als een serie verwisselingen te schrijven. q.e.d. |
|||||
|
© h.hofstede (h.hofstede@hogeland.nl) |
|||||