OliForum Matematico

Pare che venga da una recente gara a squadre, ma non conosco la fonte esatta:

Trovare il numero di sottoinsiemi $S\subseteq \{1,2,\ldots,n\}$ non vuoti tali che se $x \in S$ allora $x+1 \notin S$.

jordan ha scritto:se $x \in S$ allora $x \notin S$.

In che modello dell'aritmetica?

E' il terzo di fila, wow :O

Non sono tanto bravo e scrivo da cellulare xD Non ho controllato calcoli o conti (appunto perché scrivo con un cellulare ... E in un letto .-.) ma spero che sia giusto (o se é sbagliato che sia almeno d'aiuto) xD
PS non ho usato il Latex sia perche non sono molto bravo sia per i motivi tecnici scritti sopra ,se non si capisce ditelo che domani sistemo ^.^

Che ne dici di provare una successione??

Colgo l'occasione per rilanciare:
dati $ n,k\in\mathbb{N} $ trovare il numero $ f(n,k) $ di sottoinsiemi di $ \{1,2,...,n\} $ non contenenti due numeri consecutivi e aventi cardinalità $ k $.

Cardinalità: numero di elementi dell'insieme?

(bonus question: interpretare i risultati trovati nel problema e nella generalizzazione di Luca95 come un modo per scrivere i numeri di Fibonacci come somma di elementi che compaiono in opportune posizioni del triangolo di Tartaglia).

Si, cardinalità=numero di elementi dell'insieme.

Quoto fph, combinando i due risultati si trova un'interessante relazione

Tento una soluzione

Si associ ad ogni elemento dell'insieme $A={1,2,...,n}$ rispettivamente una $S$ se tale elemento figura nell'insieme $K$ richiesto o una $N$ se esso non compare.
Si ha così una successione di $S$ e $N$ in cui il numero totale delle prime è uguale a $k$, mentre $S+N=n$. Inoltre, detto $C$ l'insieme richiesto, dato che $x\in\mathbf{C} \Rightarrow x+1\notin\mathbf{C}$, ogni $S$ è seguita da una $N$.
Pertanto, $n=2k+a$.
Ciascuna sequenza accettabile, dunque, sarà una permutazione con ripetizione del gruppo $SN$, che chiameremo $B$ per semplicità, e delle $N$ restanti, in numero pari ad $a=n-2k$.
Tali permutazioni sono date dalla formula $f(a;k)=\frac{(k+a)!}{k! \cdot a!}=\frac{(k+n-2k)!}{k! \cdot (n-2k)!}=\frac{(n-k)!}{k! \cdot (n-2k)!}$.
Tuttavia, così si escludono i casi in cui $n\in\mathbf{C}$.
Si considerino, quindi, le successioni in cui si ha $S$ all'n-esimo posto. Queste sono uguali alle permutazioni di $k−1$ gruppi $SN$ e $a+1$ $N$ spaiate, date da $f(a+1;k-1)=\frac{(k-1+n-2k+1)!}{(k-1)!\cdot (n-2k+1)!}=\frac{(n-k)!}{(k-1)! \cdot (n-2k+1)!}$.
Infine, gli insiemi di cardinalità $k$ richiesti sono $\frac{(n-k)!}{k! \cdot (n-2k)!} + \frac{(n-k)!}{(k-1)! \cdot (n-2k+1)!}$.

Mi hai battuto sul tempo Enigmatico xD
Stavo scrivendo anch'io una risposta e la posto comunque perché è diversa (ma spero ugualmente giusta) (ed è bella la tua idea di usare le lettere alla Callegari ^.^)

Io avevo pensato di usare di nuovo il procedimento induttivo come Luca:

Per aumentare di un elemento l'insieme e avere n+1 mantenendo uguale k ,io ho a disposizione tutti i sottoinsiemi in f(n,k) che rimangono ugualmente validi a cui sommare tutti i sottoinsiemi da un elemento in meno che non comprendono l'elemento n : f(n-1,k-1)

f(n+1,k)=f(n,k)+f(n-1,k-1)

f(1,1)=1
f(2,1)=2
f(2,2)=0
f(x,0)=0

Con $ 1 \leq k \leq n/2 $ [Grazie Enigmatico ]

Manca che $k\leq n/2$ come ho scritto sopra, così ti eviti di fare a mano casi inutili e sveltisci molto il procedimento

EDIT: scusa, così pare alquanto falsa...
Meglio dire che $1 \leq k \leq n/2$

Corretto , grazie ^.^ ora diamo un occhiata a Tartaglia , che Fph era abbastanza gasato e voglio scoprire perché xD

Allora , devo ancora formalizzare ma intanto metto quest'osservazione.

Osservazione : Il numero di sottoinsiemi senza elementi consecutivi in un insieme da $ n $ elementi è dato da:

$ n + T_{n-2} + T_{n-4} +... $ finche (n-2k) non è minore di zero

Questo si può riformulare nel triangolo con $ \binom{n}{1} + \binom{n-2}{2} + \binom{n-4}{2} + ... $
Ma vengono sempre più bassi di 1 xD quindi aggiungiamo 1 xD ecco.. se magari qualcuno aggiunge un po' di teoria a quest'osservazione magari è meglio xD

EDIT : Come non detto xD funziona solo fino a 5-6