Calcolo combinatorio

Aletzunny1
Otto celebrità si incontrano a un party. Succede così che ciascuna celebrità stringe la mano esattamente ad altre due. Un ammiratore tiene una lista di tutte le coppie (non ordinate ) di celebrità che si sono strette la mano. Se l’ordine non conta, quante diverse liste sono possibili?

So benissimo che c'è la soluzione online però non capisco come viene risolto...
Qualcuno ha un metodo magari più semplice oppure è in grado di spiegarmi la soluzione già presente sul web...grazie

Risposte
giammaria2
Io ho calcolato che sono possibili 3255 liste, ma la mia soluzione è lunga e brutta; inoltre non do garanzie sull'esattezza né del ragionamento né dei calcoli.
Parli di una soluzione sul web; puoi indicarla?

mgrau
La prima celebrità, per la sua prima stretta di mano, può scegliere fra 7 possibilità, e per la seconda fra 6. Quindi, 42 possibilità.
Le celebrità sono 8, quindi 42*8.
In questo modo però ogni coppia è contata due volte, quindi alla fine 1/2 * 42 * 8 = 168
(da dove viene 3255?)

giammaria2
No, mgrau, non sono d'accordo. Tanto per cominciare, le due celebrità salutate dalla prima possono essere scelte in $C_(7,2)=21$ modi (la lista non si modifica se le due si scambiano fra loro). In secondo luogo, considerando una delle due salutate, deve dare solo più un saluto, scegliendo fra 6 celebrità: è una situazione diversa dalla prima. Ed infine, anche se tutto il resto fosse giusto, le varie possibilità vanno moltiplicate fra loro ed non per 8: il risultato sarebbe $42^8$ (forse moltiplicato per $1/2$).

Chiedi da dove viene il mio 3255, quindi scriverò la mia risposta, ma lo farò questa sera perché, come ho detto, è lunga ed adesso ho altri impegni.

giammaria2
Come promesso, do la mia risposta.

Ragionamento iniziale.
Può capitare che un gruppo di $n$ celebrità consumi nei reciproci saluti tutte le strette di mano a sua disposizione; dico allora che si ha un ciclo da $n$. Per le celebrità rimanenti è come de quelli non esistessero e devono formare un altro ciclo.
Si ha $n>=3$, quindi le possibilità sono:
a) un ciclo da 8
b) un ciclo da 3 seguito da un ciclo da 5
c) un ciclo da 5 seguito da un ciclo da 3
d) due cicli da 4 consecutivi.
Indico con $k$ il numero di celebrità da considerare all'inizio di un ciclo e con a1 la prima che considero in quel ciclo; le altre sono a2, a3, ... , numerate nell'ordine in cui considero la loro prima stretta di mano. Il ragionamento prosegue considerandone la seconda, fino alla chiusura del ciclo.
Quando in un ciclo vengono introdotte due nuove celebrità, hanno tre possibilità:
1) si stringono la mano fra loro, chiudendo il ciclo;
2) stringono la mano ad una stessa altra celebrità: anche così il ciclo si chiude, con una celebrità in più;
3) stringono la mano a due celebrità diverse; il ciclo prosegue e ci sono di nuovo le tre possibilità.

Calcoli
a1 stringe la mano ad a2, a3, che possono essere scelti in $C_(k-1,2)=((k-1)(k-2))/2$ modi diversi. Poi
1) se a2 ed a3 si stringono la mano si chiude il ciclo da 3, che quindi origina $((k-1)(k-2))/2$ liste;
2) se entrambi stringono la mano ad a4 (che può essere scelto in $k-3$ modi) si chiude il ciclo da 4, corrispondente a $((k-1)(k-2)(k-3))/2$
3) se stringono la mano ad a4, a5 il ciclo continua. La scelta di a4, a5 può essere fatto in $D_(k-3,2)=(k-3)(k-4)$ modi (questa volta sono davvero disposizioni perché non sono scambiabili)

