[Bèta wiskunde] huiswerk- en vragentopic

quote:

Op zaterdag 22 november 2008 12:19 schreef Borizzz het volgende:
Maar in deze opdracht moet a1 graad 1 hebben. Dus dan is het toch altijdzo dat a2 graad 4 heeft...
a1 zit vast aan graad 1. Of is het dan zo dat meer punten b graad 2 kunnen hebben?
Ik heb nu dit als idee:

Oké, dan was je onnauwkeuring in je probleemformulering. Want je zei eerst: Hoeveel opspannende bomen zijn er als de graad van 1 punt van a gelijk is aan 1. En 1 punt van a zou ik zeggen is óf a1 óf a2… Maar als het alleen a1 is, dan klopt het inderdaad wat je zegt.

De opdracht die ik moet maken is opbouwend bedoeld.
Ik zal proberen wat nauwkeuriger te zijn.
Dus we zijn het eens dat als a1 graad 1 heeft (en dat staat vast) dat het aantal opspannende bomen dus 4 is.
nu de vervolg vraag:

2) Nu is gegeven dat a1 graad 2 heeft en ook dat is een vast gegeven. Gevraagd is weer (voor de afwisseling!) het aantal opspannende bomen:
Ik heb dan dit als antwoord:

Ook hier geldt weer dan de boom bestaat uit 5 lijnen. Als a1 graad 2 heeft, betekent dit dat a2 graad 3 heeft (als de graad van a2 lager is dan is het geen samenhangende graaf meer, en als de graad hoger is heb ik teveel lijnen en een cykel in de boom). Er mag net als in 1) maar één punt b zijn met graad 2, de rest van de punten b hebben graad 1.
Het gaat er nu om uit te rekenen op hoeveel manieren a1 met de 4 punten b kan worden verbonden en hetzelfde voor punt a2. Dus 4!/(2!*1!*1!) 4 boven 2 is 12 mogelijke opspannende bomen.

Je ziet dat ik probeer uitgebreid een antwoord te geven. Aangezien ik ervan wil leren. Ook over dit onderdeel zal weer (over een paar maanden een tentamen volgen, en dus wil ik de onderste steen boven.)

Ik snap dat de vraag opbouwend is, maar als je ze niet nauwkeurig formuleert hier dan zit ik een ander probleem op te lossen natuurlijk. Bij 2 is je redenatie correct. De berekening zelf vind ik echter wat warrig, ik zou zeggen: Het gaat er nu om uit te rekenen op hoeveel manieren a1 met de 2 van de 4 punten b kan worden verbonden. Dit geeft (4 boven 2) = 4!(2!2!) = 6 mogelijkheden (ik snap niet helemaal hoe jij aan je 1! 1! komt). Dat de andere twee niet-verbonden punten van b met a2 moeten worden verbonden is evident. Dan is echter voor de 5e lijn nog de keus met welke van de twee punten die ook met a1 verbonden zijn je deze verbindt. Dat geeft 2 mogelijkheden, dus totaal: 2 * (4 boven 2) = 12. (Je antwoordt klopt dus, maar ik volg je berekening niet geheel.)

Voor 3 geldt dat je niet simpelweg door optelling tot het antwoord komt, maar je bent vrij dichtbij.

Bij 2) dacht ik mbt de berekening aan 4 punten b. van die vier punten zijn er 2 equivalent (zo als je mij een paar dagen geleden leerde). en de twee andere zijn uniek. Dus: 4 boven 2.

Bij 3) is het de volgende vraag: bepaal nu door systematisch tellen het aantal opspannende bomen bij K2,4.
Mijn oplossing gaat dan als volgt:
De aantallen opspannende bomen die onder 1) en 2) zijn berekend zijn symmetrisch ware het niet dat het een gelabelde graaf is. Het totale aantal opspannende bomen uit 1) en 2) is dus 4+12=16. Vanwege symmetrie geldt dat voor een gelabelde graaf K2,4 geldt dat het belangrijk is welk punt waar staat. Dus 2*16= totaal 32 opspannende bomen voor een gelabelde graaf K2,4

Ja, 32 in totaal. Nu is het tijd voor 4.

Mooi zo. De berekening onder 2) snap ik ook. Zat even niet op te letten.

