Insiemi senza elementi consecutivi

[jordan]

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$.

[<enigma>]

se $x \in S$ allora $x \notin S$.

In che modello dell'aritmetica?

[jordan]

E' il terzo di fila, wow :O

[santilli]

Non sono tanto bravo e scrivo da cellulare xD

Testo nascosto:

ma se era in una gara a squadre (e li al posto di n c'era un numero xD) potevi provare "sommando" : Il numero di sottoinsiemi con 1 elementi (n) , quelli con 2 [n(n-2]/2 e in poi generalizzare pensando che i sottoinsiemi da k elementi (con k<n) sono {k*(k-2)*(k-4)....[k-2^(n-1)]}/(k!).
E quindi basta sommarli , cosa fattibile in una gara a squadre ma non so se venga fuori una formula abbastanza pulita in un dimostrativo

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 ^.^

[AGallese]

Che ne dici di provare una successione??

[luca95]

Testo nascosto:

Sempre tra i piedi 'sto Fibonacci
Detto $ f(n) $ il numero di tali sottoinsiemi si ha evidentemente $ f(0)=0,f(1)=1 $

ora, chiaramente i sottoinsiemi che vanno bene per $ n $ andranno bene anche per $ n+1 $, inoltre possiamo formare nuovi sottoinsiemi validi aggiungendo $ n+1 $ a un sottoinsieme valido che non contiene $ n $, ma il numero di questi è $ f(n-1) $ quindi si ha
$ f(n+1)=f(n)+f(n-1) $
da cui $ f(n)=F_ n $
dove $ F_n $ è l'ennesimo numero di Fibonacci, $ F_0=0,F_1=1 $

[luca95]

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 $.

[Enigmatico]

Cardinalità: numero di elementi dell'insieme?

[fph]

(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).

[luca95]

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

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

[Enigmatico]

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)!}$.

[santilli]

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 ]

[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$

[santilli]

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

[santilli]

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