Herhaalde partiele permutaties

Continue & discrete verdelingen, toevalsveranderlijken, betrouwbaarheidsintervallen, correlaties.
Plaats reactie
mijosa
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 02 mar 2013, 12:24

Herhaalde partiele permutaties

Bericht door mijosa » 02 mar 2013, 17:12

Beste lezers,

Ik zit in mijn maag met dit probleem:

De achterliggende gedacht is dat in een volledig netwerk met n aantal knopen verschillende volgorden (routes) worden gemaakt.De verzameling van alle volgordes is gelijk aan het aantal knopen in het netwerk. M.a.w. elke knoop wordt enkel en alleen één keer bezocht.

Als je maar 1 route mag maken dan zijn er n! verschillende permutaties.

Als je 2 routes mag maken dan is het al wat lastiger:
Voor de eerste route kun je k knopen uit n kiezen, dit heet een variatie en er zijn dan n!/(n-k)! partiele permutaties voor elke keuze van k. Voor de tweede route is de verzameling knopen nu n-k groot en omdat alle knopen moeten worden bezocht zijn het aantal mogelijkheden dan ook (n-k)!.

Voor twee routes zijn er dus SOM(k=1 tot n) (n! / (n-k)!) * (n-k)! = SOM(k=1 tot n) n! verschillende mogelijkheden.

Mijn probleem is nu: wat als je n routes mag maken, hoeveel mogelijkheden zijn er nu? Daarbij mag het voorkomen dat een route geen enkele knoop bezoekt zolang alle knopen maar wel door een route worden bezocht.

Wie kan mij helpen? Ik ben gisteren tot laat in de nacht doorgegaan maar geen succes. Bij voorbaat dank!

ps: Sorry voor de vage wiskundige notaties maar ik weet niet hoe je dat op een nette manier op het forum kan doen.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Herhaalde partiele permutaties

Bericht door arie » 03 mar 2013, 01:27

mijosa schreef: ...
Voor twee routes zijn er dus SOM(k=1 tot n) (n! / (n-k)!) * (n-k)! = SOM(k=1 tot n) n! verschillende mogelijkheden.
...
Daarbij mag het voorkomen dat een route geen enkele knoop bezoekt zolang alle knopen maar wel door een route worden bezocht.
...
Als een route nul knopen mag bezoeken, dan mag de eerste route dat ook: k start dan bij nul:
SOM(k=0 tot n) (n! / (n-k)!) * (n-k)! = SOM(k=0 tot n) n! = (n+1) * n! = (n+1)!

In tex (quote dit bericht en je ziet de tex-code):



Nu in het algemeen:
Alle knopen worden precies 1 keer bezocht. Als we ze chronologisch achter elkaar plaatsen hebben we dus n! mogelijke bezoekvolgordes.

Elk van die n! mogelijke volgordes moeten we nu nog verdelen over k routes.
Op hoeveel manieren kunnen we een volgorde van n knopen splitsen in k delen?

Hoeveel mogelijkheden zijn er dus in totaal?


Hint: Kijk zo nodig eerst naar een voorbeeld, bv n=6 en k=3:
Voor n=6 wordt knoopvolgorde ABCDEF precies gesplitst in k=3 delen door er 2 scheidingstekens '|' aan toe te voegen.
Vb: AB|C|DEF betekent: route1 = AB, route2=C, route3=DEF
op hoeveel verschillende manieren kunnen we hier die 2 scheidingstekens plaatsen?

mijosa
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 02 mar 2013, 12:24

Re: Herhaalde partiele permutaties

Bericht door mijosa » 03 mar 2013, 15:27

Beste Arie,

Bedankt voor de hint :)
Er zijn natuurlijk mogelijk manieren om 2 scheidingstekens te plaatsen in jouw voorbeeld.

In het algemeen zijn er dan zoveel mogelijkheden:

Ik had voor n=4 al een (soort van) kansboom uitgewerkt met als uitkomst 192, en dat komt overeen met:

Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Re: Herhaalde partiele permutaties

Bericht door barto » 03 mar 2013, 16:06

mijosa: , doet dit je nergens aan denken?
Bedenk dan ook eens hoe je dit antwoord had kunnen vinden zonder te sommeren...
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

mijosa
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 02 mar 2013, 12:24

Re: Herhaalde partiele permutaties

Bericht door mijosa » 04 mar 2013, 17:17

Beste Barto,

Je hebt gelijk, bij nader inzien is dat te schrijven als omdat;
met m=k-1 gelijk is aan:

door het binomium van Newton te gebruiken :)