4) De sommatieformule voor het totaal aantal opspannende bomen van een gelabelde tweedelingsgraaf K2,x
Eerst een inventarisatie van wat ik al weet:
K2,1 heeft 1 opspannende boom
K2,2 heeft 4 opspannende bomen
K2,3 heeft 12 opspannende bomen
K2,4 heeft 32 opspannende bomen
Maar ik kan hier niet zomaar een regelmaat in vinden. Sommatie zegt mij dat ik bv de vorige moet optellen dus
(ik probeer maar wat)
voor K2,3 wordt dat 1+4 =5 , maar nu van de 5 naar 12 toe (*2 en dan +2)
voor K2,4 wordt dat 1+4+12=17 en van 17 naar 32 toe (*2 en dan -2)
maar dit zie ik nog niet.

Dit lijkt me niet helemaal de manier om het aan te pakken. Op zich kun je zo'n reeks invoeren in Sloane's encyclopedia of integer sequences, en dan vind je of het een bekende reeks is en welke formules ervoor zijn, etc. Maar afleiden is toch beter.

Men neme de graaf K_2,x. Dan heb je de volgende mogelijkheden: Punt a1 heeft graad 1, heeft graad 2, heeft graad 3, heeft graad 4, heeft graad 5, etc. Als punt a1 graad p heeft, hoeveel mogelijkheden zijn er dan om p punten uit de x punten te kiezen? Op hoeveel verschillende manieren kunnen nu de overige lijnen nog neergelegd worden? Kun je zo'n uitdrukking vinden in termen van p en x?

Zo ja, sommeer dan over p. (Die formule kent een vereenvoudiging trouwens.)

Vreemd toch heb ik ooit geleerd om het op deze manier aan te pakken.
Maar goed. Afleiden.
K2,x. dus 2 punten a en x punten b.
a1 heeft graad p. dat wordt dan x! /(x-p)!*p! ?

quote:

Op zaterdag 22 november 2008 13:12 schreef Borizzz het volgende:
Vreemd toch heb ik ooit geleerd om het op deze manier aan te pakken.

Dat is een tamelijk lastige onderneming als je een uitdrukking hebt die gegeven wordt door iets moeilijkers dan een lineaire relatie.
[/quote]

quote:

a1 heeft graad p. dat wordt dan x! /(x-p)!*p! ?

Voor wat precies? En staan je haakjes goed?

x! / ( (x-p)! * p! )
dit zou zijn het aantal manieren waarop a1 met x punten b kan worden verbonden.
als dit klopt is er het omgekeerde voor a2, want a2 wordt verbonden met punten b die niet aan a1 vast zitten?

quote:

Op zaterdag 22 november 2008 13:23 schreef Borizzz het volgende:
x! / ( (x-p)! * p! )
dit zou zijn het aantal manieren waarop a1 met x punten b kan worden verbonden.
als dit klopt is er het omgekeerde voor a2, want a2 wordt verbonden met punten b die niet aan a1 vast zitten?