Siamo quindi arrivati ad $((k-1)(k-2)(k-3)(k-4))/2$ e vediamo di nuovo le possibilità:
1 bis) se a4 ed a5 si stringono la mano si chiude il ciclo da 5, che quindi origina $((k-1)(k-2)(k-3)(k-4))/2$ liste. Ora mi interessa solo più il ciclo da 8, quindi proseguo i calcoli con $k=8$ e passo direttamente a
3 bis) a4 ed a5 stringono la mano ad a6 e a7, sceglibili in $D_(3,2)=3*2$ modi. La conclusione è unica: a6 ed a7 stringono entrambi la mano ad a8: in totale $(7*6*5*4*3*2)/2$ liste.

Ora riprendo i casi a, b, c,d, indicando con $L$ la numerosità delle relative liste.
a) con un ciclo da 8 e k=8, ho $L=(7*6*5*4*3*2)/2=2520$
b) con un ciclo da 3 (k=8) seguito da un ciclo da 5 (k=5) ho $L=(7*6)/2*(4*3*2*1)/2=252$
c) con un ciclo da 5 (k=8) seguito da un ciclo da 3 (k=3) ho $L=(7*6*5*4)/2*(2*1)/2=420$
d) con due cicli da 4 consecutivi (k=8 e k=4) ho $L=(7*6*5)/2*(3*2*1)/2=63$
In conclusione
$L_("totale")=2520+252+420+63=3255$

EDIT
Nel caso d) ho dimenticato il fattore 5; vanno quindi corretti sia il suo risultato che il totale.
Rileggendo, mi rendo conto che la dimostrazione poteva essere molto abbreviata, ma ormai l'ho scritta così. Mi sembra anche più convincente.

mgrau
Effettivamente, @giammaria, sono stato un po' affrettato nella risposta.
Purtroppo non riesco a capire bene la tua argomentazione...
Però ripensandoci trovo molto interessante la tua idea dei cicli, mi è venuto in mente di rappresentare il problema in forma grafica: se indichiamo una celebrità con un nodo, si tratta di disegnare 8 nodi, da ciascuno dei quali escono due linee.
Ora, come hai già detto tu, questo si può ottenere:
con un anello di 8 nodi
con un anello di 5 e uno di 3
con due anelli di 4

Nei casi di due anelli, si tratta anche di vedere in quanti modi si possono suddividere gli 8 nodi in due gruppi, di 5 e 3, e di 4 e 4, questo mi pare un problema standard che dà rispettivamente $(8!)/(5!3!)$ e $(8!)/(4!4!)$
Si tratterebbe poi di vedere in quanti modi $D_N$ si possono disporre n oggetti in un anello: anche questo dovrebbe essere un problema standard, ma non mi viene in mente la soluzione. Salvo il caso di 3, che si può fare in un modo solo.
Alla fine mi pare che la risposta sarebbe $D_8 + (8!)/(5!3!)D_5D_3 + (8!)/(4!4!)D_4D_4$. O no?

Poi mi pare interessante vedere cosa succede cambiando un po' la situazione.
Per esempio, se invece di 2 saluti c'è un numero N diverso. Esiste una soluzione, per ogni numero di nodi?
Per N = 1, si formano delle coppie. Per cui il numero dei nodi deve essere pari.
Per N = 2, come qui, pare che che non ci siano vincoli sul numero dei nodi, si possono formare anelli con un qualsiasi numero >=3 di vertici
Per N = 3? Mi pare che venga fuori una struttura in cui da ogni nodo escono 3 linee. Questo succede per esempio se sono disposti come i vertici di un tetraedro, 4, di un cubo, 6, di un dodecaedro, 20. Però va bene anche un quadrato, in cui ogni vertice è unito agli altri 3, quindi con i lati e le diagonali (forse è equivalente al tetraedro?). Insomma, il numero dei nodi deve essere scomponibile in parti di 4, 6 o 20 nodi.
Per N = 4? Va bene un ottaedro, 6 nodi. Il pentagono, con lati e diagonali, 5. Poi c'è il reticolo quadrato, ma deve essere illimitato. Altre possibilità?
N = 5, l'icosaedro, 12, e l'esagono piano con lati e diagonali.
N generico, vedo solo il poligono di N+1 vertici, con lati e diagonali.

Tutte queste possibilità sono però condizioni sufficienti per soddisfare le condizioni. Sono anche necessarie? Mah...

giammaria2
Interessante la tua idea dei nodi che, con N=2, origina gli anelli; mi pare giusto anche il tuo ragionamento e la formula conseguente. Con una perplessità: io ottengo risultati diversi a seconda che il ciclo da 3 segua o preceda quello da 5, mentre per te è lo stesso (avrò sbagliato io? La cosa mi era sembrata strana).Se vuoi, puoi fare i calcoli e confrontare il tuo risultato col mio; con la correzione indicata nell'edit, il mio diventa 3507.
Per il caso di N generico, mi arrendo.

giammaria2
@ mgrau
Ci ho ripensato, e la tua formula va modificata; lo scrivo in una nuova mail perché se io modificassi quella precedente (che forse hai già letto) non ne saresti avvisato.
In un anello con k nodi si può partire da uno qualsiasi di essi, quindi $D_k$ va diviso per k; inoltre non ci importa il verso di percorrenza, quindi c'è anche una divisione per 2. Tu stesso scrivi "Salvo il caso di 3, che si può fare in un modo solo", ma poi nella formula compare $D_3$, che vale 6 ma dà 1 con le divisioni indicate.

mgrau
Come dicevo, il mio problema era di determinare $D_N$, cioè il numero di modi diversi di disporre N nodi su un anello.
Posso provare a questo modo. Considero i posti sull'anello numerati da 1 a N, Allora ci sono $N!$ di disporre gli N nodi.
Poi però l'anello può essere ruotato di N passi senza cambiare la configurazione, così il numero va diviso per N e diventa $(N-1)!$
Infine, ogni configurazione può essere percorsa indifferentemente in senso orario o antiorario, così dividiamo ancora per 2.
Infine abbiamo $D_N = ((N-1)!)/2$
Allora la mia formula
$D_8 + (8!)/(5!3!)D_5D_3 + (8!)/(4!4!)D_4D_4$ diventa
$2520 + 42*12 + 70*3 = 3234$

superpippone
Ho 3 situazioni diverse possibili.
In ognuna di esse le celebrità sono sedute ad un tavolo rotondo, e stringono la mano ai 2 vicini (quello di destra, e quello di sinistra).
A) Unico tavolo da 8: il primo può stringere la mano a 21 coppie possibili: $21*5*4*3*2*1=2.520$

B) Due tavoli da 4.Il primo può stringere la mano a 3 coppie possibili: $(C_(8,4)*3*1*3*1)/2=(70*3*3)/2=315$

C) Un tavolo da 5, ed un tavolo da 3. Il primo (da 5) può stringere la mano a 6 coppie possibili. $C_(8,5)*6*2*1*1=56*6*2=672$

Totale: $2.520+315+672=3.507$

giammaria2
Strano! Il risultato 3507 di superpippone è lo stesso ottenuto dal mio primo ragionamento, dopo la correzione di un errore di calcolo; vedi la mia mail del 8-4, alle ore 20,38 del mio computer. Di solito questa coincidenza è indizio di esattezza; peccato che, dopo il confronto con le vostre idee, io ora ottenga un altro risultato.
Il mio ultimo ragionamento è questo: potendo scegliere fra k persone e volendo formare un ciclo (o anello, o tavolo: in questo caso sono sinonimi) di n persone, mi interessa quali prendo ed il loro ordine, cioè mi interessa $D_(k,n)$. In base a quanto detto, va però diviso per $2n$, quindi la risposta è
$E_(k,n)=D_(k,n)/(2n)=(k(k-1)...(k-n+1))/(2n)$
Se $k=n$ le disposizioni diventano permutazioni ma la formula non cambia.

