Combinatoria

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio 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>
Aladin to the genius: "Oh, great spirit! My desire is that you do not fullfill my desire"
The genius was enlightened.
cekko
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio 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.
"...e d'un tratto capii che il pensare è per gli stupidi, mentre i cervelluti si affidano all'ispirazione e a quello che il buon Bog manda loro".
Alex, Arancia Meccanica.
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga »

Secondo me basta un solo coefficiente binomiale...
Aladin to the genius: "Oh, great spirit! My desire is that you do not fullfill my desire"
The genius was enlightened.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio 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]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
MindFlyer

Messaggio 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 ]
MindFlyer

Messaggio 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).
Shoma85
Messaggi: 98
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio 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 ]
<img src="http://dsomensi.altervista.org/immagini/im.gif">
MindFlyer

Messaggio da MindFlyer »

Solo se (n-k+1,k) = (n-2k+1,k+1). Quindi no. Pensaci un attimo... Comunque i miei sono interi positivi.
cekko
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da cekko »

toh! non avevo pensato a come dice mindflyer.
<BR>ma la mi va bene?
"...e d'un tratto capii che il pensare è per gli stupidi, mentre i cervelluti si affidano all'ispirazione e a quello che il buon Bog manda loro".
Alex, Arancia Meccanica.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio 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 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Bloccato