Calkin Wilf-träd, del 2

Rolig matte?

År 1858 ställde tyska matematiker Stern och Moritz en fråga: På hur många sätt kan man skriva talet n som en summa av tvåpotenser, där var tvåpotens får förekomma högst två gånger? (Ordningen på termerna i summan spelar inte någon roll).

Till exempel kan talet 7 skrivas på ett enda sätt:
7 = 4+2+1

Talet 8 kan däremot skrivas som:
8 = 1+1+2+4
8 = 2+2+4
8 = 4+4
8 = 8,
det vill säga på 4 olika sätt!

Vi kan göra en lite tabell, där talen n står i översta raden, medan i understa raden står antalet sätt som n kan skrivas så som beskrivet ovan. Sätten för n = 7 respektiva n = 8 var angivna, kan du komma på alla sätten för alla de andra talen?

En lite intressant fråga att ställa sig är hur många sätt talet 0 kan skrivas på som en summa av tvåpotenser. Alla tvåpotenser är ju positiva, så man skulle kunna säga att svaret är inget sätt, det vill säga noll sätt.

Men matematiskt brukar man räkna med att summan utav inga termer alls är lika med 0 (medan produkten av inga termer är lika med 1). Det vill säga, finns det exakt ett sätt att skriva 0 på enligt våra regler: det tomma sättet.

Verkar följden 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5… bekant? Om inte, jämför med den i del 1.

Vad kommer det här sambandet mellan ett gammal problem och en ny trädkonstruktion ifrån?

Låt oss tänka på hur vi kan konstruera nya sätt att framställa tal från summor från de gamla.

Säg att talet n är udda. Då måste en 1:a ingå i summaframställningen, dessutom måste det vara exakt en 1:a, då tre stycker eller fler 1:or är föbjudet. Resten av talen i summan är jämna och alltså kan alla delas med 2. Vi kan skriva framställningen av n som 1+2x, där x då blir framställningen för talet (n-1)/2.

Till exempel 11 = 1 + 2 + 4 + 4 = 1 + 2*(1 + 2 + 2).

Därmed har vi förklarat varför antalet sätt för 5 och 11 är samma. Samma gäller för paren 1 och 3, 2 och 5, 3 och 7, 4 och 9, och så vidare (se tabellen).

Men hur man om n är jämnt?

Calkin Wilf-träd, del 3

Kommentera