Niet het omgekeerde voor a2,van de (x - p) niet verbonden punten is duidelijk dat ze allemaal met a2 verbonden moeten worden. Daar is geen keus voor. Er blijft dan nog maar één lijnstuk over waarvoor wat te kiezen valt. Je keus voor a1 forceert dus op één lijn na een keus voor a2. (Zie m'n uitleg over K_4,2)

Ja, inderdaad; dat ene lijnstuk waar nog wat voor te kiezen valt maakt er juist een boom van. Daarvoor zijn x opties (er waren immers x punten b).
Dus dan kom ik op: x! / ( (x-p)! * p! ) * x als aantal opspannende bomen. Voor K2,x

quote:

Op zaterdag 22 november 2008 13:29 schreef Borizzz het volgende:
Ja, inderdaad; dat ene lijnstuk waar nog wat voor te kiezen valt maakt er juist een boom van. Daarvoor zijn x opties (er waren immers x punten b).
Dus dan kom ik op: x! / ( (x-p)! * p! ) * x als aantal opspannende bomen. Voor K2,x

Niet helemaal. a1 heeft graad p. Dus kun je a1 op (x boven p) = x!(p!(x-p)!) manieren verbinden met punten van b. Voor a2 ligt de keus op één lijn na dan vast. Maar die ene lijn moet verbonden worden met één van de punten die nu met a1 verbonden is (anders zou je een dubbele lijn krijgen en geen verbonden graaf): je hebt dus p mogelijkheden daarvoor. En dat geeft dat het aantal mogelijkheden waar bij punt a1 graad p heeft gelijk is aan:



[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:21:35 ]

Dan krijg ik dus x! / ( (x-p)! * p! ) * p als aantal opspannende bomen.
Inderdaad p mogelijkheden... steeds blijven denken dat het een boom is.
Maar dit is nog geen sommatieformule toch?

quote:

Op zaterdag 22 november 2008 13:39 schreef Borizzz het volgende:
Dan krijg ik dus x! / ( (x-p)! * p! ) * p als aantal opspannende bomen.
Inderdaad p mogelijkheden... steeds blijven denken dat het een boom is.
Maar dit is nog geen sommatieformule toch?

Nee, dat klopt. Maar je hebt nu een uitdrukking voor het geval dat a1 graad p heeft. Gaan we nu terug naar K_4,2 dan zien we dat a1 of graad 1 kan hebben, of graad 2, of graad 3 of graad 4, als we dat invullen vinden we dus dat we moeten krijgen:



En dit is gelijk aan: 1*4 + 2*6 + 3*4 + 4*1 = 4 + 12 + 12 + 4 = 32.

In het algemene geval luidt de somformule dus…

[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:20:33 ]

Waarom K4,2? We deden toch K2,4?

quote:

Op zaterdag 22 november 2008 13:47 schreef Borizzz het volgende:
Waarom K4,2? We deden toch K2,4?

Ja, typefoutje, maar het is natuurlijk volkomen identiek.

Dus de algemene formule wordt p * (x boven p).
met p loopt van 1 naar x?

Ja, dus:



En als we dan eens kijken voor x = 4: 4*2³ = 32; voor x = 3: 3*2² = 12, voor x = 2: 2*2 = 4. Het klopt als een zwerende vinger met wat je gevonden hebt. Maar, dit verband was lastig te vinden geweest door alleen naar het rijtje te kijken (denk ik).

[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:21:40 ]

En dit is dus gelijk aan de formule x * (2^x-1).
Mooi zeg Elegant.
Maar hoe kom jij van de sommatie naar de formule. Is dat een kleine stap?

Haakjes!

Ik ben nu de huiswerk opdrachten even opnieuw aan het maken.
De wielgraaf W4, aantal opspannende bomen tellen. Dit werkte met subgroepen met spaken 1,2,3, 4 achtereenvolgens.

Wielgraaf heeft A in het midden, linksboven B, rechtsboven C, rechtsonder D en linksonder E.
k=1
2 mogelijkheden voor een boom:
1) pad van het type A-B-C-D-E 60 opties
2) boom A - B en dan een tak met E-D en een tak met -C. 60 opties.
Samen 120 mogelijke subbomen.
k=2
levert zelfde typen op die al geteld zijn.
je zou kunnen proberen een subboom te maken waarin beide spaken voorkomen maar dit levert óf een cykel óf het pad dat ik al heb geteld.
k=3
zelfde redenering als onder k=2. niets nieuws onder de zon
k=4
A is dan uniek, B,C, D en E uniek. Dus 5 nieuwe mogelijkheden als subboom.
Gevolg: 60+60+5=125.

Het maakt wel uit of je met een vaste labelling werkt of niet. Als je inderdaad altijd A in het midden hebt, neemt het aantal mogelijkheden af. Aangezien je rechtsboven C hebt en linksonder E, zul je nooit de lijn AE in je graaf kunnen hebben. Dat kan alleen als je labelling niet vaststaat en je AE buurpunten kunt maken.

Het is een gelabelde graaf, ja. Labels liggen niet vast, het gaat puur om het aantal mogelijke bomen. A hoeft niet altijd het centrum te zijn. Bij k=4 zie je ook dat B,C,D, E als centrum kunnen fungeren.
Cayley zegt zelf ook dat het 5³ =125 bomen moeten worden.

Hoe kwam je van de sommatie tot de formule? Is dit gewoon wat getallen invullen en het verband nu vinden?

[ Bericht 12% gewijzigd door motorbloempje op 01-09-2013 21:21:46 ]