Calcolo combinatorio

Principio fondamentale del calcolo combinatorio. Se una scelta può essere fatta in $\displaystyle r$  modi diversi, per ciascuno dei quali una seconda scelta può essere effettuata in $\displaystyle s$ modi diversi, e, per ciascuno dei modi in cui si sono compiute le prime due scelte una terza scelta può essere effettuata in $\displaystyle t$ modi diversi ecc., allora la successione di tutte le scelte può essere compiuta in $\displaystyle r\cdot s\cdot t\cdot …$  modi diversi.

Esempio,- Dieci persone possono mangiare spaghetti o minestrone  per primo, possono poi scegliere il secondo tra carne, pesce o frittata, bevendo poi acqua naturale, birra, vino o aranciata e  scegliendo come dolci tra babbà, sfogliatella o cannolo. Quante scelte diverse si possono fare?

Alcune scelte possibili:

prima persona, spaghetti, carne, birra, babbà;
prima persona, spaghetti, carne, birra, sfogliatella; …,


seconda persona, minestrone, pesce, vino, babbà; …

….

Raggruppamenti o gruppi di elementi. Dato un insieme I finito di n elementi ( o oggetti)  e non vuoto, \[I=\left \{ a_{1}, a_{2},a_{3},…,a_{n}\right \}\], possiamo creare dei raggruppamenti o gruppi di elementi di I prendendo a piacere k > 0 elementi di I. Ad esempio  un raggruppamento possibile di tre elementi di I è  \[\left \{ a_{1}, a_{2},a_{3}\right \}\] uno di un sol elemento di I è  $\displaystyle \left \{ a_{2} \right \}$ mentre uno di k elementi lo indicheremo con \[\left \{ a_{1}, a_{2},…,a_{k}\right \}\, \, \, o\, \, \, con\, \, \, \, a_{1}a_{2}…a_{k}\]
Un raggruppamento di k elementi si dice di “classe k “o anche “a k a k.” Se non vi sono termini ripetuti il raggruppamento si dice semplice.

Si possono costruire anche raggruppamenti con eventuali ripetizioni di elementi di I, un raggruppamento di classe 3 potrebbe essere \[\left \{ a_{1}, a_{2},a_{2}\right \}\, \, \, o\, \, \, con\, \, \, \, a_{1}a_{2}a_{2}\] oppure \[\left \{ a_{2}, a_{2},a_{1}\right \}\, \, \, o\, \, \, con\, \, \, \, a_{2}a_{2}a_{1}\]
Se vi sono termini ripetuti il raggruppamento si dice con ripetizioni.

Raggruppamenti notevoli sono i seguenti:

1. Disposizioni semplici.-

Si dicono disposizioni semplici di $\displaystyle n$ oggetti distinti tra loro di classe $\displaystyle k$, con $\displaystyle k\leq n$,  tutti i possibili raggruppamenti che si possono formare prendendo k degli n  oggetti  dati, in modo che due qualsiasi raggruppamenti differiscano o per qualche oggetto o per l’ordine con cui gli oggetti sono collocati nei raggruppamenti

\[D_{n,k}=n\cdot (n-1)\cdot (n-2)\cdot …\cdot \left ( n-k+1 \right )\]

si può usare anche la formula $\displaystyle D_{n,k}=\frac{n!}{\left ( n-k \right )!}$

In questo caso è $\displaystyle 0<k\leq n$ con k e n numeri naturali.

Esempio 1.1.- Determinare le disposizioni semplici  di classe 2 degli elementi dell’insieme { P, W, A, 3, C }.

Alcuni esempi di disposizioni semplici  di classe 2 sono:  PWWPPA, C3, 3C, AC, … ( trovale…Hihihi…! )

Calcoliamo il loro numero: $\displaystyle D_{5,2}=5\cdot 4=20$

Nel caso particolare k = n si ha $\displaystyle D_{n,n}=P_{n}=n!$, mentre nel caso particolare k = 1 si ha: $\displaystyle D_{n,1}=n$, $\displaystyle D_{1,1}=1$.

Esempio 1.2.-Determinare le disposizioni semplici  di classe 4 di 11 oggetti.

Notiamo che n = 11 e k = 4.Si ha: \[D_{11,4}=11\cdot 10\cdot 9\cdot \left ( 11-4+1 \right )=11\cdot 10\cdot 9\cdot8=7920\]

Il calcolo si poteva fare anche così: \[D_{11,4}=\frac{11!}{\left ( 11-4 \right )!}=\frac{11!}{7!}=\frac{11\cdot 10\cdot 9\cdot 8\cdot 7!}{7!}=11\cdot 10\cdot 9\cdot 8=7920\]

avendo semplificato al numeratore e al denominatore 7!.

Esempio 1.3.- Vedi un altro esercizio svolto sul mio canale Youtube

Esempio 1.4- Un ulteriore esercizio svolto sul mio canale Youtube

2. Disposizioni con ripetizioni.-

