Newsgroup: it.hobby.enigmi
Titolo: [MA]Ménages

N uomini e N donne sono seduti intorno ad un tavolo circolare.In quanti casi
ogni uomo avrą al suo fianco almeno una donna?Naturalmente ogni uomo č
diverso da  tutti gli altri ed č quindi distinguibile dagli
altri,analogamente per le donne.Come caso particolare N=5.Spero di essere
stato abbastanza elegante.

 Spero di essere stato abbastanza elegante.
Elegante lo è, ma anche molto tosto, mi pare.
..
.
.
.
.
.
.
.
.
.
.
Non ho trovato molti appigli, quindi provo con la solita brute-force ed una
valutazione spannometrica.
Se i posti sono decisi casuamente ogni uomo ha C(N-1,2)/C(2N-1,2) probabiltà
di capitere tra altri due uomini. Chiamiamo p(N) la probabiltà contraria,
che vale 1-(N-1)(N-2)/((2N-1)(2N-2))=3N/(4N-2). Questa è la probabilità che
un prefissato uomo abbia almeno una donna al suo fianco, e come era lecito
aspettarsi tende a 3/4. Chiaramente le sorti degli uomini non sono
indipendenti tra di loro, però possiamo utilizzare p(N)^N come stima della
percentuale dei casi in cui tutti gli uomini sono felicemente vicini ad
almeno una donna. Visto che i possibili modi di piazzare 2N persone a tavola
sono (2N-1)!, possiamo stimare il numero di disposizioni favorevoli.
N       disp.      stima
2          6          6
3         84         87.5
4       2736       2720.5
5     146880     145833.3
6   12182400   11974424.9
Quindi i risultati sembrano confortare la previsione,
D(N) = (2N-1)!*P(N)^N =
= (2N-1)!*[3N/(4N-2)]^N
Silv:o)

 ha scritto nel messaggio
news:978ibp$o482b$1...@ID-49224.news.dfncis.de...

Io sono un fanatico delle forme chiuse e determinate,ma devo confessare che
questa approssimazione da te trovata mi ha davvero colpito !-/
Complimentoni . 8-D
Onoff.

 6   12182400   11974424.9
Ignoro per il momento le rotazioni attorno il tavolo, considerandole
differenti, come se ci fosse un capotavola.
Comincio coll'esaminare i casi piu' semplici sostituendo maschi e
femmine con "zeri" e "uno".
N=2   
Costruisco un grafo ad albero partendo dal capotavola e procedendo in
senso orario attorno il tavolo, ogni volta che e' possibile sistemare
uno zero od un uno, l'albero avra' una diramazione, per i dati del
problema, occorre solo fare attenzione di non mettere 3 simboli uguali
in successione.
Fra parentesi metto il numero delle possibili scelte. La prima volta che
piazzo uno zero  posso scegliere fra  N maschi, la seconda volta fra
N-1...ecc. Lo stesso per le donne. Ottengo:
 
                       0 (2)
                      / \
                     /   \
                (1) 0     1 (2)
                   /     / \
                  /     /   \
             (2) 1     0 (1) 1 (1)
                /     /       \
               /     /         \
          (1) 1     1 (1)       0 (1)
Vediamo che ci sono 3 possibili rami. Scambiando uomini e donne coi loro
simili, ciascuno ramo genera 2*2*1*1 = 4  permutazioni .(In generale
ogni ramo ne genera N!^2)
In tutto 4*3=12 che radoppiamo perche' vanno aggiunte le 12 disposizioni
dell'albero complementare, che si ottiene mettendo capotavola una donna,
il totate delle sol. per N=2 diventa cosi' 24, se desideriamo solo le
sol. fondamentali non resta che dividere per 2N che sono le simmetrie
del tavolo, in questo caso 24/4 = 6.
Vado avanti, e mi disegno il grafo per N=3
                                   0
                                 /   \
                                /     \
                               0       1
                              /       /  \
                             1       0     1
                            / \     / \     \
                           0   1   0   1     0 
                          /    |   |  / \    |\
                         1     0   1  0  1   0 1
                         |     |   |  |  |   |  \
                         1     1   1  1  0   1   0
