Indicizzazioni ($\mathbb{N} ^2$) e cose

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
RiccardoKelso

Indicizzazioni ($\mathbb{N} ^2$) e cose

Messaggio da RiccardoKelso »

Non vi sto per proporre un vero e proprio problema olimpico (non sono difatti sicuro sia giusto postare qui), bensì spero che qualcuno abbia voglia di darmi una mano in un modo o nell'altro nel tentativo di generalizzare questo problema: viewtopic.php?f=16&t=19366&p=160103.
La mia intenzione, in pratica, era di capire qualcosa sul numero di sottoinsiemi di cardinalità qualsiasi dei primi $n$ naturali che non contenessero $k$ numeri consecutivi.
Fissiamo un paio di notazioni: sia $R_n^{i,k}$ il numero di sottoinsiemi di $\{1,...,n\}$ di cardinalità $i$ non contenenti $k$ numeri consecutivi, e $R_n^{T,k}=\sum_{j=0}^{n} R_n^{j,k}$.
Come dal post linkato sopra, si ha $R_n^{T,2}=F_{n+1}$, riferendomi ai numeri di Fibonacci. Poi, per $k$ generico, si trova $R_n^{T,k}=2R_{n-1}^{T,k}-R_{n-k-1}^{T,k}$, il che porta a una fantasmagorica $x^{k+1}-2x^k+1=0$. $\forall \space k$ si ha $x^{k+1}-2x^k+1=(x-1)(x^k-\sum_{j=0}^{k-1}x^j)$, il che per $k=2$ è rassicurante e tutto torna, ma per $k>2$ diviene pressoché intrattabile.
Allora ho tentato un'altra via: ancora come da post, si ha $R_n^{i,2}=\binom{n+1-i}{i}$. Cosa riusciamo a dire su $R_n^{i,k}$? Con metodi puramente combinatori non ho cavato nulla di definitivo, ma dovrebbe valere $R_n^{i,k}=R_{n-1}^{i,k}+R_{n-1}^{i-1,k}-R_{n-1-k}^{i-k,k}$, in quanto sommiamo i sottoinsiemi che ci van bene di $\{1,...,n-1\}$ e poi consideriamo $n$ appartenente al sottoinsieme e quindi togliamo i sottoinsiemi di $\{1,...,n-1\}$ che contengono gli ultimi $k-1$. Da qui il titolo: esiste qualcosa sulle formule ricorsive dipendenti da due indici?? Penso di essermi reso conto del fatto che esistono tanti (troppi) possibili metodi per attaccare questo problema, e anche per questo spero che qualcuno abbia la benevolenza di dirmi due paroline a riguardo, che possono anche benissimo essere "no, lascia stare", anche se sarebbe apprezzatissima una minima spiegazione del perchè.
Rispondi