SES School, Studie en Onderwijs
Wiskunde in de brugklas, Frans voor het examen of een studie Personeel en Arbeid? Moeilijke formulieren van DUO? Iets weten over studiefinanciering of studentenverenigingen? Dit is het forum voor leerkrachten, scholieren en studenten, van brugklas tot uni
Het is niet de bedoeling dat je vandaag al inhoudelijke berichten plaatst over de A-lympiade omdat die wedstrijd nu loopt en het gewoon oneerlijk is voor de mensen die daaraan meedoen.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
Nieuw grafentheoretisch probleem.
Het gaat om een volledige tweedelingsgraaf K2,4.
Deze graaf bestaat uit twee punten a en vier punten b.
Een paar van de vragen erover.
1) Hoeveel opspannende bomen zijn er als de graad van 1 punt van a gelijk is aan 1.
Ik denk dan dat het andere punt van a de graden 1 t/m 4 moet kunnen hebben. Vier punten b hebben graad 1, of 3 punten b hebben graad 1 en eentje graad 2. Dit zijn de mogelijke opties. Maar hoe kan ik nu door handig tellen het aantal opspannende bomen vinden?
2)
Toon aan dat K2,4 12 opspannende bomen heeft als de graad van één punt van a gelijk is aan 2. Ik heb er veel uitgetekend en ook hier geldt weer dat dit het antwoord onder 1) is + het aantal opspannende bomen als beide punten a graad 2 hebben, een punt a graad 3 en een punt a graad 4. Maar weer: het handig tellen lukt me niet.
3)
Dit moet door 1) en 2) te combineren het totaal aantal opspannene bomen opleveren voor K2,4. Kan dit gewoon door een optelling van de antwoorden bij 1) en 2)? Of moet dan graad 3 en 4 erbij komen?
4)
Sommatieformule vinden voor het aantal opspannende bomen van K2,x. Dus nu in het algemeen... Maar aangezien ik 1) en 2) nog niet vinden kan lukt dit nog niet.
Het gaat om een volledige tweedelingsgraaf K2,4.
Deze graaf bestaat uit twee punten a en vier punten b.
Een paar van de vragen erover.
1) Hoeveel opspannende bomen zijn er als de graad van 1 punt van a gelijk is aan 1.
Ik denk dan dat het andere punt van a de graden 1 t/m 4 moet kunnen hebben. Vier punten b hebben graad 1, of 3 punten b hebben graad 1 en eentje graad 2. Dit zijn de mogelijke opties. Maar hoe kan ik nu door handig tellen het aantal opspannende bomen vinden?
2)
Toon aan dat K2,4 12 opspannende bomen heeft als de graad van één punt van a gelijk is aan 2. Ik heb er veel uitgetekend en ook hier geldt weer dat dit het antwoord onder 1) is + het aantal opspannende bomen als beide punten a graad 2 hebben, een punt a graad 3 en een punt a graad 4. Maar weer: het handig tellen lukt me niet.
3)
Dit moet door 1) en 2) te combineren het totaal aantal opspannene bomen opleveren voor K2,4. Kan dit gewoon door een optelling van de antwoorden bij 1) en 2)? Of moet dan graad 3 en 4 erbij komen?
4)
Sommatieformule vinden voor het aantal opspannende bomen van K2,x. Dus nu in het algemeen... Maar aangezien ik 1) en 2) nog niet vinden kan lukt dit nog niet.
kloep kloep
Ik zie nog niet helemaal wat je doet. Als je je punten aan de ene kant beide a noemt, en aan de andere kant allevier 'b', dan creëer je heel veel symmetrie en is het aantal opspannende bomen volgens mij heel veel lager dan jij denkt.
Je weet dat een boom op 6 punten 5 lijnen moet hebben. Heb je dus één van je punten a graad 1 gegeven, dan moeten de overige vier lijnen op het andere punt a uitkomen. Er is dan één b-punt dat graad 2 heeft. Welk b-punt dat is bepaalt het aantal mogelijkheden (samen met welk a-punt graad 1 heeft, en welke graad 4).
Voor onderdeel 2 geldt een soortgelijke constatering: als één punt graad 2 heeft, heeft het andere punt graad 3. En er is wederom 1 b-punt met graad 2. Jij stelt daar ook een situatie waarin punt a graad 4 heeft – maar daar kan ik me niets bij voorstellen. Als je een punt a met graad 2 en een punt a met graad 4 hebt, dan heb je sowieso zes lijnen in je graaf, en dat moet een cykel geven op 6 punten.
Je weet dat een boom op 6 punten 5 lijnen moet hebben. Heb je dus één van je punten a graad 1 gegeven, dan moeten de overige vier lijnen op het andere punt a uitkomen. Er is dan één b-punt dat graad 2 heeft. Welk b-punt dat is bepaalt het aantal mogelijkheden (samen met welk a-punt graad 1 heeft, en welke graad 4).
Voor onderdeel 2 geldt een soortgelijke constatering: als één punt graad 2 heeft, heeft het andere punt graad 3. En er is wederom 1 b-punt met graad 2. Jij stelt daar ook een situatie waarin punt a graad 4 heeft – maar daar kan ik me niets bij voorstellen. Als je een punt a met graad 2 en een punt a met graad 4 hebt, dan heb je sowieso zes lijnen in je graaf, en dat moet een cykel geven op 6 punten.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Eerst even onderdeel 1).
Ik heb de graaf ongeveer zo: a1 is het punt met graad 1, a2 is het andere punt.
a1 - b1 - a2
b2
b3
b4 (invoeren lukt niet helemaal, de b-punten moeten allemaal onder elkaar)
Boom bevat maximaal 5 lijnen, anders heb ik een cykel. Dus als a1 vast staat op graad 1, kom ik niet verder dan 4 mogelijkheden omdat b1, b2, b3 ,b4 allen een keer graad 2 kunnen hebben. Dit correct voor onderdeel 1?
Ik heb de graaf ongeveer zo: a1 is het punt met graad 1, a2 is het andere punt.
a1 - b1 - a2
b2
b3
b4 (invoeren lukt niet helemaal, de b-punten moeten allemaal onder elkaar)
Boom bevat maximaal 5 lijnen, anders heb ik een cykel. Dus als a1 vast staat op graad 1, kom ik niet verder dan 4 mogelijkheden omdat b1, b2, b3 ,b4 allen een keer graad 2 kunnen hebben. Dit correct voor onderdeel 1?
kloep kloep
Waarom zou je altijd het punt met graad 1 a1 noemen?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Je wilt het aantal opspannende bomen berekenen. Als je dan stelt dat alleen punt a1 graad 1 mag hebben dan mis je alle situaties waarin punt a2 graad 1 heeft…quote:Op zaterdag 22 november 2008 12:11 schreef Borizzz het volgende:
Omdat ik de punten goed uit elkaar wil houden...
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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:
Het aantal opspannende bomen van K2,4 met als voorwaarde (a1)=1.
Dit houdt in dat a1 maar verbonden mag zijn met één punt b. Verder heeft een boom die bestaat uit 6 punten 5 lijnen. Een van die lijnen gaat naar punt a1. Dus: de overige 4 lijnen gaan allen naar a2. A2 heeft dus graad 4. De punten b hebben dan graad 1 of graad 2. Het hangt er nu alleen nog van af welk punt b graad 2 heeft. Aangezien er 4 punten b zijn, zijn er dus ook 4 mogelijke opspannende bomen.
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:
Het aantal opspannende bomen van K2,4 met als voorwaarde (a1)=1.
Dit houdt in dat a1 maar verbonden mag zijn met één punt b. Verder heeft een boom die bestaat uit 6 punten 5 lijnen. Een van die lijnen gaat naar punt a1. Dus: de overige 4 lijnen gaan allen naar a2. A2 heeft dus graad 4. De punten b hebben dan graad 1 of graad 2. Het hangt er nu alleen nog van af welk punt b graad 2 heeft. Aangezien er 4 punten b zijn, zijn er dus ook 4 mogelijke opspannende bomen.
kloep kloep
Kijk, dit is één mogelijkheid:
Maar dit is er net zo goed een:
Zijn deze anders? Ja! Want in het ene geval heeft a1 graad 4, en in het andere geval heeft a2 graad 4.
| 1 2 3 4 5 6 7 | __/ / --b2 | / || --b3 ||/ a2---b4 |
Maar dit is er net zo goed een:
| 1 2 3 4 5 6 7 8 | ||\ || \-b2 | \ \ \-b3 \ \ a2---b4 |
Zijn deze anders? Ja! Want in het ene geval heeft a1 graad 4, en in het andere geval heeft a2 graad 4.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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.quote:
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:
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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 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.)
kloep kloep
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 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.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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
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
kloep kloep
Ja, 32 in totaal. Nu is het tijd voor 4.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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.
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.
kloep kloep
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 K2,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.)
Men neme de graaf K2,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.)
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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! ?
Maar goed. Afleiden.
K2,x. dus 2 punten a en x punten b.
a1 heeft graad p. dat wordt dan x! /(x-p)!*p! ?
kloep kloep
Dat is een tamelijk lastige onderneming als je een uitdrukking hebt die gegeven wordt door iets moeilijkers dan een lineaire relatie.quote:
Vreemd toch heb ik ooit geleerd om het op deze manier aan te pakken.
[/quote]
Voor wat precies? En staan je haakjes goed?quote:a1 heeft graad p. dat wordt dan x! /(x-p)!*p! ?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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?
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?
kloep kloep
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 K4,2)quote:
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?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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
Dus dan kom ik op: x! / ( (x-p)! * p! ) * x als aantal opspannende bomen. Voor K2,x
kloep kloep
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:quote:
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
[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:21:35 ]
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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?
Inderdaad p mogelijkheden... steeds blijven denken dat het een boom is.
Maar dit is nog geen sommatieformule toch?
kloep kloep
Nee, dat klopt. Maar je hebt nu een uitdrukking voor het geval dat a1 graad p heeft. Gaan we nu terug naar K4,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:quote:
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?
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 ]
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ja, typefoutje, maar het is natuurlijk volkomen identiek.quote:
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ja, dus:
En als we dan eens kijken voor x = 4: 4*23 = 32; voor x = 3: 3*22 = 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 als we dan eens kijken voor x = 4: 4*23 = 32; voor x = 3: 3*22 = 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 ]
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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?
Mooi zeg
Elegant.Maar hoe kom jij van de sommatie naar de formule. Is dat een kleine stap?
kloep kloep
Haakjes!
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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.
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.
kloep kloep
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.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
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 53 =125 bomen moeten worden.
Cayley zegt zelf ook dat het 53 =125 bomen moeten worden.
kloep kloep
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 ]
kloep kloep
Dan lijkt me dat correct.quote:
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 53 =125 bomen moeten worden.
Nee, dit is een 'vaste' formule. Hij is wel af te leiden trouwens. Als je het binomium van Newton neemt:quote:
[ afbeelding ]
Hoe kwam je van de sommatie tot de formule? Is dit gewoon wat getallen invullen en het verband nu vinden?
En nu invult y = 1, krijg je:
Differentieer nu beide zijden naar x:
Vul nu ‘x = 1’ in:
Dus:
[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:21:50 ]
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Deze vraag lijkt me simpel. Té simpel.
Het gaat om een fibonacci graaf.
T(0) heeft 1 punt
T(1) heeft 1 punt
als n groter gelijk aan 3 geldt voor T(n) dat T(n-1) is linker deelboom en T(n-2) is rechterdeelboom. Elk punt heeft dus maximaal 2 onderburen.
Gevraagd is een formule voor het aantal eindpunten.
Ik heb dat gedaan met recurrente betrekking:
Dus:
T1=1
T2=1
T3=1+1 = T2+T1 = 2
T4=2+1 = T3+T2 = 3
T5=3+2 = T4+T3 = 5
T6=5+3 = T5+T4 = 8
T7=8+5 = T6+T5 = 13
Geeft mij: Tn= Tn-1+Tn-2.
Maar is dit het nu? Volgens mij ben ik zo klaar...of vergeet ik wat..
Het gaat om een fibonacci graaf.
T(0) heeft 1 punt
T(1) heeft 1 punt
als n groter gelijk aan 3 geldt voor T(n) dat T(n-1) is linker deelboom en T(n-2) is rechterdeelboom. Elk punt heeft dus maximaal 2 onderburen.
Gevraagd is een formule voor het aantal eindpunten.
Ik heb dat gedaan met recurrente betrekking:
Dus:
T1=1
T2=1
T3=1+1 = T2+T1 = 2
T4=2+1 = T3+T2 = 3
T5=3+2 = T4+T3 = 5
T6=5+3 = T5+T4 = 8
T7=8+5 = T6+T5 = 13
Geeft mij: Tn= Tn-1+Tn-2.
Maar is dit het nu? Volgens mij ben ik zo klaar...of vergeet ik wat..
kloep kloep
Als we kijken naar een parametervoorstelling van een punt P (bijv. x(t) = sin(t) en y(t) = cos(t), wat is dan de definitie van 'P raakt de lijn l'?
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
Het lijkt mij, ook als je het uittekent, zo te kloppen, behalve dat je van T(0) en T(1) als basis overgaat naar T(1) en T(2).quote:
Deze vraag lijkt me simpel. Té simpel.
Het gaat om een fibonacci graaf.
T(0) heeft 1 punt
T(1) heeft 1 punt
als n groter gelijk aan 3 geldt voor T(n) dat T(n-1) is linker deelboom en T(n-2) is rechterdeelboom. Elk punt heeft dus maximaal 2 onderburen.
Gevraagd is een formule voor het aantal eindpunten.
Ik heb dat gedaan met recurrente betrekking:
Dus:
T1=1
T2=1
T3=1+1 = T2+T1 = 2
T4=2+1 = T3+T2 = 3
T5=3+2 = T4+T3 = 5
T6=5+3 = T5+T4 = 8
T7=8+5 = T6+T5 = 13
Geeft mij: Tn= Tn-1+Tn-2.
Maar is dit het nu? Volgens mij ben ik zo klaar...of vergeet ik wat..
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
ow ja... weer eens onnauwkeurig. Maar ik heb nu een recurrente betrekking afgeleid. Kan ik dit zien als formule? En is er anders een manier om van een recurrente betrekking over te stappen naar een formule?
kloep kloep
Ik zou zeggen dat voor punt P = (xP, yP) geldt dat voor een zekere t geldt x(t) = xP en y(t) = yP en daarnaast dat de richting wordt gegeven door dy/dx van die kromme.quote:
Als we kijken naar een parametervoorstelling van een punt P (bijv. x(t) = sin(t) en y(t) = cos(t), wat is dan de definitie van 'P raakt de lijn l'?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ja, die is er, en er zijn verschillende technieken om van een recurrente betrekking naar een gesloten uitdrukking te komen (meestal breng je je betrekking in een vorm die je 'weet', maar de Fibonaccigetallen zijn zo'n vorm). Zie het Wikipedia-artikel over Fibonaccigetallen.quote:
ow ja... weer eens onnauwkeurig. Maar ik heb nu een recurrente betrekking afgeleid. Kan ik dit zien als formule? En is er anders een manier om van een recurrente betrekking over te stappen naar een formule?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Jouw definitie is sowieso onvolledig, maar laat je licht eens schijnen over deze situatie: stel nu dat je de y-as als lijn neemt, x(t) = sin(x)+1, y(t) = 0. Ofwel iets dat zich over de x-as beweegt en steeds de y-as aantikt. Is dat raken?
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
