Hoeveel mogelijkheden, formule

[Michel Uphoff]

Een kunstenaar vraagt mij om antwoord op het volgende:
 
Een flink aantal vierkante plaatjes hebben allemaal een zwarte achterzijde, en een voorzijde met een gedeelte van een afbeelding. Het is dus een soort puzzel, die slechts één goede oplossing kent. Dat is die waarbij alle plaatjes met de gezichtszijde omhoog, in de juiste rotatie (0,90,180 en 270 graden) op de juiste locatie (links, boven, rechts onder) bij de juiste buur aansluiten. De achterzijde boven geldt ook als een mogelijkheid, maar dan is de rotatie niet van belang. Op hoeveel manieren is deze puzzel verkeerd te leggen?
 
Bij een vierkantje hebben we 5 mogelijkheden (de achterzijde boven en de 4 rotaties)
Bij twee vierkantjes hebben we 5 mogelijkheden voor het tweede stukje bij iedere 5 mogelijkheden van het eerste stukje, maar ook 4 onderlinge posities (onder-boven, boven-onder, recht-links en links-rechts. Ik zou dan denken 5*5*4=100 mogelijkheden. Bij 3 plaatjes wordt het al lastiger voor mij om het aantal mogelijkheden te bepalen.
 
Er zijn 286 vierkantjes, en het is ook bekend dat gaten in de afbeelding niet mogen voorkomen, alle blokjes sluiten aan in een gevulde rechthoek. Dat beperkt de uiteindelijke afmetingen m.i. dan tot 1*286, 2*143, 11*26 en 13*22, ieder met 4 rotaties.
 
Ik ben altijd slecht geweest in dit soort sommetjes, dus graag jullie inzicht.
Hoeveel legmogelijkheden zijn er bij 286 stukjes? Welke compacte formule berekent dit correct?

[Professor Puntje]

Is het niet bekend wat de afmetingen van de juist gelegde puzzel zijn?
 
Bij een 1*286 puzzel hebben de stukjes al minstens twee rechte zijden zodat de mogelijkheden minder zijn....

[Michel Uphoff]

Nee, alleen dat het een gevulde rechthoek is.

[Professor Puntje]

Oh - mogelijk begrijp ik het verkeerd, de stukjes haken niet in elkaar?

[Michel Uphoff]

Het zijn vierkante plaatjes en 'passen' dus altijd.

[Professor Puntje]

Het is voor mij ook proberen, want bij zulke vraagstukken zie je heel gemakkelijk iets over het hoofd.
 
Klopt dit?
 
In een bepaalde rechthoek kun je ieder stukje in een zekere volgorde op vijf manieren leggen. Dus zijn er bij een bepaalde rechthoek 5²⁸⁶ manieren om de stukjes in een zekere volgorde te leggen.

[Michel Uphoff]

5ⁿ lijkt mij niet correct.
Dat zou bij twee stukjes (a en b) 25 mogelijkheden geven. Dat zijn wel alle rotatiecombinaties, maar niet de onderlinge posities.
a links en b rechts, a boven en b onder en spiegelbeeld zijn ook mogelijkheden. Daarom kwam ik bij twee stukjes al op 100.
Maar hoe dan verder?

[Professor Puntje]

Stel:
 
T is het totale aantal mogelijkheden om de stukjes te leggen.
 
R is het aantal mogelijke rechthoeken waarin de stukjes gelegd kunnen worden.
 
V is het aantal volgorden waarin de stukjes in een gekozen rechthoek gelegd kunnen worden.
 
S is het aantal manieren waarop de stukjes in een gekozen rechthoek in een gekozen volgorde gelegd kunnen worden.
 
M is het aantal manieren waarop een stukje op een gekozen plaats gelegd kan worden.
 
N is het aantal stukjes.
 
Dan zou:
 
T = R . V . S
 
V = N!
 
S = M^N

[Michel Uphoff]

Dus T=R.V.5ⁿ
V is volgens mij n! (n faculteit)
 
Dan zou de formule worden: T=R.n!.5ⁿ
 
Bij twee stukjes: R=1, V=2 S=25, totaal 50
Bij drie stukjes: R=1, V=6, S=125, totaal 450
Bij vier stukjes: R=2, V=24, S=625, totaal 30.000
 
Zou best kunnen, maar zeker ben ik er niet van. Ik mis de rotatiemogelijkheid en zo kom ik bij n=2 op 100 ipv 50.
 
Bij 286 stukjes krijgen we tot nu toe:
 
T=4 * 286! * 5²⁸⁶
4 * 8,706891727.10⁵⁷⁹  * 5²⁸⁶= ruwweg 2,8.10⁷⁸⁰

[Professor Puntje]

Er is altijd het gevaar dat je iets over het hoofd ziet. Gelden bijvoorbeeld 2*143 en 143*2 als verschillende rechthoeken? Zo nee - dan zou de puzzel logischerwijze ook in meerdere standen "goed" gelegd kunnen worden.

[Michel Uphoff]

Gelden bijvoorbeeld 2*143 en 143*2 als verschillende rechthoeken?

 
Ja. De ene afbeelding is een kolom en de andere een rij, terwijl het een van die twee moet zijn.

[Professor Puntje]

Maar dan zou je voor N=2 toch R=2 moeten hebben?

[Michel Uphoff]

Ja, klopt. Over het hoofd gezien.
 
Bij twee stukjes: R=2, V=2 S=25, totaal 100
Bij drie stukjes: R=2, V=6, S=125, totaal 1500
Bij vier stukjes: R=8, V=24, S=625, totaal 120.000
 
(vier: 1*4 en 2x2 in 4 rotaties, totaal 8)
 
Bij 286 stukjes kom ik op 16 mogelijke rotaties en dan krijgen we volgens mij:
 
T = 16 * 286! * 5²⁸⁶
16 * 8,71.10⁵⁷⁹  * 5²⁸⁶= ruwweg 1,12.10⁷⁸¹

[Emveedee]

Bij N=286 heb je dan R=8: http://www.wolframalpha.com/input/?i=divisors+of+286
 
Edit:
Je mag niet het aantal rotaties meetellen in R. Dit zit immers al inbegrepen in de volgorde van de stukjes! Bij N=4 heb je dus R=3, want je kunt rechthoeken van 1x4, 2x2 en 4x1 maken.

[Michel Uphoff]

Ik denk dat je gelijk hebt.
 
Dus dan krijgen we:
 
T = 8 * 286! * 5²⁸⁶
8 * 8,71.10⁵⁷⁹  * 5²⁸⁶= ruwweg 5,6.10⁷⁸⁰
 
Niet dat dat nu echt wat uitmaakt, het blijft ondoenlijk veel.