Dimostrazione di alcune formule di calcolo combinatorio

[vinx91ct]

Ciao

Non riesco a trovare nel mio manuale di testo la dimostrazione (formale) che mi permetta di scrivere le disposizione in varie forme. Il manuale di testo che da cui sto studiando utilizza frasi del tipo "si verifica facilmente che" e dà per scontato che chiunque sappia verificare ciò che viene scritto.

Io non sono riuscito a verificarla e quindi chiedo aiuto. In particolare, qual è, se esiste, la dimostrazione formale che mi permette di passare dalle disposizioni semplici di n elementi di classe k scritta in questo modo


$D_{n,k}=n(n-1)(n-2)...(n-k+1)$

alla forma che usa il rapporto di due numeri fattoriali?

$D_{n,k}= \frac{n!}{(n-k)!}$

e poi da questa a quella che usa la nozione di coefficiente binomiale?

$D_{n,k}= \binom{n}{k}\cdot k!$

Stessa cosa dicasi per le permutazioni semplici di n elementi

$P_n= n!=n\cdot (n-1)!$ Perché quest'ultima identità è vera?


Grazie in anticipo.

[maurizio.schirinzi]

Ciao, sono daccordo con te! ... anche se sembra un paradosso, il 99% dei libri di testo sono pensati e scritti per chi la matematica già la conosce!!

Partiamo innanzi tutto dal fattoriale (definizione e proprietà fondamentale):
\[n! = n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot \;....\; \cdot 3 \cdot 2 \cdot 1\]
esempio:
\[5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\]
dalla definizione segue immediatamente che possibile disaccoppiare e staccare un qualsiasi numero di fattori mettendoli a prodotto con il fattoriale dei termini discendenti successivi:

esempi:
\[\begin{array}{l}
5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5 \cdot (4 \cdot 3 \cdot 2 \cdot 1) = 5 \cdot 4!\\
5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5 \cdot 4 \cdot (3 \cdot 2 \cdot 1) = 5 \cdot 4 \cdot 3!
\end{array}\]
ne segue pertanto in generale:
\[\begin{array}{l}
n! = n \cdot (n - 1)!\\
n! = n \cdot (n - 1) \cdot (n - 2)!\\
n! = n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3)!
\end{array}\]
Riguardo alla formula delle disposizioni semplici (senza ripetizione) di n elementi in classe k si ha, moltiplicando e dividendo per (n-k)!:
\[{D_{n,k}} = n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot \;....\; \cdot (n - k + 1) = \]
\[ = \frac{{n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot \;....\; \cdot (n - k + 1) \cdot (n - k)!}}{{(n - k)!}} = \]
\[ = \frac{{n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot \;....\; \cdot (n - k + 1) \cdot (n - k) \cdot (n - k - 1) \cdot (n - k - 2) \cdot \;...\; \cdot 3 \cdot 2 \cdot 1}}{{(n - k)!}} = \]
\[ = \frac{{n!}}{{(n - k)!}}\]
ricordando inoltre la definizione di coefficiente binomiale si ha:
\[\left( \begin{array}{l}
n\\
k
\end{array} \right) = \frac{{n!}}{{(n - k)!\;k!}}\]
quindi moltiplicando e dividendo la formula delle disposizioni per k! si ha:
\[{D_{n,k}} = \frac{{n!}}{{(n - k)!}} = \frac{{n!}}{{(n - k)!}}\frac{{k!}}{{k!}} = \frac{{n!}}{{(n - k)!\;k!}} \cdot k! = \left( \begin{array}{l}
n\\
k
\end{array} \right) \cdot k!\]

Saluti.

[vinx91ct]

Grazie!!!

O.k. Sempre per lo stesso motivo di prima, io dovrei dimostrare il risultato delle permutazioni con ripetizione e capire il perché del fatto che sia uguale alle combinazioni semplici di r1+r2 elementi di classe r1, cioé

\[P^{r}_{r1,r2}=\frac{(r_1+r_2)!}{r_1!\cdot r_2!}=\binom{r_1+r_2}{r_1}= C_{r_1+r_2,r_1}\]

E come ultimo, dovrei saper dimostrare che le combinazioni con ripetizione di n elementi presi k a k (o di classe k) sono uguali alle combinazioni di n+k-1 elementi di classe k, cioè

\[C^{r}_{n,k}=\frac{n\cdot(n+1)\cdot (n+2)\cdot.....\cdot(n+k-1)}{k!}=\binom{n+k-1}{k}= C_{n+k-1,k}\]

Io da solo non riuscirei a saper dimostrare un bel niente.

[maurizio.schirinzi]

Riguardo alla prima formula dalla definizione di coefficiente binomiale si ha:
\[\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right) = \frac{{n!}}{{(n - k)!\;k!}}\]
da cui:
\[{C_{{r_1} + {r_2},{r_1}}} = \left( {\begin{array}{*{20}{l}}
{{r_1} + {r_2}}\\
{\;\;\;{r_1}}
\end{array}} \right) = \frac{{({r_1} + {r_2})!}}{{({r_1} + {r_2} - {r_1})!\;\;{r_1}!}} = \frac{{({r_1} + {r_2})!}}{{({r_2})!\;\;{r_1}!}} = \frac{{({r_1} + {r_2})!}}{{{r_1}!\;\;{r_2}!}} = P_{r1,r2}^r\]

invece per la seconda formula si ha:
\[C_{n,k}^r = \frac{{n \cdot (n + 1) \cdot (n + 2)\cdot.....\cdot(n + k - 1)}}{{k!}} = \]
scrivendo il numeratore in ordine inverso
\[ = \frac{{(n + k - 1) \cdot \;...\; \cdot (n + 2) \cdot (n + 1) \cdot n}}{{k!}} = \]
moltiplicando e dividendo per (n-1)!
\[ = \frac{{(n + k - 1) \cdot \;...\; \cdot (n + 2) \cdot (n + 1) \cdot n \cdot (n - 1)!}}{{k!\;\;(n - 1)!}} = \]
dove ora il numeratore nei suoi termini discendenti è ora equivalente ad un unico fattoriale (per la solita proprietà di co-fattorizzazione del fattoriale)
\[ = \frac{{(n + k - 1)!}}{{k!\;\;(n - 1)!}} = \left( \begin{array}{c}
n + k - 1\\
k
\end{array} \right) = {C_{n + k - 1,k}}\]

Saluti.

[vinx91ct]

Grazie. Tutto molto più chiaro adesso.