Hur många fylogenetiska träd?
Baserat på tråden https://www.pluggakuten.se/trad/fylogenetiskt-trad/ inspirerades jag till att formulera följande kluring/problem. Något klumpigt laddar jag upp det som en bild för skissade det som en poster att sätta upp i fikarummet på jobbet för att fortsätta distrahera mina kollegor.
Visa spoiler
Kan det vara 28? Vet inte varför jag fick den siffran hahaha
Aloosher skrev:Visa spoiler
Kan det vara 28? Vet inte varför jag fick den siffran hahaha
Jag fick ett annat tal (i samma storleksordning) men kan ju vara för att du tolkat problemet annorlunda än jag tänkt. Enda sättet man kan veta det är att redovisa sin metod : )
SeriousCephalopod skrev:Aloosher skrev:Visa spoiler
Kan det vara 28? Vet inte varför jag fick den siffran hahaha
Jag fick ett annat tal (i samma storleksordning) men kan ju vara för att du tolkat problemet annorlunda än jag tänkt. Enda sättet man kan veta det är att redovisa sin metod : )
Visa spoiler
Jag tänkte såhär, det finns totalt 2 träd du kan bilda, en med 1 gren och 3 grenar bredvid varandra och en med 2 grenar och 2 grenar.
I trädet med 2 stycken 2 grenar så finns det totalt 6 sätt att kombinera insekterna, 6 * 1 (Anledningen till att det inte är 4*3*2*1 är för att insekt 1, insekt 2 och insekt 2, insekt 1 i samma "grenträd" räknas som samma så det blir 4 choose 2 gånger 2 choose 2.)
I trädet med 3 grenar och 1 gren så finns det totalt 4 sätt att kombinerna insekterna, 1 * 4 (samma anledning som ovan).
Totalt blir det då 10 sätt. (Jag tänkte först i huvudet när jag fick 28 men tänkte på samma sätt, är det rätt?):
@Aloosher
Visa spoiler
Grundlogiken tycker jag ser rimlig ut, att dela upp i två typer av träd och räkna hur man kan placera djuren i de räden, men jag är inte riktigt med på vad du menar med "1 gren och 3 grenar"-fallet.
Visa spoiler
nigus skrev:Visa spoiler
Faller inte under accepterade lösningar så som listade :P . Men ja...! det är serien.
SeriousCephalopod skrev:nigus skrev:Visa spoiler
Faller inte under accepterade lösningar så som listade :P . Men ja...! det är serien.
Visa spoiler
OK, trevligt problem. Jag hittade första termerna med rekursionen
Så vi testar alla möjligheter för trädets första förgrening, det finns $\binom{n}{i}$ sätt att välja delmängden för det vänstra subträdet, och $f(i)f(n-i)$ sätt att konstruera de två subträden. Sedan måste vi dela med två för att slippa dubbelräkning eftersom vi kan byta plats på de två subträden.
Fast jag vet inte hur man går från rekursionen till (2n-1)!!. Eller induktion funkar men det är lite fusk tycker jag. Finns det någon fin bijektion eller något?
Sammanhanget var att jag var intresserad av rekursiva algoritmer för att generera själva graferna snarare än att räkna antal så kan inte säga så mycket om kombinatoriska förenklingar för att få enklare formel för antalet.
SeriousCephalopod skrev:@Aloosher
Visa spoiler
Grundlogiken tycker jag ser rimlig ut, att dela upp i två typer av träd och räkna hur man kan placera djuren i de räden, men jag är inte riktigt med på vad du menar med "1 gren och 3 grenar"-fallet.
Jag gör en snabb illustration:
Men vad ska man få för svar?
Trädet till vänster är inte ett tillåtet träd. Poängen med fylogenetiska träd är att man ska kunna avgöra vilka arter som är närmast släkt. Har man en tregrening så kan man inte se vilket par som är närmast släkt.
Trädet till vänster måste se ut lite mer som
I slutändan kommer svaret, när man summerar möjligheterna i de två träden att bli
Visa spoiler
15
SeriousCephalopod skrev:Trädet till vänster är inte ett tillåtet träd. Poängen med fylogenetiska träd är att man ska kunna avgöra vilka arter som är närmast släkt. Har man en tregrening så kan man inte se vilket par som är närmast släkt.
Trädet till vänster måste se ut lite mer som
I slutändan kommer svaret, när man summerar möjligheterna i de två träden att bli
Visa spoiler
15
Det är logiskt faktiskt. I trädet med 2, 2 grenar finns 3 kombinationer (för i lättare ord finns det 6 "par" av insekter man kan skapa och om du väljer exempelvis par 1 så kommer du få par 2 automatiskt i den andra gruppen av grener men om du tar par 2 så får du också par 1 automatiskt i den andra grenen så du överäknar 6 dubbelt så du delar det med 2 för att få 3) och i det nya trädet finns det 12 kombinationer för det finns 6 sätt du kan kombinera grenerna längst åt höger och sen kan du multiplicera det med 2 för de två sista insekternas plats spelar roll. Man kan även göra tvärtom, 4 *3 * 1 = 12.
12+3 = 15.
För n>1 finns det (2n-3)!! möjligheter.
Om det finns intresse kan jag bevisa det, annars lämnar jag det som en överskurskluring för den som känner sig hågad.
Behövs ingen avancerad matematik för att bevisa, typ bara sådant som ingår i en första kurs i diskret matematik.
En lista över alla kombinationer, illustrerad med tvåpotenser för enkelhetens skull. Vi döper de fyra djuren till 1, 2, 4, respektive 8. Barnet till två djur skrivs som summan av föräldrarnas tal.
Visa spoiler
Den första möjligheten är att trädet är ett "V", följt av två extra grenar. Det ger tolv möjligheter.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Vi har även möjligheten att trädet ser ut som två "V:n", som sedan förenas. Det ger tre möjligheter:
1.
2.
3.
Kul uppgift!
Måttligt intresse för min generella lösning.
Jag kör ändå, jag har lite grejer jag behöver prokastinera.
Visa spoiler
Huvudidén är följande antal fylogenetiska träd med n+1 arter är lika med antal sätt att välja ett fylogenetiskt träd med n arter och sedan välja en nod i det trädet. I princip väljer vi först hur trädet skulle sett ut utan art n+1 och sedan väljer vi vid vilken nod vi ska stoppa in art n+1.
Vad vi visar först är att antalet noder i ett fylogenetiskt träd med n arter är 2n-1.
Vi börjar med lite terminologi. Noden som är "the common ancestor" kallar vi roten. Noderna längst ner som svarar mot en specifik art kallar vi löv. Noder däremellan kallar vi grenar.
Observera att roten har grad 2, löven grad 1 och grenar grad 3. Vi vet att det finns 1 rot och n löv. Säg att det finns k grenar. Eulers formel ger
Noder-kanter+ytor =2
Ett träd har inga slutna ytor så ytor=1 och vi får
Noder-kanter =1
Noder är n+1+k. Summan av alla noders gradtal är 2+3k+n, Antal kanter är hälften av detta. Löser vi det ekvationssystemet får vi k=n-2. Totalt antal noder är alltså 1, rot, n-2 grenar, n löv, det vill säga 2n-1 noder.
Vi har ju nu ett binärt träd, så varje icke-löv har två noder under sig, vilka vi tänka på som en högernod och en vänsternod. Bara rent konventionsmässigt antar vi art n+1 alltid är i en högernod.
Givet en nod i ett träd, kallar vi den noden och alla noder under den för ett delträd.
Betrakta nu ett fylogeneiskt träd med n+1 arter.
Lövet för art n+1 är då högernod för någon nod u, vars vänsternod v är rot till ett delträd T. Suddar vi bort lövet för art n+1 samt u och ersätter u med T, med rot i v, så får vi ett fylogenetiskt med n arter.
Omvänt, givet ett fylogenetiskt träd med n arter, kan vi välja en nod v, som är rot till delträdet T, ersätta v med u, en nod som har ett löv för art n+1 som högernod och som har delträdet T med rot v, som vänsternod.
Det finns alltså lika många träd för n+1 arter som det finns sätt att välja träd med n arter och sedan välja en nod i det trädet. Varje träd för n arter har 2n-1 noder så vi får,
a_(n+1)=a_n*(2n-1)
som tillsammans med initialvillkoret a_1=1 ger a_n =(2n-3)!! för n>1.
Smutsmunnen skrev:Måttligt intresse för min generella lösning.
Jag kör ändå, jag har lite grejer jag behöver prokastinera.
Visa spoiler
Huvudidén är följande antal fylogenetiska träd med n+1 arter är lika med antal sätt att välja ett fylogenetiskt träd med n arter och sedan välja en nod i det trädet. I princip väljer vi först hur trädet skulle sett ut utan art n+1 och sedan väljer vi vid vilken nod vi ska stoppa in art n+1.
Vad vi visar först är att antalet noder i ett fylogenetiskt träd med n arter är 2n-1.
Vi börjar med lite terminologi. Noden som är "the common ancestor" kallar vi roten. Noderna längst ner som svarar mot en specifik art kallar vi löv. Noder däremellan kallar vi grenar.
Observera att roten har grad 2, löven grad 1 och grenar grad 3. Vi vet att det finns 1 rot och n löv. Säg att det finns k grenar. Eulers formel ger
Noder-kanter+ytor =2
Ett träd har inga slutna ytor så ytor=1 och vi får
Noder-kanter =1
Noder är n+1+k. Summan av alla noders gradtal är 2+3k+n, Antal kanter är hälften av detta. Löser vi det ekvationssystemet får vi k=n-2. Totalt antal noder är alltså 1, rot, n-2 grenar, n löv, det vill säga 2n-1 noder.
Vi har ju nu ett binärt träd, så varje icke-löv har två noder under sig, vilka vi tänka på som en högernod och en vänsternod. Bara rent konventionsmässigt antar vi art n+1 alltid är i en högernod.
Givet en nod i ett träd, kallar vi den noden och alla noder under den för ett delträd.
Betrakta nu ett fylogeneiskt träd med n+1 arter.
Lövet för art n+1 är då högernod för någon nod u, vars vänsternod v är rot till ett delträd T. Suddar vi bort lövet för art n+1 samt u och ersätter u med T, med rot i v, så får vi ett fylogenetiskt med n arter.
Omvänt, givet ett fylogenetiskt träd med n arter, kan vi välja en nod v, som är rot till delträdet T, ersätta v med u, en nod som har ett löv för art n+1 som högernod och som har delträdet T med rot v, som vänsternod.
Det finns alltså lika många träd för n+1 arter som det finns sätt att välja träd med n arter och sedan välja en nod i det trädet. Varje träd för n arter har 2n-1 noder så vi får,
a_(n+1)=a_n*(2n-1)
som tillsammans med initialvillkoret a_1=1 ger a_n =(2n-3)!! för n>1.
Wow riktigt snyggt, tror jag iaf för det är ju inte som att jag fattar
Bra jobbat hahaha :d (Jag var faktiskt väldigt intresserad men vågade inte fråga)
