Probabilità/Calcolo combinatorio: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 159:
== Partizioni ==
astrattemente, una combinazione è equivalente alla spartizione di un set in due sottoinsiemi, uno contenente K elementi e l ' altro contenente n-K elementi rimanenti. In generale, il gruppo S ={1, 2, ...,} può essere spartito in sottoinsiemi r. Lasciate n1, n2, ..., nr essere interi non negativi tali
che Pr
p=1 np = n.
Si consideri il seguente algoritmo iterativo che conduce ad una partizione di S. Per primo, noi selezioniamo un sottoinsieme di elementi n1 da S. Avendo scelto il primo sottoinsieme, selezioniamo un secondo sottoinsieme contenente n2 elementi degli elementi restanti n-n1.
Noi continiuamo questa procedura successivamente scegliamo sottoinsiemi di elementi np dal rimanente n-n1 -...-np-1 elementi, fino a quando non rimane un elemento.Questo algoritmo produce una spartizione di S in sottoinsiemi r, con il p-esimo
sottoinsieme contenente esattamente elementi np.Noi vogliamo contare il numero di tali spartizioni. Sappiamo che ci sono n!
n1!(n-n1)! modi per formare il primo sottoinsieme.
We continue this procedure by
successively choosing subsets of np elements from the remaining n−n1 −···−np−1 elements,
until no element remains. This algorithm yields a partition of S into r subsets, with the p-th
subset containing exactly np elements.
We wish to count the number of such partitions. We know that there are n!
n1!(n−n1)! ways to
form the first subset. Examining our algorithm, we see that there are
(n−n1−···−np−1)!
np!(n−n1−···−np)!
ways to form the p-th subset. Using the counting principle, the total number of partitions is
then given by
n!
n1!n2!···nr!
.
This expression is called a multinomial coefficient.
Example: A die is rolled nine times. We wish to compute the number of outcomes for
which every odd number appears three times. The number of distinct sequences in which
one, three, and five each appear three times is equal to the number of partitions of {1, 2, ...
, 9} into three subsets of size three, namely
9!
3!3!3! = 1680.
In the above analysis, we assume that the size of each subset is fixed, three subsets of size
three. Suppose instead that we are interested in counting the number of ways of picking the
sizes of the subsets, r subsets of n1,n2,...,nr size, where the sum of the sizes is a constant.
Specifically, we wish to compute the number of ways integers n1,n2,...,nr can be selected
such that every integer is nonnegative and
Pr
p=1 np = n.
We can visualize the number of possible assignments as follows. Picture n balls spaced out
on a straight line and consider r-1 vertical markers, each of which can be put between two
consecutive balls, before the first ball, or after the last ball. For instance, if there are five
balls and two markers then one possible assignement is illustrated below.
== Probabilità di calcolo ==
| |||