WisFaq!

Vlakvulling met cijfers via faculteiten

Hoeveel mogelijkheden zijn er om een vierkant van n x n vakjes zo in te vullen dat er in elke rij en in elke kolom de cijfers 1 t/m n zijn ingevuld ????

voorbeeld:

1234
4312
3421
2143

Als het een vierkant van 3x3 is, dan zijn er voor de eerste rij 3!(6) mogelijkheden, en bij een vierkant van 4x4 zijn er voor de eerste rij 4!(24) mogelijkheden.

Maar nu is het zo dat voor een vierkant van 3x3 voor de tweede rij 2 mogelijkheden en voor een vierkant van 4x4 voor de tweede rij 9 mogelijkheden zijn. Bij een vierkant van 5x5 zijn er 44 mogelijkheden.

Hoe komen ze aan die getallen ??? Zit daar een logica in of is dat toevallig ??? En hoe zit het met de derde en vierde rij ???

Bij voorbaat dank,

Joost Vermeij
1-11-2004

Antwoord

Vullen van een vierkant van n x n:
Stel k_i(n)="aantal mogelijkheden voor de i^e rij in een n x n vierkant", wanneer we dus bij de bovenste rij beginnen invullen (in)

Eerste rij: k₁(n)=n getallen permuteren=n!

Tweede rij:
*Bekijk n-1 getallen, bekijk de mogelijkheden waarbij de getallen op een andere plaats dan in de eerste rij staan.
*Voeg 1 getal toe.
*Om nu voor die n getallen een mogelijkheid voor de tweede rij te hebben moet dit laatste getal verkeerd staan, dus op één van de andere n-1 plaatsen: wissel om met één van die plaatsen: (n-1)×k₂(n-1) mogelijkheden. Echter mag degene waarmee je omwisselt ook op de juiste plaats staan en de andere n-2 getallen (van die eerste n-1 getallen) moeten nog steeds verkeerd staan: nog eens (n-1)×k₂(n-2) mogelijkheden.
Totaal: (n-1)×(k₂(n-1)+k₂(n-2)).
Zo kun de dus gemakkelijk als de eerste getallen in de rij waarbij je n laat variëren gekend zijn de volgende berekenen.
Per inductie kan je uit deze formule bewijzen dat k₂(n)=n×k₂(n-1)+(-1)ⁿ.
Dit kan dan absoluut geschreven worden met faculteiten (ook gemakkelijk zelf uit te schrijven): k₂(n)=n!×å(0®n)(-1)^k/k!).
Deze rij staat ook op het web als de rij van permutaties van n getallen die alle getallen op een andere plaats zet (zie onderstaande link).

Voor de volgende rijen in het vierkant zijn het aantal mogelijkheden moeilijker te zeggen, omdat dit verschilt naargelang de situatie in de rijen erboven.

Zie mogelijkheden voor de tweede rij [http://www.research.att.com/projects/OEIS?Anum=A000166]

Joeri
8-11-2004