Antag, at der er m Martians & n Earthlings på en fredskonference. For at sikre, at Martians bliver fredelige på konferencen, må vi sørge for, at ingen to martians sidder sammen, sådan at der mellem mindst to Martians er mindst en Earthling? (Se detaljer)

Svar:

en) # (N! (N + 1)!) / ((N-m + 1)!)

b) # (N! (N-1)!) / ((N-m)!)

Forklaring:

Ud over nogle ekstra ræsonnement vil vi bruge tre almindelige teknikker til tælling.

For det første vil vi gøre brug af det faktum, at hvis der er # N # måder at gøre en ting og # M # måder at gøre en anden på, så antager opgaverne uafhængige (hvad du kan gøre for en ikke stole på det du gjorde i den anden), der er # Nm # måder at gøre begge dele. For eksempel, hvis jeg har fem skjorter og tre par bukser, så er der #3*5=15# tøj jeg kan lave.

For det andet vil vi bruge det antal måder at bestille på # K # objekter er #K! #. Dette er fordi der er # K # måder at vælge det første objekt på og derefter # K-1 # måder at vælge den anden, og så videre og så videre. Således er det samlede antal måder #K (k-1) (k-2) … (2) (1) = k! #

Endelig vil vi bruge det antal måder at vælge # K # objekter fra et sæt af # N # objekter er # ((n), (k)) = (n!) / (k! (n-k)!) # (udtalt som n vælg k). En oversigt over, hvordan man ankommer til denne formel er givet her.

a) Hvis vi i første omgang ignorerer splittelserne, er der #m! # måder at bestille Martians og #n! # måder at bestille earthlings på. Endelig skal vi se, hvor Martians er placeret. Som hver martiner skal placeres enten på en ende eller mellem to Earthlings, er der # N + 1 # steder, de kan sidde (den ene til venstre for hver Earthling, og så en mere helt til højre). Som der er # M # Martians, det betyder at der er # ((n + 1), (m)) = ((n + 1)!) / (m! (n + 1-m)!) mulige måder at placere dem på. Således er det samlede mulige sædearrangementer

(n + 1)!) / ((n + 1-m)!) = (n! (n + 1)!) / ((n-m + 1)!)

b) Dette problem ligner ovenstående. For at gøre tingene enklere, lad os vælge en Earthling og kalde ham præsidenten. Fordi det er ligegyldigt, hvordan en cirkel drejes rundt, i stedet for at henvise til sædearrangementer baseret på en absolut bestilling, vil vi overveje siddepladser i forhold til deres forhold til præsidenten.

Ligesom ovenfor, hvis vi starter fra præsidenten og fortsætter med uret rundt om cirklen, kan vi tælle antallet af måder at bestille de resterende deltagere på. Som der er # M # Martians og # N-1 # resterende earthlings, der er #m! # måder at bestille Martians og # (N-1)! # måder at bestille de resterende Earthlings på.

Derefter skal vi igen placere Martiansne. Denne gang har vi ikke en ekstra plads i slutningen, så er der kun # N # steder de kan sidde på. Så er der # ((N), (m)) = (n!) / (M! (N-m)!) måder at placere dem på. Således er det samlede mulige sædearrangementer

# (N-1)! M! (N!) / (M! (N-m)!) = (N! (N-1)!) / ((N-m)!)