OliForum Matematico

Ci sono m uomini ed n donne che si siedono attorno ad un tavolo rotondo (con m+n posti, ovviamente), cercando di fare in modo che non ci siano mai due donne una di fianco all'altra. Possono farlo? In quanti modi?

Chiaramente condizione necessaria affinché possano sedersi in quel modo è che $ m \geq n $.
Numero i posti da 1 a m+n.
Per ogni modo in cui le donne possono sedersi (anche senza rispettare la condizione) le ordino seguendo l'ordine crescente del numero del loro posto ottenendo così una sequenza $ p_1,p_2,...,p_n $ di posti occupati da donne.
Pongo $ p'_i=p_i-(i-1) $; allora le disposizioni buone sono in corrispondenza biunivoca con i sottoinsiemi di n elementi di $ (1,...,m+1) $ [come cavolo si fanno le graffe in TeX?] che sono $ \binom{m+1}n $. Questo non è però il numero che stavamo cercando, perché non abbiamo escluso i casi in cui l'unica coppia di posti adiacenti occupata da due donne sia $ (1,m+n) $; nel nostro insieme (1,...,m+1), questo equivale a dire che 1 e m+1 sono "occupati", e quindi a contare le possibili disposizioni per la restanti donne.
Il risultato è quindi $ \binom{m+1}n - \binom{m-1}{n-2} $

Che casino... spero si capisca almeno qualcosa.

what ha scritto: nel nostro insieme (1,...,m+1), questo equivale a dire che 1 e m+1 sono "occupati", e quindi a contare le possibili disposizioni per la restanti donne.
Il risultato è quindi $ \binom{m+1}n - \binom{m-1}{n-2} $

Aspetta.. tu hai detto che, se chiamo $ x_{(m,n)} $ il numero di modi di mettere m donne ed n uomini in modo che non siano attaccate le donne, allora ho che:

$ \displaystyle x_{(m,n)}=\binom{m+1}n - x_{(m-2,n-2)} $

giusto? A questo punto hai una ricorsione da sviluppare...

No, non mi sono spiegato.
Ci riprovo.

Contrassegno i posti con i numeri da 1 a m+n, li rappresento perciò con l'insieme $ P=\{1,...,m+n\} $.
Mettere a sedere le donne equivale a scegliere un sottoinsieme di P di n elementi.
Ad ogni possibile sottoinsieme $ \{a_1,a_2,...,a_n\} $ con $ a_1<a_2<...<a_n $ associo la n-upla $ \{b_1,b_2,...,b_n\} $ dove $ b_i=a_i-i+1 $. Allora il sottoinsieme di partenza non ha elementi consecutivi sse la n-upla ha tutti elementi distinti, ossia se la n-upla è un sottoinsieme di $ \{1,...,m+1\} $.

Abbiamo così $ \displaystyle \binom{m+1}n $ possibilità.


In tutto questo c'è però una falla: io ho contato i sottoinsiemi di P senza elementi consecutivi, ma non tutti vanno bene per il problema. Infatti potrebbe esserci una donna nel posto 1, una nel posto m+n e nessun'altra coppia adiacente. Queste configurazioni sono state contate nel procedimento di prima, ma non soddisfano il problema.

Quante sono?
Bè, per il mio sottoinsieme di P ho due scelte obbligate; per scegliere gli altri n-2 elementi in modo tale da non avere altri due elementi consecutivi, posso usare il trucco di prima. Guardo quindi la n-upla associata: si avrà $ b_1=1,b_n=m+1 $ con tutti gli elementi della n-upla distinti. Devo scegliere $ b_2,b_3,...,b_{n-1} $ fra gli elementi dell'insieme $ \{2,3,...,m\} $.

Pertanto $ \displaystyle \binom{m-1}{n-2} $.


Il numero delle combinazioni davvero buone è quindi $ \displaystyle \binom{m+1}n - \binom{m-1}{n-2} = $ $ \displaystyle \binom m n + \binom m{n-1} -\binom{m-1}{n-2} = \binom m n + \binom {m-1}{n-1} $
[scritto così è anche più carino ]

Ok ho capito, grazie del chiarimento

Comunque immagino che così conti alcune configurazioni più volte (quelle uguali a meno di rotazioni)... mi sbaglio?

