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è.
Indicizzazioni ($\mathbb{N} ^2$) e cose
Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Vai a
- Getting Started
- ↳ Comitato di accoglienza nuovi utenti
- ↳ Ciao a tutti, mi presento:
- ↳ Glossario e teoria di base
- Problem solving olimpico
- ↳ Algebra
- ↳ Combinatoria
- ↳ Geometria
- ↳ Teoria dei Numeri
- Altri esercizi
- ↳ Matematica ricreativa
- ↳ Matematica non elementare
- ↳ Fisica
- ↳ Informatica
- Supporto tecnico
- ↳ Il sito delle olimpiadi della matematica
- ↳ LaTeX, questo sconosciuto
- Gare e concorsi
- ↳ Olimpiadi della matematica
- ↳ Gara a squadre
- ↳ Giornalino del gruppo tutor
- ↳ Altre gare
- ↳ Scuole d'eccellenza e borse di studio
- Tra un problema e l'altro...
- ↳ Cultura matematica e scientifica
- ↳ Il colmo per un matematico
- ↳ Discorsi da birreria
- I messaggi del vecchio forum (memoria storica di sola lettura)
- ↳ [vecchio forum]Le olimpiadi della matematica
- ↳ [vecchio forum]Come vedo il sito delle Olimpiadi della Matematica
- ↳ [vecchio forum]Giornalino della Matematica
- ↳ [vecchio forum]Gruppo Tutor
- ↳ [vecchio forum]Proponi gli esercizi
- ↳ [vecchio forum]Compro, baratto, vendo, rido!
- ↳ [vecchio forum]Cesenatico
- ↳ [vecchio forum]Sondaggi, che passione!
- ↳ [vecchio forum]Proposte ai Responsabili Provinciali
- ↳ [vecchio forum]Tra responsabili
- ↳ [vecchio forum]Non solo Matematica!