Ottenendo 7 rami (14 con i complementari), ciascuno vale, come visto
(3*2*1)^2=36. 36*14=504 sol. differenti.
 504/6=84 sol. fondamentali.
Per avere una sol. generale basterebbe sapere quanti sono i rami in
funzione di N.
A questo punto del ragionamento, ho visto la sol. si Silvio, che sfrutto
subito! Facendo i conti a ritroso mi calcolo i rami. Ecco lo specchietto
risultante:
N   rami +compl   N!^2     tot.sol    /2N (fondam)    
 
2     3     6       4          24         6
3     7    14      36         504        84
4    19    38     576       21888      2763
5    51   102   14400     1468800    146880  
6   141   282  518400   146188800  12182400 
Allora i rami sono 1,3,7,19,51,141....... corro subito a consultare
Sloane e... eccola li' !
E' l'espansione di (1+x+x^2)^n, studiata dall'immancabile Eulero. La
serie continua con  393,1107,3139,8953....
Se tutto va bene le sol per N=7 sono:
7  393   786  25401600  19965657600  1426118400
Ce la fai Silvio a controllare ?
La relazione l'abbiamo trovata la parte piu' difficile e' dimostrare che
e' effettivamente cosi'.
ciao :) dario

 e' effettivamente cosi'.
Neanche poi tanto. Stai a vedere.
Immagina che le N donne prendono posto attorno al tavolo, senza sedersi. Tra
una donna e l'altra possono inserirsi 0, 1 o 2 uomini. In pratica dobbiamo
contare in quanti modi possibili possiamo scegliere N addendi, compresi tra
0 e 2, in modo che la somma sia N.
Ora, cos'è il coefficiente di x^n nell'espansione di (1+x+x^2)^n, se non
questo numero?
Faccio un esempio con n=3 per facilitare la comprensione:
(1+x+x^2)(1+x+x^2)(1+x+x^2) =
= 1*1*1 + 1*1*x + 1*1*x^2 + 1*x*x^2+ ... =
=x^(0+0+0) + x^(0+0+1) + x^(0+0+2) + x^(0+1+2) + ... =
= 000 + 001 + 002 + 012 + ...
solo il quarto di questi addendi contribuirà ad incrementare le x^3, altri
contributi verranno da 1*x^2*x (021), da 102,111,120,201,210, sette in
totale.
Infatti (1+x+x^2)^3=x^6+3x^5+6x^4+7x^3+6x^2+3x+1
Ci sono modi semplici per calcolarsi questi coefficienti anche a mano
(1+x+x^2)^2 = 1+ x+ x^2
               + x+ x^2+ x^3
             _____+_x^2+_x^3+x^4_=
              1+2x+3x^2+2x^3+x^4
per le potenze successive scrivo solo i coeff.
1 2 3 2 1
  1 2 3 2 1
____1_2_3_2_1_
1 3 6 7 6 3 1
  1 3 6 7 6 3 1
____1_3_6_7_6_3_1_
siamo arrivati a
1,4,10,16,19,16,10,4,1
Il coeff. centrale è quello che ci interessa.
In pratica possiamo costruire un riangolo di Pascal di grado tre, dove i
termini si ottengono sommando i tre che stanno sopra:
n
0                  1
1               1  1  1
2            1  2  3  2  1
3         1  3  6  7  6  3  1
4      1  4 10 16 19 16 10  4  1
5   1  5 15 30 45 41 45 30 15  5  1
nella colonna centrale ci sono i nostri numeri!
Silv:o)

 6   141   282  518400   146188800  12182400
