Pagina 1 di 1

Inviato: 01 gen 1970, 01:33
da Catraga
Un bel problemino di combinatoria...
<BR>
<BR>Dati due interi n e k, quanti sono i sottoinsiemi di k elementi dell\'insieme {1,...,n} che non contengono due elementi consecutivi?
<BR>

Inviato: 01 gen 1970, 01:33
da cekko
direi
<BR>(n,k) - sum(i=2->k)[(-1)^i * 2(n-i-1,k-1) + (n-i-1)(n-i-2,k-1)]
<BR>sottraggo gli insiemi con esattamente 2 elementi consecutivi, poi sommo quelli con 3, .... fino a k con il principio inclusione-esclusione.
<BR>la spezzatura è dovuta al fatto che se ho i primi o gli ultimi m termini posso scegliere i restanti k-m tra n-m-1. se invece il \"blocco\" è nel mezzo allora posso scegliere tra n-m-2.

Inviato: 01 gen 1970, 01:33
da Catraga
Secondo me basta un solo coefficiente binomiale...

Inviato: 01 gen 1970, 01:33
da Marco
..ma certo che ne basta uno!!
<BR>
<BR>Ovvìa, contate le sequenze: quelle nuove con n+1 non possono contentere n. Quelle vecchie vanno tutte bene. Scrivete la formula ricorsiva. Fatevi i casi piccoli, congetturate la formula finale e fate la dimostrazioncina per induzione.
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>[addsig]

Inviato: 01 gen 1970, 01:33
da MindFlyer
Io penso che sia (n-k+1,k), infatti equivale a scegliere k+1 interi positivi aventi somma n-k.
<BR>
<BR>EDIT: Sì, insomma, quello che è. Avete capito...<BR><BR>[ Questo Messaggio è stato Modificato da: MindFlyer il 09-09-2004 09:51 ]

Inviato: 01 gen 1970, 01:33
da MindFlyer
Ecco, sì: scegliamo il primo elemento, e lo rappresentiamo con un intero positivo corrispondente alla sua \"posizione\". Poi, dobbiamo scegliere k-1 interi positivi che rappresentano gli spazi tra i k elementi. In totale, è come scegliere k interi positivi aventi somma n-k+1, ovvero proprio (n-k+1,k).

Inviato: 01 gen 1970, 01:33
da Shoma85
Ma (n-k+1,k) non equivale a scegliere k+1 interi che abbiano somma
<BR>n-2k+1 ?<BR><BR>[ Questo Messaggio è stato Modificato da: Shoma85 il 09-09-2004 10:17 ]

Inviato: 01 gen 1970, 01:33
da MindFlyer
Solo se (n-k+1,k) = (n-2k+1,k+1). Quindi no. Pensaci un attimo... Comunque i miei sono interi positivi.

Inviato: 01 gen 1970, 01:33
da cekko
toh! non avevo pensato a come dice mindflyer.
<BR>ma la mi va bene?

Inviato: 01 gen 1970, 01:33
da Marco
Allora, dato che ci sono tante idee, ma le soluzioni complete latitano, cerco di scriverne una io.
<BR>
<BR>
<BR>Dati due interi n e k, quanti sono i sottoinsiemi di k elementi dell\'insieme {1,...,n} che non contengono due elementi consecutivi?
<BR>
<BR>
<BR> EDIT: Aaaargh! perché non funzionano i tags QUOTE? Ho usato
<BR> quelli dell\'icona predisposta...
<BR>
<BR>Claim: dico che il numero cercato è { n - k + 1 } \\choose k, con la convenzione usuale che a \\choose b vale 0 se b è negativo o a < b.
<BR>
<BR>Dimostro il claim per induzione su n.
<BR>
<BR>Per n = 0, 1 il claim è vero. Infatti nei casi n=k=0; n=1, k=0; n=k=; l\'unico sottoinsieme che, nei tre casi, soddisfa le ipotesi è, rispettivamente, \\empty; \\empty; {1}.
<BR>
<BR>Sia ora n>1 e suppondo il claim vero per n-1 e n-2. Contiamo gli insiemi che soddisfano l\'ipotesi suddividendo gli insiemi che non contengono l\'elemento n e quelli che lo contengono.
<BR>
<BR>I primi, sono esattamente i sottoinsiemi di k elementi di {1, ..., n-1} che soddisfano le ipotesi e quindi, per ipotesi induttiva, sono { n - k } \\choose k.
<BR>
<BR>I secondi, sono in corrispondenza biunivoca con i sottoinsiemi di k-1 elementi di {1, ..., n-2}, dove la corrispondenza è data dall\'aggiunta dell\'elemento n. Quindi, per ipotesi induttiva, sono { n - k } \\choose { k - 1 }.
<BR>
<BR>Ma allora, il numero cercato vale { n - k } \\choose k + { n - k } \\choose { k - 1 } = { n - k + 1 } \\choose k.
<BR>
<BR>Questo dimostra il claim.
<BR>
<BR>------
<BR>
<BR>Ho scritto questo messaggio non è tanto per dare nuove idee o rubare idee di altri; tuttavia, per fare bene le gare olimat, occorre anche sapere scrivere BENE una dimostrazione. A volte, vedere una dimostrazione scritta bene (o, meglio ancora, cercare di scriverne una), può insegnare qualcosa.
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>-------
<BR>
<BR>\"Well, master, we\'re in a fix and no mistake.\"
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: marco il 15-09-2004 10:54 ]