Antal vägar av längd n i en bipartit graf

a-x-b-y och b-y-a-x är inte samma väg. De går ju via olika kanter.

Var kommer din formel ifrån?

Antalet vägar av längd 1 verkar däremot vara 9.

Formeln ser mycket märklig ut, jag har svårt att se vad den skulle kunna beskriva men antalet vägar av längd n i $K_{3,3}$ är det inte, iaf :)

Min formel kommer från en lösning av en gammal tentauppgift. Jag har bifogat en screenshot nedan för att kanske göra min fundering lite klarare 
Lösning:

Det verkar som att det är meningen att man ska gå från en specifik punkt till en annan specifik punkt på andra sidan, så alla vägar från tex a till z. Då stämmer formeln. 

Micimacko skrev:

Det verkar som att det är meningen att man ska gå från en specifik punkt till en annan specifik punkt på andra sidan, så alla vägar från tex a till z. Då stämmer formeln. 

 Jag kanske har missuppfattat vad som menas med längden n, men som jag tänker så går man fram-tillbaka-fram mellan mänderna ($T_1 och T_2$) när n = 3? (se kontroll nedan). Om det är tillåtet och n = 3, så blir i så fall antalet vägar $3^{3-1}= 3^2 =9$, men det verkar inte stämma när jag kontrollerar då jag hittar fler vägar än 9 stycken:
axby
axbz
azcy
azcx
aybx
aybz
bzcx
bzcy
byax
byaz
czby
...
Här har jag hittat 11 vägar av längd n = 3, och jag kan hitta fler om jag fortsätter.

Läs screenshoten och Micimackos svar igen. Formeln gäller inte antalet vägar från T1 till T2, utan från a till x.

Sen gillar jag inte formuleringen i uppgiften. Jag tror att jag bara har sett definitionen av väg som en vandring där varje kant bara används en gång. I din uppgift finns inte den restiktionen, utan väg används synonymt med vandring, utan att kommenteras.

haraldfreij skrev:

Läs screenshoten och Micimackos svar igen. Formeln gäller inte antalet vägar från T1 till T2, utan från a till x.

 Nu förstår jag :) Tack för hjälpen