Ho usato un altro approccio e trovo valori differenti. Evidentemente a
qualcuno (probabilmente a me) sfugge qualcosa.
Forse mi sono incasinato con il fatto delle rotazioni e del capotavola, ma
in tal caso penso che i rapporti tra i miei ed i vostri risultati dovrebbero
essere interi. Boh?
Ecco comunque la mia soluzione, provate a vedere cosa non va.
Considerate le 2N persone disposte attorno al tavolo in un qualunque modo,
posso contare k gruppi di uomini alternati ad altrettanti gruppi di donne
(ciascun gruppo eventualmente formato da una sola persona).
Il numero k può variare da 1 (disposizione puritana, tutti gli uomini da una
parte e le donne dall'altra) ad N (perfetta alternanza uomini-donne).
Mi interessano solo i casi in cui tutti i gruppi siano formati da due
persone o da una sola persona.
Condizione necessaria è che sia k<=N/2.
Per ogni valore di k risultano definiti il numero d di gruppi duplici ed il
nupero s di gruppi singoli.
d=N-k
s=k-d
i d gruppi duplici di uomini possono essere disposti in C(k,d) modi diversi
per esempio
N=3
per k=2 avrò d=1 s=1 (un gruppo duplice ed uno singolo) con due disposizioni
d-s  s-d
per k=3, d=0 s=3, unica disposizione s-s-s
ad ognuna delle disposizioni corrispondono N! permutazioni degli N uomini,
quindi
C(k,d)*N! possibilità
da elevare al quadrato, per tener conto anche delle disposizioni e
permutazioni delle donne.
Sommando i valori per tutti i k compresi tra N/2 ed N, dovrei avere il
risultato.
n   k   d    C(k,d)   C*n!   (C*n!)^2
3   2   1      2      12       144
3   3   0      1       6        36
tot                            180
4   2   2      1      24       576
4   3   1      3      72      5184
4   4   0      1      24       576
tot                           6336
5   3   2      3     360    129600
5   4   1      4     480    230400
5   5   0      1     120     14400
tot                         374400
6   3   3      1     720     518400
6   4   2      6    4320   18662400
6   5   1      5    3600   12960000
6   6   0      1     720     518400
tot                        32659200
ciao
paolo

 nella colonna centrale ci sono i nostri numeri!
Cacchio ! Silvio, che bonta'.
:) dario

 ha scritto nel messaggio
news:1h3m6.9308$q97.1...@twister1.tin.it...

Caro Paolo,
In questo vortice di alberi e programmi ti posto la forma chiusa (neanche
tanto,ma non penso si possa semplificare ulteriormente) sperando ti possa
tornare utile per ricostruire il ragionamento.
     N!(N-1)!SumC(N,k)C(N-k,K)   sommata su k
Onoff

 tot                           6336     2160
E sono meno delle previste 2736. Questo perché, come detto, mancano i casi
con 3 donne di fila, che vedono la quarta donna seduta tra due gruppi di due
uomini:
DDD UU D UU
permutando gli uomini e le donne nello schema si hanno 4!^2=576 altri
possibili tavoli coi quali raggiungiamo il risultato già visto di 2736
tavoli.
Silv:o)

 avevamo trovato noi.
questo paragrafetto l'ho riscritto in altri termini ma ho dimenticato di
cancellarlo prima dell'invio: repetita juvant
Silv:o)

 ma non è la stessa cosa per le donne:
E' vero, avevo letto distrattamente e mi era parso che la condizione fosse
simmetrica.
Ma la commissione pari opportunità, che ci sta a fare?
:-)
grazie per i chiarimenti
ciao
paolo

 Cacchio ! Silvio, che bonta'.
Sono d'accordo con te :))))
Soprattutto perché il rusultato trovato č ben piů generico.
Se ora qualcuno ci chiedesse quanti tavoli si posso formare con d donne e u
uomini in modo che ogni uomo abbia almeno una donna al suo fianco, gli
risponderemmo al volo:
č il coefficiente di x^u nello sviluppo di (1+x+x^2)^d. E col triangolo di
Pascal3 potremmo pure trovarcelo in pochissimo tempo, (tendente a zero, con
un foglio elettronico).
Ora che ci penso, la simmetria mica me la aspettavo. Se ci sono 10 donne, 7
uomini si possono mischiare a loro negli stessi modi in cui possono farlo 3
uomini (parlo ovviamente solo di schemi U-D: le cose cambiano se
distinguiamo i commensali).
Per esempio, se ci chiedessero quanti tavoli si formano con 3 uomini e 5
donne potremmo al volo rispondere: 30, da moltiplicarsi per 4!*3! se
distinguiamo i commensali (in generale per (d-1)!*u!).
Ciao, Silv:o)