Calcolo combinatorio scuola superiore catania

[fili7.5]

Salve, avrei bisogno di spiegazioni su questo risultato
$ (sum_(k = 1)^(n-r+1)k( (n-k), (r-1) ) )/( ((n), (r) ) ) = (n+1)/(r+1) $
è il passaggio finale dell'esercizio 8 del test di ammissione 2011 alla scuola superiore di catania per matematica. Non sono riuscito a capire se questa è una formula esistente o è il risultato di un calcolo che devo eseguire. Qualcuno può aiutarmi?

[kobeilprofeta]

Prova a Sostituire con valori semplici, esempio $n=4$ e $r=3$ e sviluppa tutta la sommatoria. In questo modo capirai il significato dell'espressione.

[fili7.5]

Sono ritornato sull'esercizio da poco...adesso risulta tutto, grazie. Non ho capito solo se quella è una formula bella e fatta che si può trovare su un libro oppure no

[wrugg25]

Approfitto di questo topic per chiedere informazioni anche io su tale passaggio: si ha che i due membri di quell'uguaglianza sono uguali, e in effetti assegnando dei valori numerici ad $n$ ed $r$ ciò è evidente... ma come lo si può determinare, a livello meramente "algebrico"? Quali semplificazioni, quali sostituzioni vanno fatte per trasformare il primo membro nel secondo?

[Thomas]

Un modo per verificare l'identita' e' riscriverla come:

$ (sum_(k = 1)^(n-r+1)k( (n-k), (r-1) ) )=((n+1), (r+1) ) $

A questo punto a destra e sinistra si vedono due modi diversi di scrivere la stessa cosa. Quanti sono i modi di scegliere $r+1$ caselle tra $n+1$ ?
Fissiamo innanzitutto le caselle e numeriamole da 1 a $n+1$. Prendiamo tra queste un qualsiasi gruppo di $r+1$ caselle e ordiniamole anche loro in maniera crescente. Una combinazione possibile e' quindi descritta da una sequeza crescente $a_1<a_2<...<a_{r+1}$. Quante sono le combinazioni tali che $a_2=k$ ? Che valori puo' assumere $k$?

Sono curioso di vedere altre dimostrazioni a me questa non pare cosi' immediata...

[wrugg25]

Io la tua dimostrazione non l'ho capita

Però, se è vero che

$ (sum_(k = 1)^(n-r+1)k( (n-k), (r-1) ) )=((n+1), (r+1) ) $

(a proposito, come l'hai dimostrata 'sta somma?), allora risulta che:
$ mu (n, r) = (sum_(k = 1)^(n-r+1)k( (n-k), (r-1) ) )/( ((n), (r) ) ) = (((n+1), (r+1)))/(((n), (r))) = (((n+1)!)/((r+1)!(n-r)!))/((n!)/((n-r)!r!)) = ((n+1)!r!)/((r+1)!n!) = (n+1)/(r+1) $

E il quesito è risolto.

[Thomas]

E' una tecnica carina per provare identità con i binomiali. Ti rimando a questo link:

http://www.cut-the-knot.org/arithmetic/ ... tity.shtml

in particolare alla "combinatorial proof". Applicando ragionamenti simili (ho scritto come si comincia sopra), dovresti essere in grado di dimostrare la tua formula e molte altre identità con i binomiali.

Queste dimostrazioni sono una manifestazione di una idea ancora più generale, si chiama "double counting". "Conti" in due modi diversi la stessa cosa. Avendo tu contato sempre la stessa cosa, i risultati saranno uguali e li puoi eguagliare. Naturalmente più i modi che usi per contare sono diversi, più le identità che ottieni sono potenti! Si riesce a vedere nella "combinatorial proof" che questa è l'idea di fondo?

[Thomas]

In ogni caso ci saranno di sicuro dimostrazioni diverse, se questa non ti soddisfa... Forse girando un po' nel sito che ti ho indicato trovi ispirazione