Insiemi senza elementi consecutivi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Insiemi senza elementi consecutivi

Messaggio da 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$.
Ultima modifica di jordan il 18 apr 2015, 13:43, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Insiemi senza elementi consecutivi

Messaggio da <enigma> »

jordan ha scritto:se $x \in S$ allora $x \notin S$.
In che modello dell'aritmetica? :mrgreen:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Insiemi senza elementi consecutivi

Messaggio da jordan »

E' il terzo di fila, wow :O
The only goal of science is the honor of the human spirit.
santilli
Messaggi: 24
Iscritto il: 30 set 2014, 20:59
Località: Rovigo

Re: Insiemi senza elementi consecutivi

Messaggio 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 ^.^
16 esimi GAS '2016 :D finalmenteeeee! #RovigoPower xD
AGallese
Messaggi: 19
Iscritto il: 02 dic 2013, 19:57

Re: Insiemi senza elementi consecutivi

Messaggio da AGallese »

Che ne dici di provare una successione?? :D
Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: Insiemi senza elementi consecutivi

Messaggio da luca95 »

Testo nascosto:
Sempre tra i piedi 'sto Fibonacci :lol:
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 $
Ultima modifica di luca95 il 29 mag 2015, 11:07, modificato 1 volta in totale.
Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: Insiemi senza elementi consecutivi

Messaggio 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 $.
Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: Insiemi senza elementi consecutivi

Messaggio da Enigmatico »

Cardinalità: numero di elementi dell'insieme?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Insiemi senza elementi consecutivi

Messaggio 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).
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: Insiemi senza elementi consecutivi

Messaggio da luca95 »

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

Quoto fph, combinando i due risultati si trova un'interessante relazione :D
Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: Insiemi senza elementi consecutivi

Messaggio da Enigmatico »

Tento una soluzione 8)

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
Messaggi: 24
Iscritto il: 30 set 2014, 20:59
Località: Rovigo

Re: Insiemi senza elementi consecutivi

Messaggio 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 ;)]
Ultima modifica di santilli il 31 mag 2015, 22:44, modificato 1 volta in totale.
16 esimi GAS '2016 :D finalmenteeeee! #RovigoPower xD
Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: Insiemi senza elementi consecutivi

Messaggio 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 :wink:

EDIT: scusa, così pare alquanto falsa...
Meglio dire che $1 \leq k \leq n/2$
santilli
Messaggi: 24
Iscritto il: 30 set 2014, 20:59
Località: Rovigo

Re: Insiemi senza elementi consecutivi

Messaggio da santilli »

Corretto , grazie ^.^ ora diamo un occhiata a Tartaglia , che Fph era abbastanza gasato e voglio scoprire perché xD
16 esimi GAS '2016 :D finalmenteeeee! #RovigoPower xD
santilli
Messaggi: 24
Iscritto il: 30 set 2014, 20:59
Località: Rovigo

Re: Insiemi senza elementi consecutivi

Messaggio 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

EDIT : Come non detto xD funziona solo fino a 5-6 :?
16 esimi GAS '2016 :D finalmenteeeee! #RovigoPower xD
Rispondi