WisFaq!

Bolpuzzel

Een bekend puzzeltje bestaat uit twintig bolletjes, die je in een driehoekige piramide moet opstapelen. Er zijn twee uiterste verdelingen: één puzzelstuk van twintig bollen aan elkaar en twintig puzzelstukken (alle bolletjes los). Daartussen zitten zeer veel mogelijkheden. De vraag is alleen hoe veel. Ik ben begonnen met het opstellen van de mogelijkheden. Bij 20 vast en 0 los is er 1 mogelijkheid. Bij 19 vast en 1 los zijn er 2 mogelijkheden. Bij bijvoorbeeld 16 vast en 4 los zijn er 5 mogelijkheden, namelijk 16-4 16-3-1 16-2-2 16-2-1-1 16-1-1-1-1. Zo ben ik uitgekomen op 616 mogelijkheden in totaal. Ik weet niet zeker of dit klopt. 16-3-1 kan natuurlijk ook geschreven worden als 3-1-16 of 1-16-3 (en nog meer). Dit bereken je volgens mij met faculteit. Van het aantal puzzelstukken moet je dan de faculteit nemen. Bij het voorbeeld hierboven zou ik dus 3 faculteit moeten nemen. 16-4 16-3-1 16-2-2 16-2-1-1 16-1-1-1-1 wordt dan 2!+3!+3!+4!+4! Dit duurt natuurlijk een eeuwigheid. Klopt deze manier om het totale aantal mogelijkheden te berekenen? En zou dit ook op een eenvoudiger manier kunnen met behulp van een formule. Ik heb eerst ook gedacht aan combinaties en permutaties, maar daar kwam ik niet uit.

Ik hoop dat u mij kunt helpen met dit probleem. Alvast bedankt.

Marjolein Hartog
20-1-2004

Antwoord

Ik snap de puzzel niet helemaal, maar ik denk dat je het hebt over het aantal "partities" van 20 elementen, namelijk het aantal manieren waarom je 20 bolletjes in groepjes kan verdelen (waarbij groepjes met hetzelfde aantal elementen mogen verwisseld worden, zonder dat dit een nieuwe mogelijkheid oplevert).

Zo is het aantal partities van 5 elementen gelijk aan 7, namelijk:

5
4-1
3-2
3-1-1
2-2-1
2-1-1-1
1-1-1-1-1

Heel moedig dat je ze allemaal hebt proberen opschrijven. Je 616 is fout, maar je zit er dichtbij. Kan je ontdekken waar je er enkele bent vergeten?

Zie Aantal partities @ Online Integer Sequences Database [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000041]

cl
20-1-2004