Pretpostavimo da na moru ima m Marsovaca i n Zemljana. Da bismo osigurali da Marsovci ostanu mirni na konferenciji, moramo se pobrinuti da ne postoje dva Marsovca zajedno, tako da između dva Marsovca postoji barem jedan Zemljanin (vidi detalj)

Odgovor:

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

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

Obrazloženje:

Osim nekih dodatnih razmišljanja, koristit ćemo tri uobičajene tehnike za brojanje.

Prvo, iskoristit ćemo činjenicu da ako postoje # # N načina da učinite jednu stvar i # M # način da učinite nešto drugo, a pretpostavljajući da su zadaci neovisni (ono što možete učiniti za jednog ne oslanjaju se na ono što ste učinili u drugom), postoje # Nm # načina za oboje. Na primjer, ako imam pet košulja i tri para hlača, onda postoje #3*5=15# odjeću koju mogu napraviti.

Drugo, koristit ćemo to broj načina naručivanja # K # objekata #K! #, To je zato što postoje # K # načina odabira prvog objekta, a zatim # K-1 # načina odabira drugog, i tako dalje i tako dalje. Tako je ukupan broj načina #K (k-1), (k-2) … (2) (1) = k! #

Konačno, koristit ćemo to broj načina odabira # K # objekata iz skupa # # N objekata # ((n), (k)) = (n!) / (k! (n-k)!) # (izgovara se kao n odaberite k). Ovdje je dat pregled kako doći do ove formule.

a) Ako u početku zanemarimo podjele, postoje # m! # načina da naručite Marsovce i #N! # načine naručivanja Zemljana. Konačno, moramo vidjeti gdje su Marsovci smješteni. Budući da svaki Marsov treba biti smješten na kraju ili između dva Zemljana, postoje # N + 1 # mjesta koja mogu sjesti (jedan lijevo od svakog Zemljanina, a zatim još jedan na desnoj strani). Kao što postoje # M # Marsovci, to znači da postoje # ((n + 1), (m)) = ((n + 1)!) / (m! (n + 1-m)!) # moguće načine postavljanja. Prema tome, ukupni mogući raspored sjedenja je

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

b) Ovaj je problem sličan gore navedenom. Da pojednostavimo stvari, hajde da odaberemo Zemljanina i nazovemo ga predsjednikom. Budući da nije važno kako se kruži krug, umjesto da se poziva na raspored sjedenja na temelju apsolutnog naručivanja, razmotrit ćemo raspored sjedenja na temelju njihovog odnosa s predsjednikom.

Kao što je gore navedeno, ako krenemo od predsjednika i nastavimo u smjeru kazaljke na satu oko kruga, možemo izbrojati broj načina naručivanja preostalih sudionika. Kao što postoje # M # Marsovci i # N-1 # preostalih Zemljana, postoje # m! # načina da naručite Marsovce i # (N-1)! # načina naručivanja preostalih Zemljana.

Zatim, ponovno moramo postaviti Marsovce. Ovaj put nemamo dodatnu točku na kraju, tako da postoje samo # # N mjesta gdje mogu sjediti. Onda postoje # ((N), (m)) = (n!) / (M! (N-m)!) # načina da ih smjestite. Prema tome, ukupni mogući raspored sjedenja je

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