Si dicono disposizioni con ripetizioni di $\displaystyle n$ oggetti distinti di classe $\displaystyle k$,  tutti i possibili raggruppamenti che si possono formare prendendo k degli n  oggetti  dati, in modo che due qualsiasi raggruppamenti differiscano per qualche oggetto o per l’ordine con cui gli oggetti sono collocati nei raggruppamenti o per il numero di volte che si ripete qualche oggetto.

\[D’_{n,k}=n^{k}\]

In questo caso può essere $\displaystyle n\geq k,\, o\, \, \, n<k$

Esempio 2.1.- Determinare le disposizioni con ripetizioni  di classe 3 degli elementi dell’insieme { W,  A}.

Notiamo che n = 2 e k = 3.
Alcune disposizioni con ripetizioni sono: WWW, WWA, WAW, WAA, AAA, AAW,…. ( trovale…Hihihi…! )

Esse sono: $\displaystyle D’_{2,3}=2^{3}=8$

Esempio 2.2.- Determinare  il numero delle colonne del  Totocalcio (Concorso settimanale italiano di pronostici sulle partite di calcio).
Notiamo che in questo caso n = 3, i simboli del totocalcio sono 1, 2, X per indicare rispettivamente la vittoria della squadra di casa, la vittoria della squadra ospite , il pareggio; mentre k = 13 essendo 13 il numero di incontri giocati (partite giocate) ogni domenica.
Dunque si ha: \[D’_{3,13}=3^{13}=1594323\]

Schedina del Totocalcio

Esempio 2.3.- Determinare  il numero delle colonne del  Totocalcio che si devono giocare se il numero degli incontri  disputati è 3.

Si tratta di disposizioni con ripetizioni di n = 3 oggetti {1, X, 2}. Si ha:
\[D’_{3,3}=3^{3}=27\]

Le disposizioni con ripetizioni (le colonne) in questo caso sono:

$\displaystyle \begin{matrix} 1 &2 &1 &2 &x &2 &2 &x &x \\ x &2 &1 &2 &x &x &1 &1 &2 \\ 2 &x &1 &2 &x &1 &x &2 &1 \end{matrix}$

\[\begin{matrix} 1 &1 &2 &2 &x &x \\ x &2 &x &1 &1 &2 \\ x &2 &x &1 &1 &2 \end{matrix}\]

\[\begin{matrix} 1 &1 &2 &2 &x &x \\ 1 &1 &1 &x &1 &2 \\ x &2 &x &1 &2 &1 \end{matrix}\]

\[\begin{matrix} 1 &1 &2 &2 &x &x \\ x &2 &x &1 &1 &2 \\ 1 &1 &1 &x &2 &1 \end{matrix}\]

3. Permutazioni semplici.-

Si dicono permutazioni semplici di $\displaystyle n$ oggetti distinti tutti i possibili raggruppamenti che si possono formare prendendo n degli n  oggetti  dati, in modo che due qualsiasi raggruppamenti differiscano solo per l’ordine con cui gli oggetti sono collocati nei due raggruppamenti.

\[P_{n}=n!\]

Esempio 3.1.- Determinare le permutazioni semplici delle lettere della parola ” CIGNO

Alcune permutazioni  delle lettere della parola “CIGNO ” sono:

 CGNOI, CIGONIOGCN, GONIC,….( trovale…Hihihi…! )

Dato che la parola è costituita da cinque lettere diverse si ha che il numero delle permutazioni semplici delle lettere di tale parola è: \[p_{5}=5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120\]

4. Permutazioni con ripetizioni.-

Si dicono permutazioni con ripetizioni di $\displaystyle n$ oggetti non tutti distinti, di cui alcuni uguali tra loro, tutti i raggruppamenti  che si possono formare con gli n oggetti in modo che ogni raggruppamento differisca da un altro soltanto per l’ordine con cui sono collocati gli oggetti nei raggruppamenti. Se tra gli n oggetti ve ne sono s uguali tra loro, altri r uguali tra loro, altri t uguali tra loro,… si ha:

\[P^{‘}_{n}=\frac{n!}{s!\cdot r!\cdot t!\cdot …}\]

Tale formula si può scrivere anche così.

\[P_{n}^{s,r,t,…}=\frac{P_{n}}{P_{s}\cdot P_{r}\cdot P_{t}}=\frac{n!}{s!\cdot r!\cdot t!…}\]

Esempio 4.1.- Determinare le permutazioni con ripetizioni della parola “MATEMATICA”.

Notiamo che n = 10 sono gli elementi (lettere) della parola “Matematica”; mentre s = 3 per la lettera A (perchè si ripete tre volte), r = 2 per la lettera M (si ripete due volte), t = 2 per la lettera T (si ripete due volte) e le altre lettere si presentano una sola volta. Quindi si ha:

\[P^{‘}_{10}=\frac{10!}{3!\cdot 2!\cdot 2!\cdot 1!}=151200\]

Esempio 4.2.- Determinare le permutazioni con ripetizioni degli elementi  { A, A, A, B, B, C }.

Si ha che n = 6,  s = 3 perchè la A si ripete 3 volte, r = 2 perchè B si ripete 2 volte e t = 1 perché la C figura una sola volta.
Dunque le permutazioni con ripetizioni sono:

