CALCOLO COMBINATORIO: DISPOSIZIONI














n = numero dei distinti oggetti considerati (n  1);
k = numero degli oggetti scelti dagli n;
Scegliere k oggetti significa costituire un gruppo di k oggetti scelti e il gruppo di
(n-k) oggetti complementari
D(n,k) = numero delle possibili disposizioni (semplici);
Dr(n,k) = numero delle possibili disposizioni con ripetizioni;
P(n) = numero delle possibili permutazioni di n oggetti;
C(n,k) = numero delle possibili combinazioni;
Cr(n,k) = numero delle possibili combinazioni con ripetizioni.
Disposizioni
Criterio di distinzione tra due scelte (o gruppi) di k oggetti:
Un gruppo (scelta) di k oggetti si distingue da un altro sempre di k oggetti se è
diverso o per almeno un oggetto, oppure per l’ordine nel quale gli oggetti sono
riportati.
Si hanno:
Dr(n,k) = nk,
(k  1);
D(n,k) = n(n-1)(n-2)···(n-k+1),
(1  k  n).
PERMUTAZIONI

n = numero dei distinti oggetti considerati (n  1);

P(n) = numero delle scelte possibili permutazioni.




Criterio di distinzione tra due scelte (o gruppi) costituite dai medesimi n oggetti:
Un gruppo (scelta) si distingue da un altro sempre costituito dai medesimi n se è
diverso l’ordine nel quale gli oggetti sono riportati.
Si ha:






P(n) = n(n-1)(n-2)···3·2·1
Scriveremo:
n! := n(n-1)(n-2)···3·2·1
Si ha:
P(n) = D(n,n).
(n  1).
(n  1).
PERMUTAZIONI

Anagrammare R O M A

Permutazioni di n oggetti di cui k uguali tra loro e i rimanenti (n-k) differenti dai
primi ma anch’essi uguali tra loro (1  k  n).
Se si indica con P(n: k, (n-k)) il numero delle permutazioni ricercato, realizzando
per ciascuna delle permutazioni suddette le permutazioni dei primi k oggetti in
ipotesi che sia possibile distinguerli e successivamente realizzando per ciascuna
delle permutazioni così ottenute le permutazioni dei secondi k oggetti in ipotesi
che sia possibile distinguerli, si otterranno le permutazioni di n oggetti tutti tra
loro distinguibili.
Si ha dunque:
P(n: k, (n-k))•P(k)•P(n-k) = P(n);
segue quindi:
P(n: k, (n-k)) = P(n)/[P(k)•P(n-k)] = n! / [k!(n-k)!].








Si conviene:
0! = 1.
COMBINAZIONI



n = numero dei distinti oggetti considerati (n  1);
k = numero degli oggetti scelti dagli n;
Scegliere k oggetti significa costituire un gruppo di k oggetti scelti e il gruppo di
(n-k) oggetti complementari

C(n,k) = numero delle scelte possibili combinazioni.

Criterio di distinzione tra due scelte (o gruppi) costituite da k oggetti:
Un gruppo (scelta) di k oggetti si distingue da un altro sempre costituito da k
oggetti se è diverso per almeno un oggetto. L’ordine nel quale gli oggetti sono
riportati è irrilevante.
Dalla relazione:
C(n,k)·P(k) = D(n,k)
Segue: C(n,k) = D(n,k)/P(k) = n(n-1)(n-2)···(n-k+1)/k! (1  k n).
Scriveremo:
n
(1  k n).

k 
:= n(n-1)(n-2)···(n-k+1)/k!
 
Segue:
n

 
 = n!/[k!(n-k)!]








k 
COMBINAZIONI

Contare i modi con cui si possono scegliere x=3 caselle da n=9.
1
2
3
4
5
6
7
8
9





Contare i modi con cui si possono ottenere x teste in n lanci di una monete.
Contare i modi con cui si possono ottenere x “sei” in n lanci di un dado da gioco.
Contare i modi con cui si possono scegliere x numeri da novanta (dal numero 1
al numero 90).
Dati gli oggetti {1,2,3,4} costruire le 12 disposizioni in classe 2.
Dati gli oggetti {1,2,3,4} costruire le 6 combinazioni in classe 2.
COMBINAZIONI: PROPRIETÀ





Valgono le seguenti proprietà:
n

k 
=
 
Regola di Stiefel (vedi triangolo di Pascal):
 n  1  n  1  n 

 k  1
 +  k  = 
k 


 
  
Sviluppo del binomio di Newton:




n


 ;
n  k 
 n  i n i
 a b ;

i 0  i 
n
(a+b)n
=
Specificazione per a=b=1:
n
   2 n .

i 0  i 
n
COMBINAZIONI CON RIPETIZIONI



n = numero dei distinti oggetti considerati (n  1);
k = numero degli oggetti scelti dagli n;
Scegliere k oggetti significa costituire un gruppo di k oggetti scelti e il gruppo di
(n-k) oggetti complementari

Cr(n,k) = numero delle scelte possibili combinazioni con ripetizioni.

Criterio di distinzione tra due scelte (o gruppi) costituite da k oggetti:
Un gruppo (scelta) di k oggetti si distingue da un altro sempre costituito da k
oggetti se è diverso per almeno un oggetto, potendo un oggetto essere presente
più volte (massimo k volte). L’ordine nel quale gli oggetti sono riportati è
irrilevante.
Risulta:
 n  k  1

Cr(n,k) = 



k

COMBINAZIONI CON RIPETIZIONI
 n  k  1

k

Cr(n,k) = 

Risulta:

Non dipendendo il numero delle combinazioni dalla natura specifica degli
oggetti si assuma che gli n oggetti a disposizione siano costituiti dai primi n
numeri interi naturali: S = {1, 2, …, n}.
Una k-upla di numeri scelti da S viene indicata con (x1,x2,…,xk).
Non essendo rilevante l’ordine per le combinazioni possiamo pensare i k numeri
scelti ordinati in modo non decrescente:
x1  x2  …  xk
Come si vede si può realizzare anche l’uguaglianza tra i numeri avendo stabilito
che sono possibili le ripetizioni.
Consideriamo ora la k-upla di numeri (y1,y2,…,yk) definiti come segue:
(1)
y1 = x1 + 0; y2 = x2 + 1; y3 = x3 + 2; …; yk = xk + k - 1.
Tali nuovi numeri saranno tutti distinti:
y1  y2  …  yk;
inoltre si avrà:
yi : 1  yi  n+k-1, i=1,2 …,k.
Mediante la (1) a una k-combinazione con ripetizione estratta da S corrisponde
biunivocamente una k-combinazione semplice estratta dall’insieme:
A= {1, 2, …, n+k-1}
Segue quindi:
 n  k  1


Cr(n,k) = C (n+k-1,k) =  k














