teoria binomiale

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Nadal21

teoria binomiale

Messaggio da Nadal21 »

Mostrare che $ \binom{n}{k} $ è intero per ogni $ k<n $.

per binomiale si intende: $ \binom{n}{k} = \dfrac{n!}{k!(n-k)!} $
Saro00
Messaggi: 115
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Re: teoria binomiale

Messaggio da Saro00 »

Penso che avresti potuto metterlo anche in combinatoria
Testo nascosto:
Considero una stringa di $ n $ lettere, di cui $ k $ sono A e $ n-k $ sono B.
Ora mi chiedo quante sono le possibili stringhe diverse.
Esse sono esattamente $ \frac{n!}{k!(n-k)!} $, che deve per forza essere intero poiché il numero di anagrammi è un numero intero.
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)
RiccardoKelso

Re: teoria binomiale

Messaggio da RiccardoKelso »

Penso che si riferisse al mostrare che $k!\mid \frac{n!}{(n-k)!}$ senza usare la combinatoria, anche perché in caso contrario non sarebbe nemmeno necessario distaccarsi dalle combinazioni :lol:
Comunque mi viene in mente solo
Testo nascosto:
il numero di fattori di $\frac{n!}{(n-k)!}$ è esattamente $k$ e sono tutti consecutivi, di conseguenza ogni fattore di $k!$ trova almeno un suo multiplo in $\frac{n!}{(n-k)!}$. A grandi linee poco formali.
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: teoria binomiale

Messaggio da mr96 »

Ovvero mostrare che $ k! $ divide il prodotto di $ k $ interi consecutivi, che è un problema abbastanza noto
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

RiccardoKelso ha scritto:
Testo nascosto:
il numero di fattori di $\frac{n!}{(n-k)!}$ è esattamente $k$ e sono tutti consecutivi, di conseguenza ogni fattore di $k!$ trova almeno un suo multiplo in $\frac{n!}{(n-k)!}$. A grandi linee poco formali.
Occhio che questo ragionamento in generale non funziona: per dimostrare che un numero è multiplo di $4\cdot 2$, non basta dire che tra i suoi fattori ci sono un multiplo di $4$ e un multiplo di $2$. Insomma, nel tuo caso non è sufficiente lavorare sui fattori separatamente e dire che $i\mid N$ per ogni $i \leq k$.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
PIELEO13
Messaggi: 58
Iscritto il: 05 feb 2015, 23:12

Re: teoria binomiale

Messaggio da PIELEO13 »

Saro00 ha scritto: Considero una stringa di $ n $ lettere, di cui $ k $ sono A e $ n-k $ sono B.
Ora mi chiedo quante sono le possibili stringhe diverse.
Esse sono esattamente $ \frac{n!}{k!(n-k)!} $, che deve per forza essere intero poiché il numero di anagrammi è un numero intero.
Guarda che non puoi dimostrarlo così. Per prima cosa si deve dimostrare che $ \frac{n!}{k!(n-k)!} $ è intero. Dopo di che si dimostra che in questo caso $ \frac{n!}{k!(n-k)!} $ è la formuletta per le permutazioni con ripetizione. Non è che puoi dire: visto che $ \frac{n!}{k!(n-k)!} $ è la formula per le permutazioni allora è intero. Il fatto che puoi trovare gli anagrammi è una conseguenza del fatto che sia intero, non una causa.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

PIELEO13 ha scritto:Non è che puoi dire: visto che $ \frac{n!}{k!(n-k)!} $ è la formula per le permutazioni allora è intero. Il fatto che puoi trovare gli anagrammi è una conseguenza del fatto che sia intero, non una causa.
Al contrario, una dimostrazione di questo tipo, in generale, è perfettamente valida. Per dimostrare che 15/5 è intero, puoi prendere 15 oggetti e dimostrare che si possono mettere in tante scatole da 5 elementi senza che ne avanzi nessuno. È un altro modo di scrivere che quando dividi 15 per 5 hai resto zero, se vuoi.