Quindi le possibilità sono:
- un ciclo da 8, che dà
$E_(8,8)=(8*7...*1)/(2*8)=(8!)/16=2520$
- un ciclo da 3 ed uno da 5 (non importa in che ordine) che danno
$E_(8,3)*E_(5,5)=(8*7*6)/(2*3)*(5*4...*1)/(2*5)=(8!)/60=672$
- due cicli da 4, che danno
$E_(8,4)*E_(4,4)=(8*7..*5)/(2*4)*(4*3...*1)/(2*4)=(8!)/64=630$

La somma dà 3822.

axpgn
[ot]Ragazzi, se ne trovate altri quattro, ci diamo appuntamento da qualche parte e verifichiamo ... :-D[/ot]

Aletzunny1
Scusate se tardo a rispondere ma volevo capire bene il procedimento e avevo poco tempo in questi giorni...
Il risultato "corretto" é 3507

mgrau
@axpgn[ot]dovremmo essere delle celebrità...[/ot]
C'è qualcosa di strano...
superpippone trova $2520 + 672 + 315 = 3507$, trovato in prima battuta anche da giammaria, e che l'OP dichiara essere la risposta giusta
giammaria poi trova $2520 + 672 + 630 = 3822$
io avevo trovato $3234$, ma avevo sbagliato i calcoli, in effetti la mia formula
$D_8 + (8!)/(5!3!)D_5D_3 + (8!)/(4!4!)D_4D_4 $ dove $D_N = ((N-1)!)/2$, dà $2520 + 56*12 + 70*9 = 2520 + 672 + 630 = 3822$, come la seconda risposta di giammaria.
Si noti che $630 = 2 * 315$
Ora, com'è che proprio il termine 4 + 4 di superpippone è le metà degli altri due? Da dove sbuca questo fattore 2? Chi ha ragione, e dove sta l'errore?

axpgn
@mgrau
[ot]Perché? Non lo siamo? :-D[/ot]

Aletzunny1
"superpippone":
Ho 3 situazioni diverse possibili.
In ognuna di esse le celebrità sono sedute ad un tavolo rotondo, e stringono la mano ai 2 vicini (quello di destra, e quello di sinistra).
A) Unico tavolo da 8: il primo può stringere la mano a 21 coppie possibili: $21*5*4*3*2*1=2.520$

B) Due tavoli da 4.Il primo può stringere la mano a 3 coppie possibili: $(C_(8,4)*3*1*3*1)/2=(70*3*3)/2=315$

C) Un tavolo da 5, ed un tavolo da 3. Il primo (da 5) può stringere la mano a 6 coppie possibili. $C_(8,5)*6*2*1*1=56*6*2=672$

Totale: $2.520+315+672=3.507$


Stessa risoluzione avuta in classe

superpippone
Nella situazione 4+4 divido per due, perchè ci sono delle ripetizioni.
Voglio dire se al primo tavolo ho a-b-c-d-al secondo tavolo ho e-f-g-h.
E se al primo tavolo ho e-f-g-h- al secondo avrò a-b-c-d.
E, ai nostri scopi, le due situazioni sono identiche.

P.S. $3.507$ è anche la soluzione che ho trovato su internet

mgrau
"superpippone":

se al primo tavolo ho a-b-c-d-al secondo tavolo ho e-f-g-h.
E se al primo tavolo ho e-f-g-h- al secondo avrò a-b-c-d.
E, ai nostri scopi, le due situazioni sono identiche.


E' vero! :)

giammaria2
Concordo anch'io; non ci avevo pensato.
La mia prima soluzione è però concettualmente sbagliata e dà il corretto 3507 solo per caso. Forse la si può giustificare con qualche strano ragionamento, ma non ne vale la pena.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.