Esercizio di calcolo combinatorio difficile
Ciao a tutti, questo è il mio primo post qua sul forum.
Prima di spiegare il mio problema metto il testo dell'esercizio:
"Otto celebrità si incontrano a un party. Succede così che ciascuna celebrità stringe la mano a esattamente altre 2. 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?"
Ho tentato in vari modi di risolverlo ma mi incastro sempre, purtroppo è l'unico esercizio del libro che non mi viene e ci sto sbattendo la testa da due giorni.
La via che mi sembra più prolifica è quella di dividere prima le coppie formate dalla prima stretta di mano. Per risolverlo ho immaginato due colonne da 4 persone in modo da trovare tutte le coppie possibili con una stretta di mano (ho fatto in questo modo [tex]\binom{8}{4}[/tex]*[tex]\binom{4}{4}[/tex]/2 anche se fosse sbagliato mi interessa la parte dopo) per la seconda stretta di mano invece mi trovo in trappola: non ho idea di come fare per poter calcolare tutte le combinazioni di persone sapendo che un posto non può essere occupato; riformulo così il problema, dato un'insieme di 4 elementi I={A,B,C,D} quante sigle posso creare sapendo che la A non può andare nel primo posto, la B nel secondo, la C nel terzo, e la D nel quarto?
Grazie mille in anticipo a chi potesse essermi utile, risolvendo l'esercizio o dandomi qualche dritta!
Prima di spiegare il mio problema metto il testo dell'esercizio:
"Otto celebrità si incontrano a un party. Succede così che ciascuna celebrità stringe la mano a esattamente altre 2. 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?"
Ho tentato in vari modi di risolverlo ma mi incastro sempre, purtroppo è l'unico esercizio del libro che non mi viene e ci sto sbattendo la testa da due giorni.
La via che mi sembra più prolifica è quella di dividere prima le coppie formate dalla prima stretta di mano. Per risolverlo ho immaginato due colonne da 4 persone in modo da trovare tutte le coppie possibili con una stretta di mano (ho fatto in questo modo [tex]\binom{8}{4}[/tex]*[tex]\binom{4}{4}[/tex]/2 anche se fosse sbagliato mi interessa la parte dopo) per la seconda stretta di mano invece mi trovo in trappola: non ho idea di come fare per poter calcolare tutte le combinazioni di persone sapendo che un posto non può essere occupato; riformulo così il problema, dato un'insieme di 4 elementi I={A,B,C,D} quante sigle posso creare sapendo che la A non può andare nel primo posto, la B nel secondo, la C nel terzo, e la D nel quarto?
Grazie mille in anticipo a chi potesse essermi utile, risolvendo l'esercizio o dandomi qualche dritta!
Risposte
Ciao.
Per quanto riguarda la prima stretta di mano, a me verrebbe $(8!)/(4!*2^4)=105$
Per la seconda ci devo pensare....
Quelle che chiedi tu, si chiamano dismutazioni. Se cerchi sul web trovi una formula per calcolarle. E' un po' complicatina.
Comunque per 4 elementi, lo possibilità sono 9.
Ma non so se sono applicabili in questo caso.
Per quanto riguarda la prima stretta di mano, a me verrebbe $(8!)/(4!*2^4)=105$
Per la seconda ci devo pensare....
Quelle che chiedi tu, si chiamano dismutazioni. Se cerchi sul web trovi una formula per calcolarle. E' un po' complicatina.
Comunque per 4 elementi, lo possibilità sono 9.
Ma non so se sono applicabili in questo caso.
Se ho capito:
n = numero delle persone
s = numero totale delle strette di mano
Per n < 3 ..... s = 0
n = 3 ..... s = 6 .......... A ---> B,C ; B ---> A,C ; C ---> A,B
n = 4 ..... s = 24 ........ A ---> B,C ; B ---> A,D ; C ---> A,D : D ---> B,C | A ---> B,D ; B ---> A,C ; C ---> B,D ; D ---> A,C | A ---> C,D ; B ---> C,D ; C ---> A,B : D ---> A,B
................
$ s = n*(n-1)*(n-2) $
o
$ s = (n!)/((n-3)!) $
per $ n = 8 $..... $ s = 336 $
Pardon: mi sono accorto che le strette di mano in realtà sono la metà di quanto ho considerato...
n = numero delle persone
s = numero totale delle strette di mano
Per n < 3 ..... s = 0
n = 3 ..... s = 6 .......... A ---> B,C ; B ---> A,C ; C ---> A,B
n = 4 ..... s = 24 ........ A ---> B,C ; B ---> A,D ; C ---> A,D : D ---> B,C | A ---> B,D ; B ---> A,C ; C ---> B,D ; D ---> A,C | A ---> C,D ; B ---> C,D ; C ---> A,B : D ---> A,B
................
$ s = n*(n-1)*(n-2) $
o
$ s = (n!)/((n-3)!) $
per $ n = 8 $..... $ s = 336 $
Pardon: mi sono accorto che le strette di mano in realtà sono la metà di quanto ho considerato...
Se ho ben capito il problema però la richiesta è "quante liste sono possibili ?" cioè quante combinazioni di coppie non ordinate si possono avere, non le strette di mano ...
Per esempio, una lista è ... (o dovrebbe essere ...)
$ab$
$ac$
$ce$
$eg$
$gh$
$fh$
$df$
$bd$
Quante di queste liste sono possibili ?
Per esempio, una lista è ... (o dovrebbe essere ...)
$ab$
$ac$
$ce$
$eg$
$gh$
$fh$
$df$
$bd$
Quante di queste liste sono possibili ?
"axpgn":
Se ho ben capito il problema però la richiesta è "quante liste sono possibili ?" cioè quante combinazioni di coppie non ordinate si possono avere, non le strette di mano ...
Per esempio, una lista è ... (o dovrebbe essere ...)
$ab$
$ac$
$ce$
$eg$
$gh$
$fh$
$df$
$bd$
Quante di queste liste sono possibili ?
Si, questa è una lista, ed è equivalente a tutte le sue permutazioni in quanto sia l'ordine interno degli elementi di ogni coppia che l'ordine di tutte le coppie non conta.
"nino_":Purtroppo il risultato è 3507
Se ho capito:
n = numero delle persone
s = numero totale delle strette di mano
[...]
$ s = n*(n-1)*(n-2) $
o
$ s = (n!)/((n-3)!) $
per $ n = 8 $..... $ s = 336 $
Pardon: mi sono accorto che le strette di mano in realtà sono la metà di quanto ho considerato...
"superpippone":
Ciao.
Quelle che chiedi tu, si chiamano dismutazioni. Se cerchi sul web trovi una formula per calcolarle. E' un po' complicatina.
Indipendentemente dal fatto che si possano usare o meno il fatto che tu sia riuscito a dirmi che si chiamano così mi ha aperto un nuovo mondo che il mio libro ha preferito tenermi oscuro.
Mi sono accorto che questo problema è stato dato alle gare matematiche tra MIT e Harvard e forse è il caso di spostare la discussione nello spazio riservato a questo tipo di cose (?)
In ogni caso grazie a tutti per le risposte!
"polarized":
... Si, questa è una lista, ed è equivalente a tutte le sue permutazioni in quanto sia l'ordine interno degli elementi di ogni coppia che l'ordine di tutte le coppie non conta. ...
Sarà anche così, non lo discuto, ma non è l'unica lista possibile ... cioè se $a, b, ...$ sono persone allora $a$ potrebbe stringere la mano, in un altra occasione con le stesse persone, a $d$ e $e$ invece cha a $b$ e $c$; questo chiede il problema ... IMHO.
Cordialmente, Alex
A sensazione ... ( 
) dovrebbero essere $56$ le liste possibili, cioè $(8!)/(3!5!)$.
La persona $a$ può stringere le mani a $21$ coppie diverse ($(7!)/(2!5!)$), mentre la persona $b$ può stringere la mani a $15$ coppie diverse ($(6!)/(2!4!)$) perché se contassi anche $a$ includerei alcune possibilità già contate.
Isnt' it ?
Cordialmente, Alex
) dovrebbero essere $56$ le liste possibili, cioè $(8!)/(3!5!)$.La persona $a$ può stringere le mani a $21$ coppie diverse ($(7!)/(2!5!)$), mentre la persona $b$ può stringere la mani a $15$ coppie diverse ($(6!)/(2!4!)$) perché se contassi anche $a$ includerei alcune possibilità già contate.
Isnt' it ?
Cordialmente, Alex
"axpgn":
A sensazione ... (
La persona $a$ può stringere le mani a $21$ coppie diverse ($(7!)/(2!5!)$), mentre la persona $b$ può stringere la mani a $15$ coppie diverse ($(6!)/(2!4!)$) perché se contassi anche $a$ includerei alcune possibilità già contate.
Isnt' it ?
Cordialmente, Alex
Il problema è che ogni persona stringe 2 volte la mano e che quindi ogni lettera compare due volte nelle 8 coppie totali sempre in coppia con una persona diversa. Almeno io lo ho interpretato così.
Aspetto una tua risposta
Occorre capire bene il testo.
Esaminiamo casi più semplici, con meno persone, ciascuna che stringe due mani.
Per n < 3 è impossibile (=0)
Per n = 3 c'è un caso solo? (ab, bc, ca)
Per n = 4 i casi sono 3? (ab, ac, bd, cd | ab, ad, bc, cd | ac, ad, bc, bd)
A questo punto, aumentando n, l'esame manuale diventa complicato.
Pe n = 5 la lista dovrebbe essere = 12
Se per n = 6 è = 70, si continua con n = 7 -----> 465 , n = 8 -----> 3507 , n = 9 ----->30016
Esaminiamo casi più semplici, con meno persone, ciascuna che stringe due mani.
Per n < 3 è impossibile (=0)
Per n = 3 c'è un caso solo? (ab, bc, ca)
Per n = 4 i casi sono 3? (ab, ac, bd, cd | ab, ad, bc, cd | ac, ad, bc, bd)
A questo punto, aumentando n, l'esame manuale diventa complicato.
Pe n = 5 la lista dovrebbe essere = 12
Se per n = 6 è = 70, si continua con n = 7 -----> 465 , n = 8 -----> 3507 , n = 9 ----->30016
"nino_":
Occorre capire bene il testo.
Esaminiamo casi più semplici, con meno persone, ciascuna che stringe due mani.
Per n < 3 è impossibile (=0)
Per n = 3 c'è un caso solo? (ab, bc, ca)
Per n = 4 i casi sono 3? (ab, ac, bd, cd | ab, ad, bc, cd | ac, ad, bc, bd)
A questo punto, aumentando n, l'esame manuale diventa complicato.
Pe n = 5 la lista dovrebbe essere = 12
Se per n = 6 è = 70, si continua con n = 7 -----> 465 , n = 8 -----> 3507 , n = 9 ----->30016
Come hai svolto i conti?
C'è qualcosa di oscuro che non mi è chiaro porbabilmente, comunque il risultato è giusto ti prego di spiegarmelo 
mi sembra impossibile tu abbia svolto tutte le liste accettabili, o sbaglio?
"polarized":[/quote]
[quote="nino_"]: mi sembra impossibile tu abbia svolto tutte le liste accettabili, o sbaglio?
Chiaramente non sbagli.
Dai primi valori ho utilizzato una formula ricorsiva.
"nino_":[/quote]
[quote="polarized"][quote="nino_"]: mi sembra impossibile tu abbia svolto tutte le liste accettabili, o sbaglio?
Chiaramente non sbagli.
Dai primi valori ho utilizzato una formula ricorsiva.[/quote]
Sono metodi a me sconosciuti purtroppo, almeno per quanto riguarda il percorso di studi fatto finora
Formula ricorsiva significa semplicemente (si fa per dire ) che ha trovato (o intuito o dimostrato) un legame (una formula) tra il caso $n$ e il caso $n+1$.
Esaminando i casi più semplici (come $n=1, n=2, n=3, ...$) può capitare di intuire una correlazione (che però poi va dimostrata); a quel punto, in teoria, puoi calcolare qualsiasi termine.
Cordialmente, Alex
P.S.: ho iniziato a battere quella strada ma non ho visto il legame ...
) che ha trovato (o intuito o dimostrato) un legame (una formula) tra il caso $n$ e il caso $n+1$.Esaminando i casi più semplici (come $n=1, n=2, n=3, ...$) può capitare di intuire una correlazione (che però poi va dimostrata); a quel punto, in teoria, puoi calcolare qualsiasi termine.
Cordialmente, Alex
P.S.: ho iniziato a battere quella strada ma non ho visto il legame ...
La ricorsione che ho ricavato è:
$ a(0)=0; a(1)=0; a(2)=0; a(3)=1 $
Per n>2
$ a(n+1) = n*a(n) + (n*(n-1))/2 * a(n-2) $
Esaminando i casi con n piccolo, il mio primo approccio è stato che per ogni n>3 occorreva moltiplicare il valore di a(n-1) per n.
Per questo, avevo postato nel mio primo messaggio la sequenza relativa al numero delle strette di mano (che è uguale alla lista richiesta moltiplicata per n), sbagliando però per n>4.
In effetti, se analizziamo le liste possibili N_l, abbiamo:
n=3 ; N_l=1 ; ab-ac-bc
n=4 ; N_l=3 ; ab-ac-bd-cd ; ab-ad-bc-cd ; ac-ad-bc-bd
che possono essere scritte:
a(b-c) + d(b-c) ; b(a-c) + d(a-c) ; c(a-b) + d(a-b)
n=5 ; N_l=12 ; fatte le prime due liste a(b-c) | bd, ce, de | bc, cd, de |
è sufficiente invertire le lettere delle due terzine da abbinare con
a(b-d) , a(b-e) , a(c-d) ; a(c-e) ; a(d-e)
per ottenere le 12 liste totali.
Con n=6 ho allora pensato che il risultato fosse $ N_l = 12*5 = 60 $;
in realtà, a queste liste vanno aggiunte altre $ (C(6,3))/2 = 10 $, cioè gli ambi dell'n precedente moltiplicato per il numero delle liste di n-3.
Queste liste aggiuntive si ottengono unendo le combinazioni di due terzine, ad esempio ab-ac-bc | de-df-ef
e quindi per $ n=6 ; N_l=70 $
Le liste corrispondenti a n>6 si calcolano facilmente con la formula che ho messo all'inizio.
$ a(0)=0; a(1)=0; a(2)=0; a(3)=1 $
Per n>2
$ a(n+1) = n*a(n) + (n*(n-1))/2 * a(n-2) $
Esaminando i casi con n piccolo, il mio primo approccio è stato che per ogni n>3 occorreva moltiplicare il valore di a(n-1) per n.
Per questo, avevo postato nel mio primo messaggio la sequenza relativa al numero delle strette di mano (che è uguale alla lista richiesta moltiplicata per n), sbagliando però per n>4.
In effetti, se analizziamo le liste possibili N_l, abbiamo:
n=3 ; N_l=1 ; ab-ac-bc
n=4 ; N_l=3 ; ab-ac-bd-cd ; ab-ad-bc-cd ; ac-ad-bc-bd
che possono essere scritte:
a(b-c) + d(b-c) ; b(a-c) + d(a-c) ; c(a-b) + d(a-b)
n=5 ; N_l=12 ; fatte le prime due liste a(b-c) | bd, ce, de | bc, cd, de |
è sufficiente invertire le lettere delle due terzine da abbinare con
a(b-d) , a(b-e) , a(c-d) ; a(c-e) ; a(d-e)
per ottenere le 12 liste totali.
Con n=6 ho allora pensato che il risultato fosse $ N_l = 12*5 = 60 $;
in realtà, a queste liste vanno aggiunte altre $ (C(6,3))/2 = 10 $, cioè gli ambi dell'n precedente moltiplicato per il numero delle liste di n-3.
Queste liste aggiuntive si ottengono unendo le combinazioni di due terzine, ad esempio ab-ac-bc | de-df-ef
e quindi per $ n=6 ; N_l=70 $
Le liste corrispondenti a n>6 si calcolano facilmente con la formula che ho messo all'inizio.
Davvero interessante, anche se purtroppo non é il metodo risolutivo corretto é stato comunque utile!
E quale sarebbe il "metodo risolutivo corretto?"
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo