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$.
Re: Insiemi senza elementi consecutivi
Inviato: 17 apr 2015, 13:14
da <enigma>
jordan ha scritto:se $x \in S$ allora $x \notin S$.
In che modello dell'aritmetica?
Re: Insiemi senza elementi consecutivi
Inviato: 18 apr 2015, 13:56
da jordan
E' il terzo di fila, wow :O
Re: Insiemi senza elementi consecutivi
Inviato: 26 apr 2015, 23:58
da 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 ^.^
Re: Insiemi senza elementi consecutivi
Inviato: 27 apr 2015, 15:33
da AGallese
Che ne dici di provare una successione??
Re: Insiemi senza elementi consecutivi
Inviato: 29 mag 2015, 10:18
da 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 $
Re: Insiemi senza elementi consecutivi
Inviato: 29 mag 2015, 10:43
da 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 $.
Re: Insiemi senza elementi consecutivi
Inviato: 29 mag 2015, 16:59
da Enigmatico
Cardinalità: numero di elementi dell'insieme?
Re: Insiemi senza elementi consecutivi
Inviato: 29 mag 2015, 17:17
da 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).
Re: Insiemi senza elementi consecutivi
Inviato: 29 mag 2015, 20:32
da luca95
Si, cardinalità=numero di elementi dell'insieme.
Quoto fph, combinando i due risultati si trova un'interessante relazione
Re: Insiemi senza elementi consecutivi
Inviato: 31 mag 2015, 21:51
da 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)!}$.
Re: Insiemi senza elementi consecutivi
Inviato: 31 mag 2015, 22:22
da 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 ]
Re: Insiemi senza elementi consecutivi
Inviato: 31 mag 2015, 22:34
da 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$
Re: Insiemi senza elementi consecutivi
Inviato: 31 mag 2015, 22:46
da santilli
Corretto , grazie ^.^ ora diamo un occhiata a Tartaglia , che Fph era abbastanza gasato e voglio scoprire perché xD
Re: Insiemi senza elementi consecutivi
Inviato: 31 mag 2015, 23:20
da 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