Maar,
ik was iets te snel door te stellen dat dit de oplossing van mijn probleem was .
Ik heb in mijn eerste post niet duidelijk genoeg aangegeven dat het doel is unieke routes te vinden.
Daarmee wil ik zeggen dat 1->2->3->4 gelijk is aan 4->3->2->1, want dat is gewoon de omgekeerde route.
Dit probleem lijkt me nog een stuk lastiger omdat voor elke keuze van k en daarmee de

term verschillende soorten dubbele routes oplevert.

Zou iemand mij wellicht iets verder kunnen helpen?

Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Re: Herhaalde partiele permutaties

Bericht door barto » 04 mar 2013, 17:42

mijosa schreef:Maar,
ik was iets te snel door te stellen dat dit de oplossing van mijn probleem was .
Ik heb in mijn eerste post niet duidelijk genoeg aangegeven dat het doel is unieke routes te vinden.
Daarmee wil ik zeggen dat 1->2->3->4 gelijk is aan 4->3->2->1, want dat is gewoon de omgekeerde route.
Bedoel je dan dat ook de rondgang
1,2,3,4 hetzelfde is als 4,1,2,3?
En dat 1,2|3,4 hetzelfde is als 4,3|2,1? (hier zijn er dus 2 routes, gescheiden door '|')
Of hetzelfde als 3,4|1,2 ?
Het hangt er van af welke voorwaarden je precies wilt stellen.
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

mijosa
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 02 mar 2013, 12:24

Re: Herhaalde partiele permutaties

Bericht door mijosa » 04 mar 2013, 20:04

barto schreef: Bedoel je dan dat ook de rondgang
1,2,3,4 hetzelfde is als 4,1,2,3?
En dat 1,2|3,4 hetzelfde is als 4,3|2,1? (hier zijn er dus 2 routes, gescheiden door '|')
Of hetzelfde als 3,4|1,2 ?
Het hangt er van af welke voorwaarden je precies wilt stellen.
Misschien bent u bekend met het traveling salesmen problem TSP?
Daarin wordt vaak vermeld dat er n! mogelijkheden zijn, maar dat is niet helemaal zo omdat in een symmetrische graaf de tak van i->j dezelfde kosten meebrengen als j->i.
Derhalve is 1,2,3,4 hetzelfde als 4,1,2,3 omdat deze route (getekend op de graaf als cykel) feitelijk dezelfde is.

Mijn probleem is echter wat groter dan het TSP.
Als eerste uitbreiding kan men het zien als een multiple TSP.
Als ik weet hoeveel unieke routes in het mTSP aanwezig zijn, dan zijn er voor mijn probleem x2 zoveel routes.

Misschien dat het nu wat duidelijker is...

Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Re: Herhaalde partiele permutaties

Bericht door barto » 04 mar 2013, 20:12

Ja, dit maakt het duidelijk. Twee configuraties zijn gelijk als hun grafen (die ongeoriënteerd zijn) gelijk zijn.
Dus 1,2|3,4 is niet hetzelfde als 1,2|4,3 omdat de route eigenlijk slechts uit één cyclus bestaat?
Ik kan niet direct een antwoord bedenken, o.a. wegens tijdsgebrek maar ik zal er eens over nadenken.
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

mijosa
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 02 mar 2013, 12:24

Re: Herhaalde partiele permutaties

Bericht door mijosa » 04 mar 2013, 20:13

Oke mooi, alvast bedankt! :)
Maar 1-2|3-4 is wel hetzelfde als 1-2|4-3.
Het is idee is als een voertuig de route 3-4 periodiek zou gaan uitvoeren, dan is 3-4 hetzelfde als 4-3.
Periodiek wordt het namelijk 3-4-3-4-3-4-3-4-...-

mijosa
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 02 mar 2013, 12:24

Re: Herhaalde partiele permutaties

Bericht door mijosa » 04 mar 2013, 22:04

Beste Barto,

Ik heb zelf nog eens wat onderzoek gedaan en ben op een artikel uit 1975 gekomen waarbij ze bepalen hoeveel 'ELEMENTARY CIRCUITS' en in een gerichte graaf zijn. Ik citeer:
A directed graph G (V, E) consists of a nonempty and finite set of vertices
V and a set E of ordered pairs of distinct vertices called edges. There are n vertices
and e edges in G. A path in G is a sequence of vertices Pvu =(v=v1, v2, ..., vk = u)
such that (vi, vi+ 1)e E for 1 <= i < k. A circuit is a path in which the first and last
vertices are identical. A path is elementary if no vertex appears twice. A circuit is
elementary if no vertex but the first and last appears twice. Two elementary
circuits are distinct if one is not a cyclic permutation of the other.
Volgens mij is dit waar ik (wij) naar op zoek zijn. Zonder afleiding stellen zij dat er exact

elementary circuits in een complete directe graaf zijn met n knopen.

Graag wil ik weten wat jouw mening hierover is en of dit aansluit bij onze eisen?

Plaats reactie