COMBINAZIONI CON RIPETIZIONE
COMBINAZIONI CON RIPETIZIONE
Determinare il numero di combinazioni possibili, in cui non conta l'ordine degli elementi e un elemento può anche essere ripetuto, di n oggetti distinti in k posti distinti.
Prova a definirlo per ricorsione:
- cosa succede se aggiungo un oggetto ma con gli stessi posti?
- cosa succede se aggiungo un posto con gli stessi oggetti
Poi trova i valore per (1,1) o comunque n e k molto piccoli
E quindi prova a fare una tabella: a cosa assomiglia?
come puoi trasformare tutto in un binomiale?
- cosa succede se aggiungo un oggetto ma con gli stessi posti?
- cosa succede se aggiungo un posto con gli stessi oggetti
Poi trova i valore per (1,1) o comunque n e k molto piccoli
E quindi prova a fare una tabella: a cosa assomiglia?
come puoi trasformare tutto in un binomiale?
Soluzione puramente combinatoria, senza induzione, che insegna un truccaccio utile:
Sia $ a_0, a_1, a_{k-1} $ un possibile insieme di elementi (eventualmente ripetuti, pescati in $ A = \{1, 2, \dots, n\} $. Dato che non conta l'ordine, supponiamo che gli indici siano messi in modo (largamente) crescente, ossia che
$ a_0 \leqslant a_1 \leqslant \cdots \leqslant a_{k-1} $
Adesso trasformiamo gli $ a_i $ nel modo seguente:
$ b_i = a_i + i $
Non è difficile verificare che i $ b_i $ sono interi in ordine strettamente crescente, sono compresi tra 1 e n+k-1 (inclusi) e che sono in corrispondenza biunivoca con gli insiemi con ripetizione iniziali.
Ne segue che i possibili $ \{a_i\} $ sono tanti quanti i $ \{b_i\} $, che sono tutti i possibili sottinsiemi senza ripetizioni di k elementi pescati in n+k-1 possibili, che si sa essere il binomiale voluto.
Sia $ a_0, a_1, a_{k-1} $ un possibile insieme di elementi (eventualmente ripetuti, pescati in $ A = \{1, 2, \dots, n\} $. Dato che non conta l'ordine, supponiamo che gli indici siano messi in modo (largamente) crescente, ossia che
$ a_0 \leqslant a_1 \leqslant \cdots \leqslant a_{k-1} $
Adesso trasformiamo gli $ a_i $ nel modo seguente:
$ b_i = a_i + i $
Non è difficile verificare che i $ b_i $ sono interi in ordine strettamente crescente, sono compresi tra 1 e n+k-1 (inclusi) e che sono in corrispondenza biunivoca con gli insiemi con ripetizione iniziali.
Ne segue che i possibili $ \{a_i\} $ sono tanti quanti i $ \{b_i\} $, che sono tutti i possibili sottinsiemi senza ripetizioni di k elementi pescati in n+k-1 possibili, che si sa essere il binomiale voluto.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
MindFlyer
Io l'avevo pensato in un altro modo, sempre combinatorio e sempre con truccaccio, ma che secondo me si visualizza meglio.
In sostanza comunque è lo stesso metodo di Marco...
Immaginiamo che gli elementi tra cui scegliere siano A, B, C, etc, e consideriamo tutte le stringhe del tipo:
AAA#BB#CCCC#D##FFF#GG...
dove i "#" sono dei separatori.
Contare le stringhe che ci interessano è facile, perché ogni stringa deve contenere esattamente k elementi scelti tra A, B, C, etc, più n-1 separatori.
Quindi queste stringhe sono esattamente tante quante i modi di scegliere gli n-1 separatori tra gli n+k-1 caratteri totali della stringa, ovvero il coefficiente binomiale voluto.
In sostanza comunque è lo stesso metodo di Marco...
Immaginiamo che gli elementi tra cui scegliere siano A, B, C, etc, e consideriamo tutte le stringhe del tipo:
AAA#BB#CCCC#D##FFF#GG...
dove i "#" sono dei separatori.
Contare le stringhe che ci interessano è facile, perché ogni stringa deve contenere esattamente k elementi scelti tra A, B, C, etc, più n-1 separatori.
Quindi queste stringhe sono esattamente tante quante i modi di scegliere gli n-1 separatori tra gli n+k-1 caratteri totali della stringa, ovvero il coefficiente binomiale voluto.
Bellissimo!
Mi ricorda il trucco "delle carte" che ci ha spiegato un simpatico tizio a Trieste per risolvere il problema:
Quante sono le n-uple di numeri naturali tali che $ a_1+...+a_n=k $?
Immaginiamo di avere un mazzo con k carte, oltre a queste ci aggiungo (n-1) 'jolly'.
(immaginatevi il signore che tira fuori di tasca le carte da briscola e inizia a spiegare
)
Poi mescolo il tutto e, a seconda della posizione dei jolly ho diviso il mazzo in n mucchietti, anche di zero carte.
Quindi le terne cercate sono equivalenti a tutti i modi di disporre (n-1) jolly in un mazzo di k carte.
Per calcolare questo la penso in questo modo:
- il primo jolly lo posso mettere in k+1 posizioni (prima della 1° carta, ... , prima della n° carta, dopo la n° carta
- il secondo jolly lo posso mettere in k+2 posizioni: oltre a quelle dette prima, lo posso mettere sia prima che dopo il primo jolly
- il h-esimo jolly lo posso mettere in k+h posizioni...
Calcolando tutte queste possibilità, ora basta che trascuro l'ordine, e lo faccio dividendo per (n-1)!.
Alla fine la soluzione del problema è quindi:
$ \frac{(k+1) \cdot \ (k+2) \hdots (k+n-1)} {(n-1)!} = \frac{(k+n-1)!} {(k!)(n-1)!} $
Alla fine abbiamo trovato lo stesso coefficiente binomiale, infatti i problemi corrispondono: i numeri $ a_1,a_2,...,a_n $ corrispondono rispettivamente alla quantità del primo, secondo, ..., n-esimo oggetto.
Anche questo problema probabilmente si poteva ricondurre direttamente a un coefficiente binomiale con l'interessante metodo delle stringhe di MindFlyer
(e scusate se per sbaglio ho scritto cavolate)
Mi ricorda il trucco "delle carte" che ci ha spiegato un simpatico tizio a Trieste per risolvere il problema:
Quante sono le n-uple di numeri naturali tali che $ a_1+...+a_n=k $?
Immaginiamo di avere un mazzo con k carte, oltre a queste ci aggiungo (n-1) 'jolly'.
(immaginatevi il signore che tira fuori di tasca le carte da briscola e inizia a spiegare
)Poi mescolo il tutto e, a seconda della posizione dei jolly ho diviso il mazzo in n mucchietti, anche di zero carte.
Quindi le terne cercate sono equivalenti a tutti i modi di disporre (n-1) jolly in un mazzo di k carte.
Per calcolare questo la penso in questo modo:
- il primo jolly lo posso mettere in k+1 posizioni (prima della 1° carta, ... , prima della n° carta, dopo la n° carta
- il secondo jolly lo posso mettere in k+2 posizioni: oltre a quelle dette prima, lo posso mettere sia prima che dopo il primo jolly
- il h-esimo jolly lo posso mettere in k+h posizioni...
Calcolando tutte queste possibilità, ora basta che trascuro l'ordine, e lo faccio dividendo per (n-1)!.
Alla fine la soluzione del problema è quindi:
$ \frac{(k+1) \cdot \ (k+2) \hdots (k+n-1)} {(n-1)!} = \frac{(k+n-1)!} {(k!)(n-1)!} $
Alla fine abbiamo trovato lo stesso coefficiente binomiale, infatti i problemi corrispondono: i numeri $ a_1,a_2,...,a_n $ corrispondono rispettivamente alla quantità del primo, secondo, ..., n-esimo oggetto.
Anche questo problema probabilmente si poteva ricondurre direttamente a un coefficiente binomiale con l'interessante metodo delle stringhe di MindFlyer
(e scusate se per sbaglio ho scritto cavolate)
sqrt2 ha scritto: p.s. comunque la risposta è il binomiale di (n+k-1) su k.
Meglio che riscrivo la formula così non rischio di confondermi la prossima volta che leggo la discussione.Quindi queste stringhe sono esattamente tante quante i modi di scegliere gli n-1 separatori tra gli n+k-1 caratteri totali della stringa, ovvero il coefficiente binomiale voluto.
Se indichiamo con n la lunghezza di ogni gruppo di elementi e con k il numero di elementi tra cui possiamo scegliere, il binomiale è:
$ \displaystyle \binom {n+k-1}{k-1} $