Insiemi senza elementi consecutivi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
santilli
Messaggi: 24
Iscritto il: 30 set 2014, 20:59
Località: Rovigo

Re: Insiemi senza elementi consecutivi

Messaggio da santilli »

Allora xD ho la soluzione! (spero)

La mia osservazione precedente è sbagliata perchè non si sommano sempre i numeri triangolari ma:

f(n,k)= $ \binom{n-2(k-1)}{k} $

Quindi con $ k=1 $ uso $ n $ poi con $ k=2 $ i triangolari, poi i tetraedici ecc..

Per avere $ F_n $ devo fare $ \sum_{k=1}^{n/2} \binom{n-2(k-1)}{k} $

Ma viene sempre $ F_{n} -1 $ quindi aggiungiamo 1 (magari aggiungiamo un binomiale uguale a $ 1 $ come $ \binom{n+2}{0} $? xD

Che dite?
16 esimi GAS '2016 :D finalmenteeeee! #RovigoPower xD
Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: Insiemi senza elementi consecutivi

Messaggio da luca95 »

Ok visto che questo post è un po' morto provo a mettere la mia soluzione. Vogliamo dimostrare che
$ \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}=F_n $ ma visto che tanto $ \binom{n}{k}=0 $ per $ k>n $ possiamo scrivere
$ \sum_{k=0}^{\infty}\binom{n-k}{k}=F_n $ che è più bello.
Ora contiamo le stringhe binarie di lunghezza n che non contengono zeri consecutivi, ragionando come nel caso degli insiemi si può trovare che queste sono $ F_{n+1} $. Consideriamo ora le stringhe del tipo cercato di lunghezza $ n $ senza zeri: ce ne sarà chiaramente solo una. Di quelle con un solo zero ce ne saranno $ \binom{n}{1} $, e se abbiamo più zeri? Possiamo mettere in corrispondenza le stringhe senza zeri consecutivi contenenti $ k $ zeri con le stringhe qualunque di lunghezza $ n+1-k $, che sono chiaramente $ \binom{n+1-k}{k} $: ci basta porre un 1 a destra di ogni zero fatta eccezione per l'ultimo che compare, ad esempio 1001001$ \mapsto $1010110101, 1000$ \mapsto $101010 ecc.. (per il procedimento inverso basta cancellare tutti gli 1 che stanno a destra di uno zero eccetto quello accanto all'ultimo). Abbiamo quindi
$ 1+\binom{n}{1}+\binom{n-1}{2}+\binom{n-2}{3}+...=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\binom{n-2}{3}+...=\sum_{k=0}^{\infty}\binom{n+1-k}{k}=F_{n+1} $
e sostituendo $ n $ a $ n+1 $ otteniamo la formula cercata.
Rispondi