Recimo, da je na mirovni konferenci m marsovci in n Zemljani. Da bi zagotovili, da bodo Marsovci na konferenci ostali mirni, moramo poskrbeti, da ne bosta dva Marsovca sedela skupaj, tako da je med katerima koli dvema Marsovci vsaj en Zemljan?

Odgovor:

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

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

Pojasnilo:

Poleg nekaterih dodatnih argumentov bomo uporabili tri običajne tehnike za štetje.

Prvič, izkoristili bomo dejstvo, da če obstajajo # n # načinov za eno stvar in # m # način, kako narediti drugo, potem pa je prevzem nalog neodvisen (kaj lahko storite za enega ne zanašate na to, kar ste naredili v drugi), # nm # načinov za oboje. Na primer, če imam pet srajc in tri pare hlače, potem obstajajo #3*5=15# obleke, ki jih lahko naredim.

Drugič, uporabili bomo to število načinov naročanja # k # predmetov #k! #. To je zato, ker so # k # načinov izbire prvega predmeta in nato # k-1 # načinov izbire drugega in tako naprej in tako naprej. Tako je skupno število načinov #k (k-1) (k-2) … (2) (1) = k! #

Končno bomo uporabili to število načinov izbire # k # predmetov iz niza # n # predmetov # ((n), (k)) = (n!) / (k! (n-k)!) # (izgovarja se kot n izberite k). Tukaj je podan pregled, kako doseči to formulo.

a) Če na začetku ne upoštevamo razcepov, obstajajo #m! # načine za naročanje Marsovcev in #n! # načine za naročanje Zemljanov. Nazadnje moramo videti, kje so postavljeni Marsovci. Ker je treba vsakega Marsovca postaviti na konec ali med dva Zemljana, obstaja # n + 1 # lokacije, ki jih lahko sedijo (ena levo od vsakega Zemljanca, nato pa še ena na skrajni desni). Kakor so # m # Marsovci, to pomeni, da obstajajo # ((n + 1), (m)) = ((n + 1)!) / (m! (n + 1-m)!) # možne načine, kako jih postaviti. Tako je možna celotna razporeditev sedežev

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

b) Ta težava je podobna zgoraj. Da bi stvari poenostavili, izberite Zemljanca in ga pokličite predsednik. Ker ni pomembno, kako se krog zavrti, namesto da bi se sklicevali na ureditve sedežev, ki temeljijo na absolutnem naročanju, bomo razmislili o razporeditvi sedežev, ki temelji na njihovem odnosu do predsednika.

Tako kot zgoraj, če začnemo od predsednika in nadaljujemo v smeri urinega kazalca okoli kroga, lahko preštejemo število načinov naročanja preostalih udeležencev. Kakor so # m # Marsovci in # n-1 # preostalih Zemljanov #m! # načine za naročanje Marsovcev in # (n-1)! # načinih naročanja preostalih zemeljskih prebivalcev.

Nato moramo ponovno postaviti Marsovce. Tokrat nismo imeli dodatnega mesta na koncu, tako da obstaja samo # n # lahko sedijo. Potem so še # ((n), (m)) = (n!) / (m! (n-m)!) # načine, kako jih namestiti. Tako je možna celotna razporeditev sedežev

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