Indicizzazioni ($\mathbb{N} ^2$) e cose
Inviato: 18 feb 2017, 20:44
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è.
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è.