Il problema di quella dimostrazione è che chiederei più dettagli nel dimostrare la formula $ \frac{n!}{k!(n-k)!} $, perché è lì che sta tutto il lavoro. Insomma, vorrei leggere un discorso del tipo "divido questi $n!/(n-k)!$ elementi in tante scatole, ognuna delle quali contiene $k!$ elementi", oppure un double-counting (
Testo nascosto:
"mostro che un modo alternativo di contare le $n!/(n-k)!$ disposizioni ordinate si ottiene prendendo i $\binom{n}{k}$ sottoinsiemi e poi ordinandoli in tutti i modi possibili"
).
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Nadal21

Re: teoria binomiale

Messaggio da Nadal21 »

ok, ma una dimostrazione solamente in teoria dei numeri è possibile? del tipo mostrare in tdn che $ k! \mid \frac{n!}{(n-k)!} $?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

Sicuramente! Ce ne sono diverse. Vuoi qualche hint? Non mi è chiaro se hai proposto il problema per farlo risolvere a qualcun altro (in qual caso lascio volentieri la palla a qualcuno "in età olimpica"), o se è perché ti interessa vedere una soluzione (in tal caso te ne posso abbozzare un paio).
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Nadal21

Re: teoria binomiale

Messaggio da Nadal21 »

a me interesserebbe soprattutto trovare un modo per arrivare a soluzione in tdn, quindi qualche hint o qualche abbozzo di soluzione è molto utile, grazie :)
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

Un modo abbastanza indolore, per esempio, è per induzione su $n$ e $k$ contemporaneamente. Supponi di aver già dimostrato che $k! \mid n(n-1)\dots(n-k+1)$ per tutti gli $n'<n$ e $k'<k$. Cosa puoi dire su $n(n-1)\dots(n-k+1) - (n-1)(n-2)\dots(n-k)$?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
PIELEO13
Messaggi: 58
Iscritto il: 05 feb 2015, 23:12

Re: teoria binomiale

Messaggio da PIELEO13 »

fph ha scritto: Il problema di quella dimostrazione è che chiederei più dettagli nel dimostrare la formula $ \frac{n!}{k!(n-k)!} $, perché è lì che sta tutto il lavoro.
Assolutamente d'accordo con te, è quello che intendevo, anche se è evidente che mi sono spiegato male: non si può prendere per vera questa "formula" ma bisogna approfondire le considerazioni al riguardo.
Nadal21

Re: teoria binomiale

Messaggio da Nadal21 »

su quella differenza si può dire che è multipla di $ k $!!
provo dunque a formalizzare un poco:

Supponiamo che $h\mid m(m-1)(m-2)\ldots (m-h+1)$ $\forall h\leq k, m<n$. Mostriamo che se vale per $ m<n $, allora vale anche per $n$. notiamo che $ n(n-1)\dots(n-k+1) - (n-1)(n-2)\dots(n-k)=k(n-1)(n-2)\dots(n-k+1) $.

$k! \mid (n-1)(n-2)\dots(n-k)$ e anche
$(k-1)! \mid (n-1)(n-2)\dots(n-k+1)$ per ipotesi induttiva, dalla seconda segue che $k! \mid k(n-1)(n-2)\dots(n-k+1)$
Ma allora siccome sono interi entrambi divisibili per $ k! $ si ha che $k! \mid n(n-1)(n-2)\dots(n-k+1)$.

Mi manca ora la parte dove fisso $ n $ e varia $ k $, it's coming soon :wink: :lol:
per ora va bene?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

Benissimo - quella è l'idea; ora, come hai notato anche tu, c'è da capire come sistemare i casi base.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Nadal21

Re: teoria binomiale

Messaggio da Nadal21 »

il caso base penso sia $n=1$ e $k=1$ se si dimostra anche la seconda parte.
la seconda parte sto avendo difficoltà a risolverla: ho pensato che $\forall k$ fra i termini $n, (n-1), \ldots , (n-k+1)$ vi è sempre un multiplo di $k$, ma non riesco a mostrare che $k! \mid n(n-1)\ldots (n-k+1)$ al variare di $k$ perché non riesco a far vedere che $(k-1)!$ non si "mangia" il multiplo di $k$ nella divisione.
come posso fare??
Rispondi