Perchè $(n,k)$ è naturale.
Tengo un dubbio sui coefficienti binomiali. Questi, poiché indicano il numero delle combinazioni, devono essere naturali.
Di questa proprietà ho trovato la seguente spiegazione che non mi ha convinto:
La riporto testualmente citando MULTIFORMAT mod 12
La frazione espressa dalla formula $(n!)/(k!(n-k)!)$ è sempre equivalente a un numero naturale. Infatti:
1) Nella successione dei numeri naturali i multipli di un numero $k$ compaiono ogni $k$ numeri (per esempio i numeri pari sono ogni $2$ numeri, i multipli di $3$ ogni $3$ numeri e così via)
2) Il numeratore è il prodotto di $n$ numeri consecutivi (con $n>=k)$ quindi, uno di essi è sicuramente multiplo di k; vi sarà anche un multiplo di $k-1$, un multiplo di $k-2$ e così via
3) Ognuno di questi multipli divide uno dei fattori che compaiono al denominatore; la frazione così si semplifica può essere scritta con denominatore uguale a 1, cioè come un numero naturale.
Mi pregio di non aver capito nulla.
Soprattutto non ho capito il punto 2 dove sembra scomparire ogni riferimento a $n-k$ al denominatore.
Questo avrebbe un senso se si semplificasse la frazione trasformandola in
$((n),(k))= (n(n-1)(n-2)ldots(n-k+1))/(k!)
Ma non mi pare che questo sia l’intento dell’autore.
Inoltre, anche supponendo di partire dalla forma che ho indicato, non è chiaro perché si possa fare la semplificazione. Infatti ammettere che ogni fattore presente al denominatore abbia un multiplo al numeratore non consente di semplificare tutti i termini del denominatore: è possibile che più fattori del denominatore abbiano lo stesso multiplo.
Non vi chiedo una dimostrazione alternativa ma solo se questa via è praticabile.
Scusate se non ho espresso chiaramente il problema.
Grazie.
Di questa proprietà ho trovato la seguente spiegazione che non mi ha convinto:
La riporto testualmente citando MULTIFORMAT mod 12
La frazione espressa dalla formula $(n!)/(k!(n-k)!)$ è sempre equivalente a un numero naturale. Infatti:
1) Nella successione dei numeri naturali i multipli di un numero $k$ compaiono ogni $k$ numeri (per esempio i numeri pari sono ogni $2$ numeri, i multipli di $3$ ogni $3$ numeri e così via)
2) Il numeratore è il prodotto di $n$ numeri consecutivi (con $n>=k)$ quindi, uno di essi è sicuramente multiplo di k; vi sarà anche un multiplo di $k-1$, un multiplo di $k-2$ e così via
3) Ognuno di questi multipli divide uno dei fattori che compaiono al denominatore; la frazione così si semplifica può essere scritta con denominatore uguale a 1, cioè come un numero naturale.
Mi pregio di non aver capito nulla.
Soprattutto non ho capito il punto 2 dove sembra scomparire ogni riferimento a $n-k$ al denominatore.
Questo avrebbe un senso se si semplificasse la frazione trasformandola in
$((n),(k))= (n(n-1)(n-2)ldots(n-k+1))/(k!)
Ma non mi pare che questo sia l’intento dell’autore.
Inoltre, anche supponendo di partire dalla forma che ho indicato, non è chiaro perché si possa fare la semplificazione. Infatti ammettere che ogni fattore presente al denominatore abbia un multiplo al numeratore non consente di semplificare tutti i termini del denominatore: è possibile che più fattori del denominatore abbiano lo stesso multiplo.
Non vi chiedo una dimostrazione alternativa ma solo se questa via è praticabile.
Scusate se non ho espresso chiaramente il problema.
Grazie.
Risposte
il fatto,secondo me, è che $(n!) =n(n-1)(n-2)(n-3)....3*2*1$. Poichè $n>k$,tra questi fattori vi sarà anche $n-k$ e da quel punto in poi si semplificheranno tutti..
Si potrebbe provare per induzione che il numero della parti con $k$ di un insieme $S$ di $n$ elementi è $((n),(k))$.
Condivido le tue perplessità.
Non mi pare una dimostrazione.
Probabilmente muovendosi con quelle considerazione, si può arrivare a qualcosa di utile.
Ad esempio c'è il seguente risultato noto: il prodotto di $k$ interi consecutivi è divisibile per $k!$.
Ovvero
$((m+1)(m+2)...(m+k))/(k!)$ è intero.
Da questo, moltiplicando sopra e sotto per $l!$, si giunge a
$((m+k)!)/(k!m!)$ ma questo è
$((k+m),(m))$ o pensandoci, anche $((k+m),(k))$
A tal proposito, tempo fa aprii un topic su questo
http://olimpiadi.dm.unibo.it/oliForum/v ... ght=#94722
Ciao!
Non mi pare una dimostrazione.
Probabilmente muovendosi con quelle considerazione, si può arrivare a qualcosa di utile.
Ad esempio c'è il seguente risultato noto: il prodotto di $k$ interi consecutivi è divisibile per $k!$.
Ovvero
$((m+1)(m+2)...(m+k))/(k!)$ è intero.
Da questo, moltiplicando sopra e sotto per $l!$, si giunge a
$((m+k)!)/(k!m!)$ ma questo è
$((k+m),(m))$ o pensandoci, anche $((k+m),(k))$
A tal proposito, tempo fa aprii un topic su questo
http://olimpiadi.dm.unibo.it/oliForum/v ... ght=#94722
Ciao!
"WiZaRd":
Si potrebbe provare per induzione che il numero della parti con $k$ di un insieme $S$ di $n$ elementi è $((n),(k))$.
...mmmmmvuoi dire che siccome $((n),(k))$ è il numero delle parti e siccome il numero delle parti è naturale allora $((n),(k))$ è naturale o mi stai suggerendo qualcosa che mi sfugge?
Grazie a tutti.
io posso proporti due alternative, e comunque se usi il metodo "operativo" il consiglio di WiZaRd va tenuto in debito conto.
- ti posso citare la Formula di Stifel: $((n),(k))=((n-1),(k))+((n-1),(k-1))$
la quale giustifica la costruzione del "triangolo aritmetico" o di Pascal o di Tartaglia (in "verticale", cioè come si fa di solito).
- puoi far riferimento al significato insiemistico (come ti ha ricordato WiZaRd), o anche alla costruzione "in orizzontale" del triangolo aritmetico, cioè come si costruisce una generica riga senza ricorrere alle precedenti:
$((n),(0))=1$
$((n),(1))=((n),(0))*n/1=n$
$((n),(2))=((n),(1))*(n-1)/2=(n(n-1))/2$, intero perché almeno uno dei due tra n ed n-1 è pari
$((n),(3))=((n),(2))*(n-2)/3=(n(n-1)(n-2))/(2*3)$, intero perché almeno uno dei tre ... è multiplo di 3
vado avanti con il 4 che non è un numero primo e quindi potrebbe essere meno banale. per il 5 dovrebbe essere banale. per il 6 potresti provarci tu.
$((n),(4))=((n),(3))*(n-3)/4=(n(n-1)(n-2)(n-3))/(1*2*3*4)$ è intero perché dei quattro numeri due sono pari ed uno dei due è multiplo di 4 ...
ciao. spero ti sia stato d'aiuto il mio intervento.
- ti posso citare la Formula di Stifel: $((n),(k))=((n-1),(k))+((n-1),(k-1))$
la quale giustifica la costruzione del "triangolo aritmetico" o di Pascal o di Tartaglia (in "verticale", cioè come si fa di solito).
- puoi far riferimento al significato insiemistico (come ti ha ricordato WiZaRd), o anche alla costruzione "in orizzontale" del triangolo aritmetico, cioè come si costruisce una generica riga senza ricorrere alle precedenti:
$((n),(0))=1$
$((n),(1))=((n),(0))*n/1=n$
$((n),(2))=((n),(1))*(n-1)/2=(n(n-1))/2$, intero perché almeno uno dei due tra n ed n-1 è pari
$((n),(3))=((n),(2))*(n-2)/3=(n(n-1)(n-2))/(2*3)$, intero perché almeno uno dei tre ... è multiplo di 3
vado avanti con il 4 che non è un numero primo e quindi potrebbe essere meno banale. per il 5 dovrebbe essere banale. per il 6 potresti provarci tu.
$((n),(4))=((n),(3))*(n-3)/4=(n(n-1)(n-2)(n-3))/(1*2*3*4)$ è intero perché dei quattro numeri due sono pari ed uno dei due è multiplo di 4 ...
ciao. spero ti sia stato d'aiuto il mio intervento.
Si potrebbe usare anche il Principio di Induzione Matematica.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo