In quanti modi possono essere distribuiti a 5 persone un guanto destro e uno sinistro da 6 paia di guanti distinguibili in modo tale che nessuna persona abbia un paio? (quindi tutti devono sempre avere un guanto destro e uno sinistro ma devono essere spaiati , nessuno può cioè avere un paio iniziale)
HINT:provare a scrivere la soluzione in termini di $ D_n $ cioè derangements di n elementi
uso i derangements
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Senza usare i derangements 
...
Passo 1:
Conto tutte le configurazioni in cui ogni persona abbia un guanto destro e un guanto sinistro..
Sia $ D_{n;k} $ il numero di disposizioni semplici di classe k di n elementi.
Posso scegliere i guanti destri in $ D_{6;5} $ modi distinti e lo stesso per i sinistri.
Le configurazioni possibili sono: $ (D_{6;5})^2= (6!)^2 $
Passo 2:
Scelto un numero $ i $ di paia di guanti presenti (come minimo; ovvero se i=2 posso avere per esempio anche 4 paia presenti
) ho $ {6 \choose i} $ modi differenti per scegliere i paia di guanti.
Una volta scelti i paia ho $ D_{5;i} = {5 \choose i}i! $ modi distinti per darli alle 5 persone.
I guanti rimasti sono 6-i destri e 6-i sinistri, li distribuisco alle 5-i persone rimaste in $ (D_{6-i;5-i})^2 $ modi possibili (analogamente al passo 1) .
Ovvero dato un numero i di paia di guanti ho
$ {6 \choose i}{5 \choose i}i!(D_{6-i;5-i})^2 $ configurazioni possibili con (come minimo) quel numero di paia di guanti.
Passo 3:
Per il PIE (principio di inclusione-esclusione) ho quindi
$ \sum_{i=1}^{5}(-1)^{i+1}{6 \choose i}{5 \choose i}i!(D_{6-i;5-i})^2 $ configurazioni non accettabili perchè contenenti almeno un paio di guanti.
Le accettabili sono
$ (6!)^2-\sum_{i=1}^{5}(-1)^{i+1}{6 \choose i}{5 \choose i}i!(D_{6-i;5-i})^2 $ = $ \sum_{i=0}^{5}(-1)^{i}{6 \choose i}D_{5;i}((6-i)!)^2 $
Ricordo che $ D_{n;k}={n \choose k}k! = \frac{n!}{(n-k)!} $
Buona Serata. Simone
...Passo 1:
Conto tutte le configurazioni in cui ogni persona abbia un guanto destro e un guanto sinistro..
Sia $ D_{n;k} $ il numero di disposizioni semplici di classe k di n elementi.
Posso scegliere i guanti destri in $ D_{6;5} $ modi distinti e lo stesso per i sinistri.
Le configurazioni possibili sono: $ (D_{6;5})^2= (6!)^2 $
Passo 2:
Scelto un numero $ i $ di paia di guanti presenti (come minimo; ovvero se i=2 posso avere per esempio anche 4 paia presenti
) ho $ {6 \choose i} $ modi differenti per scegliere i paia di guanti.Una volta scelti i paia ho $ D_{5;i} = {5 \choose i}i! $ modi distinti per darli alle 5 persone.
I guanti rimasti sono 6-i destri e 6-i sinistri, li distribuisco alle 5-i persone rimaste in $ (D_{6-i;5-i})^2 $ modi possibili (analogamente al passo 1) .
Ovvero dato un numero i di paia di guanti ho
$ {6 \choose i}{5 \choose i}i!(D_{6-i;5-i})^2 $ configurazioni possibili con (come minimo) quel numero di paia di guanti.
Passo 3:
Per il PIE (principio di inclusione-esclusione) ho quindi
$ \sum_{i=1}^{5}(-1)^{i+1}{6 \choose i}{5 \choose i}i!(D_{6-i;5-i})^2 $ configurazioni non accettabili perchè contenenti almeno un paio di guanti.
Le accettabili sono
$ (6!)^2-\sum_{i=1}^{5}(-1)^{i+1}{6 \choose i}{5 \choose i}i!(D_{6-i;5-i})^2 $ = $ \sum_{i=0}^{5}(-1)^{i}{6 \choose i}D_{5;i}((6-i)!)^2 $
Ricordo che $ D_{n;k}={n \choose k}k! = \frac{n!}{(n-k)!} $
Buona Serata. Simone
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Sta volta usando i derangements
Sia $ D_n $ il numero dei derangements di n elementi.
Fisso una qualsiasi delle 6! permutazioni della stringa dei colori dei guanti destri (nella prime 5 posizioni metto ordinatamente i guanti destri distribuiti, nell'ultima metto il guanto destro non distribuito) e calcolo quante sono le configurazioni dei guanti sinistri valide.
Devo scegliere un guanto sinistro da non distribuire.
Se il guanto sinistro scelto è di un colore differente da quello destro non distribuito allora, considerando la stringa dei colori dei guanti sinistri come una permutazione della stringa dei colori dei guanti destri non devo avere punti fissi.
Ho quindi $ D_6 $ possibilità.
Se il guanto sinistro scelto è dello stesso colore di quello destro non distribuito allora gli altri 5 guanti sinistri non devono essere dati alle stesse persone a cui è stato dato il destro dello stesso colore.
Ho $ D_5 $ possibilità.
La soluzione è quindi: $ 6!(D_6+D_5) $
Ricordo che $ D_n = n! \sum_{k=0}^{n}(-1)^k \frac{1}{k!} $.
Buona serata Simone.
Sia $ D_n $ il numero dei derangements di n elementi.
Fisso una qualsiasi delle 6! permutazioni della stringa dei colori dei guanti destri (nella prime 5 posizioni metto ordinatamente i guanti destri distribuiti, nell'ultima metto il guanto destro non distribuito) e calcolo quante sono le configurazioni dei guanti sinistri valide.
Devo scegliere un guanto sinistro da non distribuire.
Se il guanto sinistro scelto è di un colore differente da quello destro non distribuito allora, considerando la stringa dei colori dei guanti sinistri come una permutazione della stringa dei colori dei guanti destri non devo avere punti fissi.
Ho quindi $ D_6 $ possibilità.
Se il guanto sinistro scelto è dello stesso colore di quello destro non distribuito allora gli altri 5 guanti sinistri non devono essere dati alle stesse persone a cui è stato dato il destro dello stesso colore.
Ho $ D_5 $ possibilità.
La soluzione è quindi: $ 6!(D_6+D_5) $
Ricordo che $ D_n = n! \sum_{k=0}^{n}(-1)^k \frac{1}{k!} $.
Buona serata Simone.
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Questo lo propongo come esercizio per chi voglia capire come funzioni il PIE (principio di inclusione-esclusione)enomis_costa88 ha scritto: $ D_n = n! \sum_{k=0}^{n}(-1)^k \frac{1}{k!} $.
Ricordo che $ D_n $ è il numero delle permutazioni senza punti fissi (derangements) di una n-upla {1,..,n}.
Buon lavoro. Simone