Calkin Wilf-träd, del 3

Matematiken är full av vackra oväntade kopplingar, som mellan ett träd av bråk och ett gammalt taluppdelningsproblem.

Hittills har vi konstaterat att antalet sätt att dela upp ett tal i en summa av tvåpotenser, där ingen potens förekommer fler än två gånger verkar sammanfalla med täljarna i bråken från Calkin Wilf-trädet, om vi skriver dem på rad. Vi såg också att antalet uppdelningar för ett udda tal är lika med antalet uppdelningar för dess mindre hälft:

#sätt(2n+1) = #sätt(n).

Låt oss hitta något samband för jämna tal. Man kan dela upp ett jämnt tal i tvåpotenser utan att använda några 1:or. Men om man använder 1:or, måste man nödävndigtvis använda exakt 2. Annars skulle inte den totala summan bli jämn.

I det första fallet får vi en summa av typen 2x. I så fall är x en uppdelning för hälften av vårt ursprungliga tal. Exempel: 12 = 2 + 2 + 4 + 4 = 2*(1 + 1 + 2 + 2). En uppdelning för 6 är just 6 = 1 + 1 + 2 + 2.

I det andra fallet får vi 1+1+2x. Då är x uppdelningen för hälften av vårt tal minus ett.
Exempel: 12 = 1 + 1 + 2 + 8 = 1 + 1 + 2*(1 + 4). En uppdelning för 5 är just 5 = 1 + 4.

Vi ser att antalet sätt att dela upp ett jämnt tal motsvarar antalet sätt att dela upp dess hälft samt sätt att dela upp talet ett mindre än dess hälft. Matematiskt sagt får vi

#sätt(2n) = #sätt(n) + #sätt(n – 1).

Så varför följer bråkraden samma mönster?

Låt oss numrera varje tal i trädet, motsvarande dess position i raden. Det översta bråket får numret 0, och sedan numrerar vi rad för rad i trädet:

Ett av sambandet vi ser är att varje bråk med udda nummer 2n + 1 är ett vänsterbarn till bråket med nummer n (detta går att visa med induktion). Enligt trädregeln har vänsterbarn exakt samma täljare som sin förälder, därmed följer trädet samma lag som antalet sätt i tvåpotensuppdelningen för udda tal.

Notera också att varje bråk med jämnt nummer 2n (utom 0) är ett högerbarn till bråket med numret n-1. Men vi har i del 1 visat att att bråket med nästa nummer n kommer att ha samma täljare som bråket innan hade nämnare. Därmed får vi att täljarna a och b tillsammans bildar täljaren a + b, precis som uppdelningssambandet för jämna tal säger.


Likheten mellan de två strukturerna är därmed visad. Men det finns fortfarande egenskaper hos Calkin-Wilf trädet som vi inte har pratat om. Till exempel ser vi att inga två bråk upprepar sig. Inget bråk går heller att förkorta. Består trädet rentav av alla icke-förkortningsbara bråk, där varje sådant bråk förekommer exakt en gång?

Om ja, kan du hjälpa mig att bevisa det?

Calkin Wilf-träd, del 2

Å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

Calkin Wilf-träd, del 1

Det är sällan som nya matematiska upptäckter handlar om någonting enkelt. All matematik som lärs ut i grundskolan upptäcktes för länge sedan av gamla greker, araber, kineser och indier. Gymnasiematematiken baserar sig på upptäckter som är minst 300 år gamla. Den nyaste forskningen är även för svår för universitetsmatten: algebrakurser har exempelvis varit ungefär likadana sedan 1920-talet.

Just därför är det så imponerande när nya enkla samband hittas. Calkin och Wilf publicerade en artikel om följande struktur så sent som 2000. Likt Pascals oändliga triangel, introducerar de ett oändligt träd, med nu är noderna bråktal.

Börja med att skriva 1/1 högst upp.
Sedan upprepa samma process om och om igen: om ett tal a/b är med i trädet, rita ut två grenar från det och skriv bråket a/(a+b) i den vänstra grenen och (a+b)/b i den högra. Till exempel, så kommer 1/1 att förgrenas i 1/2 samt 2/1.
1/2 kommer att förgrenas i 1/3 samt 3/2, och så vidare. Vi får följande struktur, som bär namnet Calkin Wilf-trädet:

Låt oss skriva ner bråken genom att läsa av en rad i trädet i taget. Vi får listan:

\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, \ldots

Notera att varje bråks nämnare sammanfaller med nästa bråks täljare. Varför är det alltid så?

För två grannar i trädet är egenskapen inte alls konstig, eftersom båda talen sammanfaller med a+b. Men om två tal är bredvid varandra i trädet utan att vara omedelbara grannar, så är det ena någons högergranne, medan det andra någons vänstergranne. Notera att högergrannar alltid ärver nämnaren, medan vänstergrannar ärver täljaren. Om vi följer arvet upp i trädet från våra två tal, kommer vi till slut fram till två tal, som faktiskt är omedelbara grannar, och därför är det första talets nämnare lika med andra talet täljare.

I den allra sista situationen är två tal grannar i raden, men i trädet skedde en radbrytningen mellan det första och det andra talet. Men vi ser att alla tal i slutet av raderna har nämnare 1, medan alla i början av raderna har täljare 1, så egenskapen bevaras här också.

Bråkraden har även andra egenskaper. Kan du komma på några?

Calkin Wilf-träd, Del 2