Esercizi di combinatoria
Ciao a tutti!! 
In primis complimenti per il forum! veramente utile!
In secondo ho trovato difficoltà in diversi esercizi di combinatoria :
1)Sia dia il numero delle possibili reazioni che coinvolgono (come reattanti o come prodotti) esattamente quattro sostanze A,B,C,D
Penso che la risposta a questo problema sia $ 4! $, ma non ne sono minimamente convinto
2)Si dia il formula che esprime il numero di tutte le stringhe su {a,b} di lunghezza 2n in cui a occorre al più volte ed è sempre seguita da b
cercando in rete credo di aver trovato una correlazione tra ho questo problema e il numero dei cammini in una griglia $ n xx n $ che collegano due vertici opposti senza mai attraversare la diagonale il che mi porta a pensare che la risposta sia il numero di Catalan $ 1/(n+1)( (2n), (n) ) $
3)Si dia il numero di tutte le stringhe su {a,b} che prescindendo dall'ordine dei loro simboli determinano il multinsime $ 7a+5b $
questo problema mi sembra rinconducibile al numero di anagrammi di una parola quindi $ (n!)/(na!*nb!) = (12!)/(7!*5!) $
4)Si diano le formule che calcolano il numero di sequenze di DNA di lunghezza 10 e di lunghezza 11 in cui compaiono lo stesso numero di purine e piramidine
purine:A,G
piramidine:C,T
Riguardo questo problema non so proprio come procedere
In primis complimenti per il forum! veramente utile! In secondo ho trovato difficoltà in diversi esercizi di combinatoria :
1)Sia dia il numero delle possibili reazioni che coinvolgono (come reattanti o come prodotti) esattamente quattro sostanze A,B,C,D
Penso che la risposta a questo problema sia $ 4! $, ma non ne sono minimamente convinto
2)Si dia il formula che esprime il numero di tutte le stringhe su {a,b} di lunghezza 2n in cui a occorre al più volte ed è sempre seguita da b
cercando in rete credo di aver trovato una correlazione tra ho questo problema e il numero dei cammini in una griglia $ n xx n $ che collegano due vertici opposti senza mai attraversare la diagonale il che mi porta a pensare che la risposta sia il numero di Catalan $ 1/(n+1)( (2n), (n) ) $
3)Si dia il numero di tutte le stringhe su {a,b} che prescindendo dall'ordine dei loro simboli determinano il multinsime $ 7a+5b $
questo problema mi sembra rinconducibile al numero di anagrammi di una parola quindi $ (n!)/(na!*nb!) = (12!)/(7!*5!) $
4)Si diano le formule che calcolano il numero di sequenze di DNA di lunghezza 10 e di lunghezza 11 in cui compaiono lo stesso numero di purine e piramidine
purine:A,G
piramidine:C,T
Riguardo questo problema non so proprio come procedere
Risposte
a) In una reazione chimica il buon senso dice che ci deve essere almeno 1 reagente o almeno un prodotto, cioè reazioni del tipo A+B+C->D oppure A->B+C+D, mentre non si capisce che senso ha A+B+C+D -> .
Quindi direi che il tutto si riconduce a contare la somma dei binomiali da 1 a 3, ossia
$\sum_(k=1)^3 ((4),(k):})$
NB: chimicamente non hanno senso queste formule, è un puro esercizio di combinatoria.
b) Tanto per capirci, scriviamo tutte le combinazioni con n=2.
BBBB
ABBB
BABB
BBAB
ABAB
Sono 5.
Il problema può essere visto così: immaginiamo che ogni A sia una divisoria che separa un numero di palline, le B.
Allora, quando nella stringa c'è ad es. una sola A, la A divide le B in due gruppi, due variabili, tali che il numero delle B sia fisso. Ossia date due variabili il problema è simile a quello di dire in quanti modi $x_1+x_2=3$, tali che le variabili sono strettamente positive e intere. La differenza è però che a sinistra della prima A, la variabile può anche essere 0.
Ora, i modi di $x_1+x_2+...+x_r=n, x_1 \in N^+$ sono $((n-1),(r-1):})$. Siccome però noi abbiamo che le variabil sono una in più del numero di A e una variabile può essere 0, la nostra risposta è
$((2n-k),(k):})$,
dove $2n$ è il numero di lettere e $k$ è il numero di A.
I modi totali sono $\sum_(k=0)^n ((2n-k),(k):})$.
3) Qui non ci metto becco siccome i multiinsiemi non li ho mai visti. Anche se leggendo qui http://it.wikipedia.org/wiki/Multiinsieme una risposta la si può intuire.
4) L'enunciato non mi sembra chiaro al 100%, comunque...
Immaginiamo di avere PU purine e PI piramidine. I modi diversi di disporre i $PU+PI$ "oggetti" sono $((PU+PI),(PU):})$.
Poi, siccome ho 2 tipi diversi di purine (e di piramidine), i modi diversi di disporre PU purine sono $2^(PU)$. Un discorso simile si può fare per le piramidine.
Ora si tratta di "contare" tutti questi modi.
Dovrebbe apparire chiaro che sono
$((PU+PI),(PU):}) 2^(PU+PI)$
Quindi direi che il tutto si riconduce a contare la somma dei binomiali da 1 a 3, ossia
$\sum_(k=1)^3 ((4),(k):})$
NB: chimicamente non hanno senso queste formule, è un puro esercizio di combinatoria.
b) Tanto per capirci, scriviamo tutte le combinazioni con n=2.
BBBB
ABBB
BABB
BBAB
ABAB
Sono 5.
Il problema può essere visto così: immaginiamo che ogni A sia una divisoria che separa un numero di palline, le B.
Allora, quando nella stringa c'è ad es. una sola A, la A divide le B in due gruppi, due variabili, tali che il numero delle B sia fisso. Ossia date due variabili il problema è simile a quello di dire in quanti modi $x_1+x_2=3$, tali che le variabili sono strettamente positive e intere. La differenza è però che a sinistra della prima A, la variabile può anche essere 0.
Ora, i modi di $x_1+x_2+...+x_r=n, x_1 \in N^+$ sono $((n-1),(r-1):})$. Siccome però noi abbiamo che le variabil sono una in più del numero di A e una variabile può essere 0, la nostra risposta è
$((2n-k),(k):})$,
dove $2n$ è il numero di lettere e $k$ è il numero di A.
I modi totali sono $\sum_(k=0)^n ((2n-k),(k):})$.
3) Qui non ci metto becco siccome i multiinsiemi non li ho mai visti. Anche se leggendo qui http://it.wikipedia.org/wiki/Multiinsieme una risposta la si può intuire.
4) L'enunciato non mi sembra chiaro al 100%, comunque...
Immaginiamo di avere PU purine e PI piramidine. I modi diversi di disporre i $PU+PI$ "oggetti" sono $((PU+PI),(PU):})$.
Poi, siccome ho 2 tipi diversi di purine (e di piramidine), i modi diversi di disporre PU purine sono $2^(PU)$. Un discorso simile si può fare per le piramidine.
Ora si tratta di "contare" tutti questi modi.
Dovrebbe apparire chiaro che sono
$((PU+PI),(PU):}) 2^(PU+PI)$
Grazie mille per la risposta!
I primi due li ho capiti, invece ho un po' di problemi con il quarto: non riesco a capire come arrivi a dire che i modi diversi per disporre $ PU+PI $ è $ ( (PU+PI), (PU) ) $, sono un po' duro, se riesci a tagliarmela giù un altro po'
I primi due li ho capiti, invece ho un po' di problemi con il quarto: non riesco a capire come arrivi a dire che i modi diversi per disporre $ PU+PI $ è $ ( (PU+PI), (PU) ) $, sono un po' duro, se riesci a tagliarmela giù un altro po'
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo