Somma combinatorica

[Pachisi]

Dimostrare \(\displaystyle \sum_{p=k-3}^{n-3} \binom{p}{k-3}\binom{n-p-1}{2}=\binom{n}{k}\).

[Pachisi]

Nel caso qualcuno fosse ancora interessato, metto un hint piccolo

Provare con una dimostrazione che conta entrambi i lati, non analitica.

[orsoulx]

Penso di esser riuscito a porla in modo comprensibile.

Si abbiano $ k $ caratteri uguali, diciamo $ a $ ed $ n-k $ caratteri uguali fra loro, ma diversi dai primi, diciamo $ b $. Il numero di anagrammi diversi che si possono formare con questi $ n $ caratteri è $ ((n), (k)) $.
Possiamo scomporre queste stringhe secondo la posizione occupata dal terzultimo carattere $ a $. Per ciascuna posizione si troveranno due sottostringhe, la prima delle quali conterrà $ k-3 $ caratteri $ a $, mentre la seconda ne conterrà $ 2 $. Indicando con $ p $ la lunghezza della prima sottostringa, deve essere $ p>=k-3 $, numero di caratteri $ a $ contenuti; mentre la seconda sottostringa, lunga $ n-1-p $, dovendo contenere $ 2 $ caratteri $ a $, impone che sia $ n-1-p>=2 \rightarrow p<=n-3$.
Per ciascuna suddivisione il numero di anagrammi formabili è allora $ ((p),(k-3))((n-p-1),(2)) $, che sommati per tutti i possibili valori di $ p $, portano a $ \sum_{p=k-3}^{n-3} ((p),(k-3))((n-p-1),(2)) $ dimostrando l'identità proposta.

Ciao
B.

[Pachisi]

Bellissima

[orsoulx]

Non esagerare! Rimane un po' confusa. L'idea di partenza erano i percorsi nella geometria del taxi, ma poi l'ho abbandonata, perché necessitava di troppe spiegazioni. Tu come l'hai affrontata?
Ciao
B.

[dan952]

[ot]Mi scuso con Pachisi dell'intrusione senza una soluzione, ma ero curioso di sapere da orsoulx come si dimostra la formula per $e^{\pi}$ scritta nella sua firma[/ot]

[Pachisi]

@orsoulx: Io inizialmente ho provato contando sottoinsiemi con diverse proprietà, ma venivano cose troppo confuse. Allora, ho fatto qualcosa di simile al tuo ma su una stringa di lettere crescenti.
@dan95: In effetti è abbastanza bizzarra come formula.

[orsoulx]

@dan95; Pachisi
[ot]conobbi quell'approssimazione grazie ad un pesce d'aprile, che il grande Martin Gardner pubblicò nel 1975 su Scientific American. L'errore relativo è meno di $ 2.5 \cdot 10^-31 $; stesso ordine di grandezza che si avrebbe fornendo la misura del diametro della galassia in cui viviamo, con l'approssimazione del raggio di van der Waals dell'oro. Wiki https://en.wikipedia.org/wiki/Heegner_n ... s_constant attribuisce ad Hermite la 'scoperta'; ... ed allora Wolfram|Alpha non c'era.[/ot]
Ciao
B.

[dan952]

Grazie per l'informazione prof.