OliForum Matematico

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

per binomiale si intende: $ \binom{n}{k} = \dfrac{n!}{k!(n-k)!} $

Penso che avresti potuto metterlo anche in combinatoria

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
Comunque mi viene in mente solo

Ovvero mostrare che $ k! $ divide il prodotto di $ k $ interi consecutivi, che è un problema abbastanza noto

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$.

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.

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 ( ).

ok, ma una dimostrazione solamente in teoria dei numeri è possibile? del tipo mostrare in tdn che $ k! \mid \frac{n!}{(n-k)!} $?

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).

a me interesserebbe soprattutto trovare un modo per arrivare a soluzione in tdn, quindi qualche hint o qualche abbozzo di soluzione è molto utile, grazie

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)$?

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.

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
per ora va bene?

Benissimo - quella è l'idea; ora, come hai notato anche tu, c'è da capire come sistemare i casi base.

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??