)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.
Quesito maturità livello Archimede (2)
Quesito maturità livello Archimede (2)
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.
)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.
"[L'universo] è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche; [...] senza questi è un aggirarsi vanamente per un oscuro laberinto." Galileo Galilei, Il saggiatore, 1623
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
Sì, era veramente immediato... Ma vedrai che ce ne saranno di così anche tra due anni! 
Comunque anche l'interpretazione non è difficile...
Comunque anche l'interpretazione non è difficile...
"[L'universo] è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche; [...] senza questi è un aggirarsi vanamente per un oscuro laberinto." Galileo Galilei, Il saggiatore, 1623
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
Mah, alla fine come pippa mentale non è neanche molto ardita...
Tu come lo hai dimostrato?
Tu come lo hai dimostrato?
"[L'universo] è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche; [...] senza questi è un aggirarsi vanamente per un oscuro laberinto." Galileo Galilei, Il saggiatore, 1623
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
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
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
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
Non ho capito il ragionamento dietro questo passaggio...Maioc92 ha scritto: contiamo ogni combinazione $ \displaystyle\binom{k} {k-1}+1=k+1 $ volte
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.
"[L'universo] è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche; [...] senza questi è un aggirarsi vanamente per un oscuro laberinto." Galileo Galilei, Il saggiatore, 1623
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
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 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
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Si, in effetti è il modo migliore per scriverlo chiaramente.fph ha scritto:L'idea è ottima ma è facile spiegarla male.
Hint sul modo migliore di formalizzarla: double-counting sui modi di scegliere un "comitato" composto da un presidente più altri k membri
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...
Nella mia ignoranza non conoscevo questa questione...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.
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 $
"[L'universo] è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche; [...] senza questi è un aggirarsi vanamente per un oscuro laberinto." Galileo Galilei, Il saggiatore, 1623
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Forse la definizione che intende edriv è questa: il numero di sottoinsiemi di {1,...,n} che hanno cardinalità k.Davide90 ha scritto:Nella mia ignoranza non conoscevo questa questione...
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 $
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Intendevo che:Jacobi ha scritto:
- 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à.