OliForum Matematico

Posto, sempre per i più giovani, un altro quesito della maturità di quest'anno che potrebbe essere carino da interpretare dal punto di vista combinatorio (la dimostrazione richiesta dalla Gelmini con lo svolgimento dei conti è troppo banale, dai )

Si dimostri l’identità $ \displaystyle \binom{n}{k+1}=\binom{n}{k}\cdot \dfrac{n-k}{k+1} $ con n e k naturali e n > k.

Dal punto di vista del significato dovrei pensarci 1 attimo....però in effetti invece di 'dimostra' potevano scrivere 'fai 2 conti'. Spero di trovarlo anch'io un quesito cosi tra 2 anni

Sì, era veramente immediato... Ma vedrai che ce ne saranno di così anche tra due anni!
Comunque anche l'interpretazione non è difficile...

ahhhhhhhhhhh. L'ho intuito ora.....
però sono molto più immediati i 2 calcoli devo dire (almeno per me)

Mah, alla fine come pippa mentale non è neanche molto ardita...
Tu come lo hai dimostrato?

come ho detto prima più che una dimostrazione vera e propria è un'intuizione...
Perchè ovviamente affinchè una combinazione di k elementi diventi di k+1 elementi va combinata con uno degli n-k elementi rimanenti. Però moltiplicando per n-k contiamo ogni combinazione $ \displaystyle\binom{k} {k-1}+1=k+1 $ volte, e quindi dividiamo per k+1.
Come dimostrazione non credo sia molto valida, ma il ragionamento che ho fatto è questo

Maioc92 ha scritto: contiamo ogni combinazione $ \displaystyle\binom{k} {k-1}+1=k+1 $ volte

Non ho capito il ragionamento dietro questo passaggio...
Comunque l'idea è esattamente quella che hai scritto: alla fine dividiamo per k+1, perchè ogni gruppo è stato contato una volta per ogni suo componente, quando questo è stato aggiunto agli altri k.

infatti fondamentalmente è quello, è solo che io sono una frana a spiegare. Forse l'ho inutilmente complicato....

L'idea è ottima ma è facile spiegarla male. Purtroppo un po' tutta la combinatoria ha questo problema...
Hint sul modo migliore di formalizzarla: double-counting sui modi di scegliere un "comitato" composto da un presidente più altri k membri

Purtroppo la difficoltà del problema dipende solo da come si definisce $ n \choose k $...
Se uno fa una definizione "ad hoc" (ovvero con i fattoriali), il problema si risolve subito, ma qualche correttore potrebbe considerarlo (quanto ingiustamente?) sbagliato.

non credo che sia un problema definire il coefficiente binomiale con i fattoriali (che, d'altrocanto, e' la definizione piu frequente che si trova)

fph ha scritto:L'idea è ottima ma è facile spiegarla male. Purtroppo un po' tutta la combinatoria ha questo problema...
Hint sul modo migliore di formalizzarla: double-counting sui modi di scegliere un "comitato" composto da un presidente più altri k membri

Si, in effetti è il modo migliore per scriverlo chiaramente.
Contiamo in quanti modi è possibile scegliere un comitato formato da k membri e un presidente, su un insieme formato da n persone.
1° MODO: Scegliamo subito tutto il comitato più il presidente: scegliamo quindi k+1 persone fra le n totali. In questo modo ho $ \binom{n}{k+1} $ possibili comitati+presidenti, e per ognuno di essi ho k+1 modi di scegliere una persona all'interno del comitato che faccia il presidente. Totale: $ \binom{n}{k+1}\cdot (k+1) $ .
2° MODO: Scegliamo prima il comitato, poi fra i rimanenti non appartenenti al comitato scegliamo il presidente. Ho $ \binom{n}{k} $ modi di scegliere il comitato, da moltiplicare per il numero di rimanenti, ognuno dei quali può essere scelto come presidente. Totale: $ \binom{n}{k}\cdot (n-k) $
Uguagliando le due espressioni, abbiamo la tesi.

Così direi che suona molto meglio in effetti...

edriv ha scritto:Purtroppo la difficoltà del problema dipende solo da come si definisce $ n \choose k $ ...
Se uno fa una definizione "ad hoc" (ovvero con i fattoriali), il problema si risolve subito, ma qualche correttore potrebbe considerarlo (quanto ingiustamente?) sbagliato.

Nella mia ignoranza non conoscevo questa questione... potresti spiegare meglio?
Cioè, il binomiale da quanto so io si può definire indifferentemente come:
- $ \dfrac{n!}{k!(n-k)!} $
- Numero nell'n-esima riga e k-esima colonna del triangolo di Tartaglia
- Coefficiente del termine $ a^k b^{n-k} $ nel polinomio $ (a+b)^n $

beh,invece a me sembrava giusta anche quella di prima vez...

Davide90 ha scritto:Nella mia ignoranza non conoscevo questa questione... potresti spiegare meglio?
Cioè, il binomiale da quanto so io si può definire indifferentemente come:
- $ \dfrac{n!}{k!(n-k)!} $
- Numero nell'n-esima riga e k-esima colonna del triangolo di Tartaglia
- Coefficiente del termine $ a^k b^{n-k} $ nel polinomio $ (a+b)^n $

Forse la definizione che intende edriv è questa: il numero di sottoinsiemi di {1,...,n} che hanno cardinalità k.

Jacobi ha scritto: non credo che sia un problema definire il coefficiente binomiale con i fattoriali (che, d'altrocanto, e' la definizione piu frequente che si trova)

Intendevo che:
- se uno prende come definizione di coefficiente binomiale quella con i fattoriali, il problema è fortemente banale e questo credo che nessuno possa negarlo... neanche il liceale medio, in teoria. (in realtà, il liceale medio si impalla lo stesso davanti alla parola "dimostrare", visto che nella sua testa la dimostrazione è qualcosa che scrive il prof alla lavagna, e durante la matura lui non è un prof, e non scrive su una lavagna)
- se uno prende un'altra definizione di binomiale, ad esempio quella proposta da Tibor, il problema aumenta considerevolmente di difficoltà.