Calcolo combinatorio e combinazioni

[ale.tzunny]

durante una gara matematica bisogna svolgere 4 problemi. una squadra è formata da sei membri. a ogni membro è affidato uno e un solo problema da svolgere. se ognuno dei quattro problemi è svolto da almeno un concorrente, in quanti modi diversi può esser fatto l'assegnamento dei membri della squadra ai problemi?

[glo_camp]

Ciao!
Ho provato a risolvere il problema con un metodo "logico", spero sia giusto.

Indico con A, B, C, D i 4 problemi da risolvere.
Devo formare raggruppamenti da 6 elementi (= 6 membri compongono la squadra) in cui ogni elemento compaia almeno una volta.
A B C D A A
A B C D A B
A B C D A C
A B C D A D

A B C D B B
A B C D B A
A B C D B C
A B C D B D

A B C D C C
A B C D C A
A B C D C B
A B C D C D

A B C D D D
A B C D D A
A B C D D B
A B C D D C
= 16 raggruppamenti partendo con A B C D

Ripeto lo stesso procedimento (idelamente) partendo con:
(A B C D)
A B D C
A C B D
A C D B
A D C B
A D B C

16 * 6 = 96 raggruppamenti partendo con la lettera A

Ripeto lo stesso procedimento partendo con le altre lettere (B, C, D).

Totale raggruppamenti = 96 * 4 = 384

[ale.tzunny]

Il libro da 1560

[glo_camp]

Ho trovato lo stesso problema in inglese su internet, ti riporto la soluzione:

We must divide 6 distinguishable objects (the team members) into 4 distinguishable
classes (the problems) with no class empty. With 3 objects in one class and 1 object in
each of the other three classes, we get C(6, 3) ∙ 3 ∙ 2 ∙ 1 = 120 assignments. There are 4
ways to divide the 4 classes into one of size 3 and 3 of size 1. With 2 objects in each of 2
classes and 1 object in each of the other 2 classes, we get C(6, 2) ∙ C(4, 3) ∙ 2 ∙ 1 = 180
assignments. There are 6 ways to divide the 4 classes into 2 of size 2 and 2 of size 1.
Thus, the total number of arrangements is 4 ∙ 120 + 6 ∙ 180 = 1560.

Fonte: http://www.mymathcounts.com/documents/PChapter26Countingd.pdf

Aggiunto 42 minuti più tardi:

# glo_camp :
Ho trovato lo stesso problema in inglese su internet, ti riporto la soluzione:

We must divide 6 distinguishable objects (the team members) into 4 distinguishable
classes (the problems) with no class empty. With 3 objects in one class and 1 object in
each of the other three classes, we get C(6, 3) ∙ 3 ∙ 2 ∙ 1 = 120 assignments. There are 4
ways to divide the 4 classes into one of size 3 and 3 of size 1. With 2 objects in each of 2
classes and 1 object in each of the other 2 classes, we get C(6, 2) ∙ C(4, 3) ∙ 2 ∙ 1 = 180
assignments. There are 6 ways to divide the 4 classes into 2 of size 2 and 2 of size 1.
Thus, the total number of arrangements is 4 ∙ 120 + 6 ∙ 180 = 1560.

Fonte: http://www.mymathcounts.com/documents/PChapter26Countingd.pdf

Quindi praticamente il ragionamento è il seguente:
Ogni problema (A, B, C, D) può essere ripetuto da 1 a 3 volte all'interno di un gruppo.
Si possono formare 4 gruppi del tipo "1 lettera ripetuta 3 volte e le altre 1 volta sola":
(1) AAA B C D = 3A 1B 1C 1D
(2) BBB A C D = 3B 1A 1C 1D
(3) CCC A B D = 3C 1A 1B 1D
(4) DDD A B C = 3D 1A 1B 1D
e ognuno di questi 4 raggruppamenti si può presentare in modo diverso per l'ordine degli elementi che lo compongono --> Permutazioni con ripetizioni di n oggetti (n=6) di cui k uguali fra loro (k = 3) con k≤n (infatti 3≤6):

P(n,k) = n!/k! = 6!/3! = 6 * 5 * 4 * 3!/3! = 6 * 5 * 4 = 120

Si possono però formare anche 6 raggruppamenti del tipo "2 lettere ripetute 2 volte e le altre lettere ripetute 1 volta sola":
(1) AA BB C D = 2A 2B 1C 1D
(2) AA CC B D = 2A 2C 1B 1D
(3) AA DD B C = 2A 2D 1B 1C
(4) BB CC A D = 2B 2C 1A 1D
(5) BB DD A C = 2B 2D 1A 1C
(6) CC DD A B = 2C 2D 1A 1B

e come prima, ciascuno di questi 6 raggruppamenti può essere diverso per l'ordine in cui compaiono gli elementi --> --> Permutazioni con ripetizioni di n oggetti (n=6) di cui k e h uguali fra loro (k = 2; h = 2):

P(n,k,h) = n!/k!h! = 6!/2!2! = 6 * 5 * 4 * 3 * 2/2 * 2 = 6 * 5 * 3 * 2 = 180

Perciò il numero totale di raggruppamenti possibili è = 120 * 4 + 180 + 6 = 1560