Consideriamo il problema così: abbiamo che ogni donna ha alla sua destra un uomo. Ora consideriamo questo nuovo problema: abbiamo $ n $ coppie DU e $ m-n $ uomini da disporre come ci pare attorno ad un tavolo (si può facilmente verificare la corrispondeza biunivoca. Quindi ora, "srotolando" il tavolo $ \binom mn $ modi di mettere queste persone. Tuttavia così contiamo ogni volta alcune configurazioni più volte... Ad esempio la configurazione:

(DU)UU(DU)U

è la stessa di

(DU)U(DU)UU

quindi è un po' incasinato!

allora, siccome coi binomiali ci devo prendere la mano co sti problemi se trovate qualcosa di semplificabile vi prego di farmlo notare ( anche se trovate qualcosa di errato )
cominiciamo

consideriamo le coppie del tipo DU.. esse sono messe in sequenza e tra due di queste adiacenti vi sono $ b\geqslant0 $ uomini

quindi abbiamo $ n!m!q $ combinazioni includendo le rotazioni dove q è il numer di modi in cui posso scrivere un somma di n termini il cui risultato sia m-n (cioè m-n uomini da sistemare in n spazi tra le coppie DU)
calcoliamo q

se mettiamo tutte le m-n U accanto e poi ne aggiungiamo altre n otteniamo che abbiamo$ \displaystyle{m-1 \choose n-1} $ di mettere n-1 separatori tra 2 U di modo che ra due separatori ci sia sempre almeno una U, cioè $ \displaystyle{m-1 \choose n-1} $ modi di scrivere la somma di n termini maggiori o uguali ad 1 il cui valore è m, cioè $ \displaystyle{m-1 \choose n-1} $ modi di scrivere la somma di n termini maggiori o uguali a 0 il cui valore è m-n...

pertanto il risultato cercato senza escludere le rotazioni è

$ \displaystyle n!m!{m-1 \choose n-1} $

mentre se si vuole escludere le rotazioni bisogna osservare che ogni disposizione è ripetuta ruotata tante volte quante sono le donne pertanto escludendo le rotazioni il risultato è

$ \displaystyle \frac{n!m!{m-1 \choose n-1}}{n}=(n-1)!m!{m-1 \choose n-1 $

un'altra soluzione...
ordino prima gli m uomini intorno al tavolo; poichè non voglio considerare le rotazioni del tavolo, divido tale valore per m. i modi per fare questo sono:
$ \frac{m!}{m}=(m-1)! $
ora ho esattamente $ m $ modi per far sedere la prima donna (perchè questa puo' stare tra 2 uomini qualunque); $ m-1 $ modi per far sedere la seconda donna (perchè puo' sedere tra 2 uomini qualunque esclusi i due tra cui è seduta la prima donna);... $ m-n+1 $ modi per far sedere l'n-esima donna. Dunque i modi di far sedere le donne sono:
$ m(m-1)...(m-n+1)=\frac{m!}{(m-n)!} $
Moltiplicando questo valore per il numero di modi di far sedere gli uomini, si ha il risultato di mattilgale:
$ \frac{(m-1)!m!}{(m-n)!} $

Ciao!
Maria

Simo_the_wolf ha scritto:Ok ho capito, grazie del chiarimento

Comunque immagino che così conti alcune configurazioni più volte (quelle uguali a meno di rotazioni)... mi sbaglio?

Consideriamo il problema così: abbiamo che ogni donna ha alla sua destra un uomo. Ora consideriamo questo nuovo problema: abbiamo $ n $ coppie DU e $ m-n $ uomini da disporre come ci pare attorno ad un tavolo (si può facilmente verificare la corrispondeza biunivoca. Quindi ora, "srotolando" il tavolo $ \binom mn $ modi di mettere queste persone. Tuttavia così contiamo ogni volta alcune configurazioni più volte... Ad esempio la configurazione:

(DU)UU(DU)U

è la stessa di

(DU)U(DU)UU

quindi è un po' incasinato!

Devo dire che mi hai un po' confuso... in effetti io pensavo che i posti a sedere non fossero indistinguibili, e che quindi le configurazioni uguali a meno di rotazioni fossero diverse.
In più, leggendo le altre soluzioni, mi pare che addirittura gli uomini fra di loro siano da considerarsi distinti!
Insomma, del problema originale non ci ho capito una mazza!

A parte questo volevo sapere: come faccio leggendo un problema simile a decidere se devo contare o meno le rotazioni, o se devo considerare le donne diverse fra loro oppure no?

Uhm... il mistero si infittisce!
Ora che mi ero convinto di aver malinterpretato il problema, ho trovato sul libro delle olimpiadi italiane questo stesso problema,
e come risultato viene indicato $ \binom m n + \binom {m-1}{n-1} $!!!

Bah, rinuncio ufficialmente a capirci qualcosa...

Eh, lo so, quel problema è, a dir poco ambiguo.
La tua soluzione è giusta se si considerano distinte due disposizioni che si sovrappongono per rotazione.
I risultati di Leblanc e mattilgale effettivamente considerano distinguibili tra loro gli uomini (o le donne), ma identificano disposizioni che differiscono di una rotazione del tavolo.
A questo punto, visto che ci siamo, non è che qualcuno mette insieme i due risultati?
Insomma, considerando indistinguibili le persone dello stesso sesso e considerando due disposizioni identiche se differiscono di una rotazione, quanti modi di mettersi a tavola ci sono?

PS : effettivamente sì, il problema era sul libro delle olimpiadi italiane e li veniva risolto senza pensare alle rotazioni (il che è un poco assurdo in quanto il testo parla di tavolo rotondo).

forse ho capito male ma le rotazioni io l ho già escluse mi pare...
ed il risultato dovrebbe essere

$ \displaystle (n-1)!m!\binom {m-1}{n-1} $