\[P_{6}^{3,2,1,…}=\frac{P_{6}}{P_{3}\cdot P_{2}\cdot P_{1}}=\frac{6!}{3!\cdot 2!\cdot 1!}=\frac{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{3\cdot 2\cdot 1\cdot 2\cdot 1\cdot 1}=60\]

Notiamo che permutazioni di 6 elmenti distinti sono  \[P_{6}=6!=720\]

Esempio 4.3.- In un incontro di calcio la squadra di casa vince 5 a 1. In quanti modi diversi possono essersi succeduti i gol?

5. PERMUTAZIONI CICLICHE.-

\[P_{n}^{cicliche}=\frac{n!}{n}=(n-1)!\]

Esempio 5.1.- Determinare le permutazioni  cicliche dei 3 elementi  dell’insieme  P, W, A }.

Si ha: \[P_{3}^{cicliche}=\frac{3!}{3}=2!=2\]
In effetti se si ricercano le permutazioni cicliche possiamo disporre i tre elementi dell’insieme su di una circonferenza e osservare che solo due non si possono trasformare l’una nell’altra con rotazioni. In pratica ci sono 6 permutazioni semplici ma tre sono di un tipo e tre di un altro. Quello dello stesso tipo si possono trasformare l’una nell’altra mediante rotazione (in figura le due permutazioni che non si possono trasformare l’una nell’altra per rotazioni).

Tutte le permutazioni semplici dei tre elementi dell’insieme invence sono:

PAW, PWA, APW, AWP, WAP, WPA

ma solo due sono quelle cicliche PAW, PWA, perchè le altre si trasformano in una delle due per rotazioni. Precisamente sono le stesse permutazioni cicliche:

PAW    e    AWP,  WPA

PWA    e     WAP, APW.

E’ chiaro che ognuna delle tre suddette si può assumere come quella ciclica.

6. Combinazioni semplici.-

Si dicono combinazioni semplici di $\displaystyle n$ oggetti distinti tra loro di classe $\displaystyle k$, con $\displaystyle k\leq n$,  tutti i possibili raggruppamenti che si possono formare prendendo k degli n  oggetti  dati, in modo che due qualsiasi raggruppamenti differiscano o per almeno un oggetto.

\[C_{n,k}=\frac{n!}{k!\left ( n-k \right )!}\]

Utilizzando il coefficiente binomiale la formula precedente si può scrivere anche così:

\[C_{n,k}=\binom{n}{k}=\frac{n!}{k!\left ( n-k \right )!}\]

In questo caso è $\displaystyle 0<k\leq n$.

Ricordiamo che: $\displaystyle C_{n,k}=\frac{D_{n,k}}{P_{k}}$

Esempio 6.1.- Determinare le combinazioni semplici  di classe 2 degli elementi dell’insieme { P, W, A, 3, C }.

Alcuni esempi di combinazioni semplici di classe 2 sono:  PWPA, 3C, ACPC, … ( trovale…Hihihi…! )

Il numero delle combinazioni semplici dei 5 elementi dell’insieme dato prese 2 a 2, cioè di classe 2, è: \[C_{5,2}=\frac{5!}{2!\cdot \left ( 5-2 \right )!}=\frac{5!}{2!\cdot 3!}=\frac{5\cdot 4}{2}=10\]

Esempio 5.2.- Un ulteriore esercizio svolto sul mio canale Youtube

7. Combinazioni con ripetizioni.-

Si dicono combinazioni con ripetizioni di n oggetti distinti tra loro di classe k, tutti i possibili raggruppamenti che si possono formare con gli n oggetti, prendendone k per volta, con la condizione che ciascuno di essi di essi differisca da un altro per almeno un oggetto oppure per il numero di volte con cui uno stesso oggetto può essere ripetuto.

\[C_{n,k}^{‘}=\frac{(n+k-1)!}{k!}\]

In questo caso può essere $\displaystyle n\geq k,\, o\, \, \, n<k$

Esempio 7.1.- Determinare le combinazioni con  ripetizioni di classe 2 degli elementi dell’insieme { P, W, A }.

Notiamo che k = 2 e n = 3. Le combinazioni con ripetizioni sono: PP,  PW, PA,  WW, WA, AA.
Si possono calcolare con la formula: $\displaystyle C’_{3,2}=\frac{\left ( 3+2-1 \right )!}{2!\left ( 3-1 \right )!}=\frac{4!}{2!\cdot 2!}=6$

Esempio 7.2.- Determinare le combinazioni con  ripetizioni di classe 5 degli elementi dell’insieme { P, W, A,  C }.

Notiamo che n = 4 e k = 5.Si ha: \[C_{4,5}^{‘}=\frac{(4+5-1)!}{5!\cdot \left ( 4-1 \right )!}=\frac{8!}{5!\cdot 3!}=\frac{8\cdot 7\cdot 6\cdot 5!}{5!\cdot 3!}=56\]

 

ALTRI ESERCIZI SVOLTI O VIDEO

COEFFICIENTE BINOMIALE