Archivio Categoria: Calcolo combinatorio

Formulario di calcolo combinatorio


FORMULARIO DI CALCOLO COMBINATORIO

Fattoriale di n o n-fattoriale ({n!}) {n!}=1\cdot 2\cdot 3\cdot 4 \cdot \dots \cdot n

{0!}=1

{1!}=1

{(n+1)!}=(n+1){n!}

Permutazioni semplici di n oggetti (si tiene conto dell'ordine) \displaystyle P_n={n!}
Permutazioni con ripetizione di n oggetti di tipo k_1, k_2, \cdots, k_m (si tiene conto dell'ordine e gli elementi si possono ripetere), con n=k_1 + k_2 + \cdots + k_m \displaystyle P^r_{n, k_1, k_2, \cdots, k_m}=\frac{n!}{k_1!\cdot k_2!\cdot \dots \cdot k_m!}
Disposizioni semplici di n oggetti presi k a k (si tiene conto dell'ordine), con 0\leq k \leq n \displaystyle D_{n,k}=\frac{n!}{(n-k)!}
Disposizioni con ripetizione di n oggetti presi k a k (si tiene conto dell'ordine e gli elementi si possono ripetere) \displaystyle D^r_{n,k}=n^k
Combinazioni semplici di n oggetti presi k a k  (non si tiene conto dell'ordine), con 0\leq k \leq n  \displaystyle C_{n,k}=\frac{n!}{k!(n-k)!}
Combinazioni con ripetizione di n oggetti presi k a k (non si tiene conto dell'ordine e gli elementi si possono ripetere) \displaystyle C^r_{n,k}=C_{n+k-1, k}=\frac{(n+k-1)!}{k!(n-1)!}

Esercizi di calcolo combinatorio: permutazioni con ripetizione


ESERCIZIO

Quanti sono gli anagrammi della parola "massa"?

SOLUZIONE

Si tratta di una permutazione con ripetizione (le lettere della parola "massa" non sono tutte diverse).

La formula per calcolare quante sono le permutazioni di n elementi di cui k_1, k_2, \dots, k_m uguali è:

\displaystyle P^r_{n, k_1, k_2, \cdots, k_m}=\frac{n!}{k_1!\cdot k_2!\cdot \dots \cdot k_m!}

dove k_1+ k_2+\dots + k_m=n.

In questo caso la parola è formata da cinque lettere di cui due "s", due "a" e una "m" (n=5, k_1=2, k_2=2, k_3=1)

\displaystyle P^r_{5, 2, 2, 1}=\frac{5!}{2!\cdot 2!\cdot 1!}=\frac{5\cdot 4\cdot 3\cdot 2}{2\cdot 2}=30.

Esercizi di calcolo combinatorio: combinazioni con ripetizione


ESERCIZIO

Dato l'insieme A=\lbrace a, b\rbrace, quante combinazioni da tre elementi si possono formare?

SOLUZIONE

Si tratta di una combinazione con ripetizione (le lettere si possono ripetere): \displaystyle C^r_{n,k}=C_{n+k-1, k}=\frac{(n+k-1)!}{k!(n-1)!}.

In questo caso per n=2 e k=3\displaystyle C^r_{2,3}=\frac{4!}{3!1!}=\frac{4\cdot 3\cdot 2\cdot 1}{3\cdot 2 \cdot 1}=4.

Le combinazioni sono quattro: aaa, bbb, aab, bba.

Esercizi di calcolo combinatorio: permutazioni semplici

ESERCIZIO

In quanti modi Luca, Simona, Gioia e Perla possono sedersi su quattro sedie?

SOLUZIONE

Si tratta di una disposizione semplice di n elementi in  n modi diversi, cioè una permutazione semplice.

La formula per calcolare quante sono le permutazioni semplici di n elementi è:
\displaystyle P_n=D_{n,n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}={n!}.

Per n=4, \displaystyle P_4={4!}=4\cdot 3\cdot 2\cdot 1=24.

ESERCIZIO

Quanti sono gli anagrammi della parola "carte"?

SOLUZIONE

Si tratta di una permutazione semplice (le lettere della parola "carte"sono tutte diverse).

Per n=5,\displaystyle P_5={5!}=5\cdot 4\cdot 3\cdot 2\cdot 1=120.

Esercizi di calcolo combinatorio: disposizioni con ripetizione




ESERCIZIO
Quanti numeri di due cifre si possono formare con gli elementi dell'insieme A=\lbrace 2, 3, 4, 7, 8 \rbrace?

SOLUZIONE
Si tratta di una disposizione (si tiene conto dell'ordine) con ripetizione (le cifre si possono ripetere), cioè  22, 33, 44, 77, 88, 23, 32, 24, 42 ecc...

La formula per calcolare quante sono le disposizioni con ripetizione di n oggetti in k modi è: \displaystyle D^r_{n,k}=n^k.

Abbiamo 5 elementi (n=5) e numeri di 2 cifre  (k=2)

\displaystyle D^r_{5,2}=5^2=25.

Esercizi di calcolo combinatorio: disposizioni semplici





ESERCIZIO
Quanti numeri di due cifre distinte si possono formare con gli elementi dell'insieme A=\lbrace 2, 3, 4, 7, 8 \rbrace?

SOLUZIONE
Si tratta di una disposizione (si tiene conto dell'ordine) semplice (non ci sono ripetizioni), cioè 23, 32, 24, 42, 27, 72 ecc...

La formula per calcolare quante sono le disposizioni semplici di n oggetti in k modi è: \displaystyle D_{n,k}=\frac{n!}{(n-k)!}.

Abbiamo 5 elementi (n=5) e numeri di 2 cifre  (k=2)

\displaystyle D_{5,2}=\frac{5!}{(5-2)!}=\frac{5!}{3!}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{3 \cdot 2\cdot 1}=20.

Esercizi di calcolo combinatorio: combinazioni semplici





ESERCIZIO

Da una classe di 22 alunni si devono estrarre a sorte 3 alunni per la realizzazione di un progetto di matematica. Quante terne di alunni si possono avere?

SOLUZIONE

Si tratta di una combinazione (non si tiene conto dell'ordine ) semplice (non ci sono ripetizioni): \displaystyle C_{n,k}=\frac{n!}{k!(n-k)!}

\displaystyle C_{22,3}=\frac{22!}{3!(22-3)!}=\frac{22!}{3!(19)!}=\frac{22\cdot 21\cdot 20 }{3\cdot 2 \cdot 1}=\frac{462}{6}=77.