5.4 Esercizi 143
Esempio 5.55 Ad ognuno dei 12 cavalieri di una tavola rotonda viene dato un sac- chetto con un certo numero di monete d’oro, tra 1 e 12; tutti ricevono un numero diverso di monete d’oro. Supponiamo che i cavalieri siano numerati da 1 a 12 (pari al loro rango), e che solo 5 abbiano un sacchetto con un numero di monete uguale alme- no al loro rango. I cavalieri decidono di passare al proprio vicino in senso antiorario il proprio sacchetto. Allora vi sono esattamente 4 cavalieri il cui gruzzolo di monete supera il loro rango. Infatti se il cavaliereiriceve in un primo momento un sacchet- to con (i) monete d’oro, allora dopo il passaggio al vicino il cavaliereiriceve un sacchetto con⇥( )(i)monete d’oro.
Esempio 5.56 (Il problema dei diplomi dello Smith College) [10] Allo Smith Col- lege la consegna dei diplomi avviene come segue. I diplomi vengono distribuiti a caso ai laureandi. Quelli che non hanno il loro diploma si riuniscono in cerchio e li pas- sano al vicino in senso antiorario: chi ottiene il proprio diploma se ne va, mentre gli altri formano un cerchio pi`u piccolo. Quante sono le possibili distribuzioni iniziali dei diplomi tali che siano necessarik 0passaggi di mano prima che ogni studente abbia il proprio diploma?
Soluzione. Numeriamo da 1 angli studenti. Supponiamo che allo studenteisia stato assegnato il diploma dello studente (i), dove = ( (1), ..., (n))`e una permu- tazione di(1, ..., n). Mettendo da parte gli studenti che hanno il proprio diploma (ovvero gliiper i quali (i) = i), possiamo considerare la permutazione 0ottenuta restringendo agli studenti rimasti (ovvero gliiper i quali (i) 6= i). Lo studente rimasto con il numero pi`u basso `e di sicuro una eccedenza stretta per 0(e per ). Sia kil numero di eccedenze strette di 0(peraltro uguale al numero di eccedenze strette di ). Il passaggio di mano corrisponde a passare da 0a⇥( 0)come visto nel Lem- ma 5.54. Ora, per il lemma citato, il numero di eccedenze strette di⇥( 0) `e uguale a k 1: sek = 1, allora⇥( 0)(i) iper ogniie tutti hanno il loro diploma, altrimenti vi sonok 1 1eccedenze strette nel gruppo degli studenti rimasti. Proseguendo, dopo esattamentekpassaggi di mano tutti hanno il loro diploma. Pertanto, il numero di passaggi necessario per diplomarenstudenti `e pari al numero di eccedenze strette nella distribuzione iniziale, o equivalentemente, pari al numero di coppie ascendenti nella distribuzione iniziale. Dunque le possibili distribuzioni iniziali dei diplomi per le quali sono necessarik 0passaggi di mano `e uguale al numero di permutazioni conkcoppie ascendenti, ovvero al numero di Eulero
*n k
+ .
5.4 Esercizi
Esercizio 5.1 In quanti modi si possono distribuire23oggetti distinti in8contenitori identici, in modo che nessun contenitore risulti vuoto?
5.4 Esercizi 145 Soluzione es. 5.2. Le 6-partizioni diI30 con collezione di occupancy[3, 4, 5, 6, 6, 6]
sono
⇧(6, 30) = 1
6!⇥ S(6, 30; 3, 4, 5, 6, 6, 6) ⇥ P (3, 4, 5, 6, 6, 6) ovvero
1
6!⇥ 30!
3!4!5!(6!)3 ⇥6!
3!.
Soluzione es. 5.3. Si tratta di contare le 5-partizioni di I14 con occupancy [2, 2, 2, 4, 4]:
⇧(5, 14; [2, 2, 2, 4, 4]) = 1
5!S(5, 14; [2, 2, 2, 4, 4]) = 1 5!
14!
2!3⇥ 4!2P (2, 2, 2, 4, 4) =
= 1 5!
14!
2!3⇥ 4!2 5!
3!⇥ 2! = 1 576 575
Soluzione es. 5.4. (a): si tratta del numero di 4-partizioni di I52 con occupancy [13, 13, 13, 13]: in tutto ve ne sono⇧(4, 52; [13, 13, 13, 13]) = 1
4!
52!
(13!)4.(b): si tratta del numero di 7-partizioni diI52con occupancy[7, 7, 7, 8, 8, 8, 8]: in tutto ve ne sono⇧(7, 52; [7, 7, 7, 8, 8, 8, 8]) = 1
7!
52!
(7!)3(8!)4 7!
3!4!.
Soluzione es. 5.5. L’esito della suddivisione individua univocamente una 5-partizione dei 18 studenti con collezione di occupancy[4, 4, 4, 3, 3], il gruppo di 3 studenti dov’`e stato messo il primo docente, il gruppo di 3 studenti dov’e’ stato inserito il secondo docente. Quindi due tappe: a) 5-partizione degli studenti con collezione di occupancy [4, 4, 4, 3, 3]b) sistemazione dei docenti nei gruppi di 3 persone: 2 modi. In tutto
2⇥ ⇧(5, 18; [4, 4, 4, 3, 3]) = 2 ⇥ 1
5! ⇥ 18!
4!3⇥ 3!2 ⇥ P (4, 4, 4, 3, 3) =
= 2⇥ 1
5!⇥ 18!
4!3⇥ 3!2 ⇥ 5!
3!⇥ 2!
Soluzione es. 5.6. Si tratta di contare le 5-partizioni di I20 con collezione di occupancy[5, 5, 3, 3, 4]. Queste sono
⇧(5, 20; [5, 5, 3, 3, 4]) = 1 5!
20!
5!5!3!3!4!P (5, 5, 3, 3, 4) = 1 5!
20!
5!5!3!3!4!
5!
2!2!1! = 20!
(5!3!2!)24!
Soluzione es. 5.7. Si tratta di contare quanti sono i 30-cicli diI100; questi sono
⇥(100, 30) = 1
30S(100, 30) = 100!
30⇥ 70! =
= 259 703 237 901 926 829 152 907 749 975 910 714 678 610 923 356 160 000 000
146 Partizioni, cicli e partizioni in cicli
Soluzione es. 5.8. Il numero delle possibili disposizioni dei 20 invitati sono uguali al numero di 20-cicli diI20, ovvero a19!Carlo, Alberto, Paola ed Elena possono essere sistemati in senso antiorario in 4! modi. Scelta una sistemazione dei 4, la pensiamo come un unico blocco e contiamo il numero delle possibili disposizioni intorno al tavolo tondo del blocco e degli altri 16 invitati: queste sono16!La probabilit`a cercata
`e dunque uguale a
4!⇥ 16!
19! = 4
969 ⇡ 0.004 = 0.4%
Soluzione es. 5.9. Dobbiamo decidere se vogliamo o no distinguere i tavoli tra loro.
Se i tavoli sono tutti uguali si tratta di contare le 8-partizioni in cicli diI40: queste sono
40
8 . Se invece i tavoli sono tutti distinti, allora, una volta ottenuta una 8-partizione in cicli, dobbiamo assegnare ad ogni ciclo un tavolo: questo pu`o essere fatto in 8!
modi. Pertanto se i tavoli sono distinti le possibili disposizioni risultano8!⇥
40 8 . Soluzione es. 5.10. Etichettati gli studenti con I100, effettuiamo una 4-partizione in
cicli diI100con occupancy[25, 25, 20, 30]; ogni ciclo rappresenta la disposizione in senso antiorario su una ruota. Dobbiamo poi assegnare ogni ciclo ad una opportuna ruota: ho una sola possibilit`a per il 30-ciclo ed il 20-ciclo, mentre ne ho due per i 25-cicli. Le possibili disposizioni degli studenti sulle ruote sono pertanto
2⇥ ⇧⇥(4, 100; [25, 25, 20, 30]) =
= 2⇥ [1
4!⇥ 100!
25⇥ 25 ⇥ 20 ⇥ 30 ⇥ P (25, 25, 20, 30)].
Le disposizioni con Niccol`o, Tommaso e Francesca nell’ordine seduti in posti con- secutivi in ordine antiorario si ottengono contando separatamente i casi in cui i tre ragazzi si sistemano nella prima ruota da 25 posti, nella seconda da 25 posti, in quella da 30 e in quella da 20. Se i 3 ragazzi si sistemano nella prima da 25 posti, dobbiamo completare i 22 posti rimanenti con una 22-sequenza diI97 pensando ai tre ragazzi come punto di partenza del ciclo, e poi sistemare i rimanenti 75 in una 3-partizione in cicli diI75con occupancy[25, 20, 30]. In tutto vi sono
S(97, 22)⇥ 1
3!⇥ 75!
25⇥ 20 ⇥ 30⇥ P (25, 20, 30)
differenti disposizioni. Analogamente se i tre ragazzi si sistemano nella seconda ruota da 25. Se invece i tre ragazzi si sistemano nella ruota da 20 o in quella da 30 si ottengono rispettivamente
2⇥ S(97, 17) ⇥ 1
3!⇥ 80!
25⇥ 25 ⇥ 30 ⇥ P (25, 25, 30)e 2⇥ S(97, 27) ⇥ 1
3!⇥ 70!
25⇥ 25 ⇥ 20⇥ P (25, 25, 20)
5.4 Esercizi 147
differenti disposizioni; il fattore 2 in ciascuna espressione tiene conto delle due scelte per collocare i due 25-cicli nelle due ruote da 25. La probabilit`a cercata `e
2⇥ [97!
75! ⇥ 1
3!⇥ 75!
25⇥ 20 ⇥ 30 ⇥ 3! +97!
80! ⇥ 1
3!⇥ 80!
25⇥ 25 ⇥ 30 ⇥3!
2 +97!
70! ⇥ 1
3!⇥ 70!
25⇥ 25 ⇥ 20 ⇥3!
2] 2⇥ 1
4!⇥ 100!
25⇥ 25 ⇥ 20 ⇥ 30 ⇥4!
2
=
⇡ 0.0001 = 0.01%
Soluzione es. 5.11. L’asserto `e vero pern = 1:
` + 0 1
!*1 0
+
= ` = `1.
Supponiamo l’asserto vero pern 1. Utilizzando la Proposizione 5.47, 2, si ha Xn
i=0
` + i n + 1
!*n + 1 i
+
=
= Xn
i=0
` + i n + 1
! (i + 1)
*n i +
+ Xn
i=0
` + i n + 1
!
(n + 1 i)
* n
i 1 +
=
n 1X
i=0
` + i n + 1
! (i + 1)
*n i +
+
n 1X
i=0
` + i + 1 n + 1
! (n i)
*n i
+
=
n 1X
i=0
*n i
+ "
` + i n + 1
!
(i + 1) + ` + i + 1 n + 1
! (n i)
#
=
n 1X
i=0
*n i
+ ✓` + i n
◆ (i + 1)(` + i n) + (n i)(` + i + 1) n + 1
=
n 1X
i=0
*n i
+ ✓` + i n
◆`(n + 1) n + 1
= `
n 1X
i=0
` + i n
!*n i
+
= ` `n= `n+1, dove l’ultima uguaglianza segue dall’ipotesi induttiva.
