Problema di Analisi combinatoria
Salve a tutti!
Vorrei chiedervi aiuto per un problema che mi sta togliendo il sonno (beh.. si fa per dire..
).
Il testo dice:
" In quanti modi di possono assegnare 8 nuovi maestri a 4 scuole? "
Allora, io ho provato a risolverlo in questo modo:
considero 8 maestri e 3 "divisori" che utilizzo per creare le scuole; se ad esempio considero l'ordinamento
$m_1 \ \ \ m_2 \ \ \ m_3 \ \ \ m_4 \ \ \ D \ \ \ m_5 \ \ \ m_6 \ \ \ D \ \ \ m_7 \ \ \ D \ \ \ m_8$
allora assumo che:
alla prima scuola assegno $m_1$ $m_2$ $m_3$ $m_4$
alla seconda scuola assegno $m_5$ $m_6$
alla terza assegno $m_7$
ed infine alla quarta $m_8$.
In tutto gli ordinamenti sarebbero:
$((8+3)!)/(3!)$
Il problema è che in questo modo considero distinti i casi i cui i maestri sono semplicemente in ordine diverso;
ed esempio
$m_1 \ \ \ m_2 \ \ \ m_3 \ \ \ m_4 \ \ \ D \ \ \ m_5 \ \ \ m_6 \ \ \ D \ \ \ m_7 \ \ \ D \ \ \ m_8$
$m_2 \ \ \ m_1 \ \ \ m_3 \ \ \ m_4 \ \ \ D \ \ \ m_5 \ \ \ m_6 \ \ \ D \ \ \ m_7 \ \ \ D \ \ \ m_8$
sono considerati come assegnazioni diverse.
A questo punto del problema mi areno.
Suggerimenti?
Grazie
Vorrei chiedervi aiuto per un problema che mi sta togliendo il sonno (beh.. si fa per dire..
).Il testo dice:
" In quanti modi di possono assegnare 8 nuovi maestri a 4 scuole? "
Allora, io ho provato a risolverlo in questo modo:
considero 8 maestri e 3 "divisori" che utilizzo per creare le scuole; se ad esempio considero l'ordinamento
$m_1 \ \ \ m_2 \ \ \ m_3 \ \ \ m_4 \ \ \ D \ \ \ m_5 \ \ \ m_6 \ \ \ D \ \ \ m_7 \ \ \ D \ \ \ m_8$
allora assumo che:
alla prima scuola assegno $m_1$ $m_2$ $m_3$ $m_4$
alla seconda scuola assegno $m_5$ $m_6$
alla terza assegno $m_7$
ed infine alla quarta $m_8$.
In tutto gli ordinamenti sarebbero:
$((8+3)!)/(3!)$
Il problema è che in questo modo considero distinti i casi i cui i maestri sono semplicemente in ordine diverso;
ed esempio
$m_1 \ \ \ m_2 \ \ \ m_3 \ \ \ m_4 \ \ \ D \ \ \ m_5 \ \ \ m_6 \ \ \ D \ \ \ m_7 \ \ \ D \ \ \ m_8$
$m_2 \ \ \ m_1 \ \ \ m_3 \ \ \ m_4 \ \ \ D \ \ \ m_5 \ \ \ m_6 \ \ \ D \ \ \ m_7 \ \ \ D \ \ \ m_8$
sono considerati come assegnazioni diverse.
A questo punto del problema mi areno.
Suggerimenti?
Grazie
Risposte
i criteri con cui devono essere assegnati devono essere esplicitati. ma in base a quello che ho visto, rompiamo gli indugi: è la risposta che aspetto al quinto quesito di un mio post nella sezione matematica discreta:
quante funzioni suriettive puoi definire da un insieme di 8 elementi a un insieme di 4 elementi?
hai mai sentito parlare di numeri di Stirling di seconda specie?
fammi sapere. ciao.
quante funzioni suriettive puoi definire da un insieme di 8 elementi a un insieme di 4 elementi?
hai mai sentito parlare di numeri di Stirling di seconda specie?
fammi sapere. ciao.
io adesso devo uscire. ti posto la risposta:
$4!*S(8,4)=24*1701=40824$ (se ho calcolato bene 1701):
S(8,4), numero di Stirling di seconda specie, è il numero di partizioni in 4 parti di un insieme di 8 elementi.
esiste la formula ricorsiva (non so se ora ne è stata trovata un'altra non ricorsiva)... anzi, fammi sapere come avete affrontato voi questo tipo di problemi:
S(n, 0)=0
S(n, 1)=S(n, n)=1
S(n+1, k)=S(n, k-1) + k*S(n, k) , 1 < k < n .
è chiaro? ciao.
$4!*S(8,4)=24*1701=40824$ (se ho calcolato bene 1701):
S(8,4), numero di Stirling di seconda specie, è il numero di partizioni in 4 parti di un insieme di 8 elementi.
esiste la formula ricorsiva (non so se ora ne è stata trovata un'altra non ricorsiva)... anzi, fammi sapere come avete affrontato voi questo tipo di problemi:
S(n, 0)=0
S(n, 1)=S(n, n)=1
S(n+1, k)=S(n, k-1) + k*S(n, k) , 1 < k < n .
è chiaro? ciao.
Innanzitutto grazie mille per la risposta.
In secondo luogo... non ho (anzi, avevo) la più pallida idea di cosa siano i numeri di Stirling di seconda specie.
In teoria questo problema si potrebbe risolvere utilizzando i fondamentali concetti di analisi combinatoria (permutazioni, combinazioni...) senza introdurre strumenti più avanzati come quelli da te citati.
Comunque, ora che mi sono noti approfondirò la mia conoscenza in materia, chissà che non trovi la soluzione "standard" (se così si può chiamare).
Grazie!
In secondo luogo... non ho (anzi, avevo) la più pallida idea di cosa siano i numeri di Stirling di seconda specie.
In teoria questo problema si potrebbe risolvere utilizzando i fondamentali concetti di analisi combinatoria (permutazioni, combinazioni...) senza introdurre strumenti più avanzati come quelli da te citati.
Comunque, ora che mi sono noti approfondirò la mia conoscenza in materia, chissà che non trovi la soluzione "standard" (se così si può chiamare).
Grazie!
benvenuto nel forum (prima mi era sfuggito che fossi nuovo).
vedi che il risultato è un numero enorme...
in alternativa potresti pensare a tutti i modi distinti di scrivere 8 come somma di 4 numeri e poi lavorare con fattoriali e coefficienti multinomiali (questi li hai sentiti, sì?). se provi ad impostare il problema in modo alternativo, facci sapere... ciao.
vedi che il risultato è un numero enorme...
in alternativa potresti pensare a tutti i modi distinti di scrivere 8 come somma di 4 numeri e poi lavorare con fattoriali e coefficienti multinomiali (questi li hai sentiti, sì?). se provi ad impostare il problema in modo alternativo, facci sapere... ciao.
Possibili Combianzioni con ripetizione?
nel mio primo intervento chiedevo se doveva esserci un criterio preciso per l'assegnazione dei maestri alle scuole. ho dato quella soluzione pensando che il criterio fosse, basandomi sui tentativi di soluzione, quello di assegnare almeno un maestro a ciascuna scuola. se non è così, ma le assegnazioni possono essere arbitrarie, la soluzione è estremamente semplice: $4^8$. questa formula ti risulta familiare?
supponendo vera la precedente ipotesi, propongo ora la soluzione alternativa (anche se certamente non è la migliore):
il numero 8 si può scrivere in 5 modi come somma di 4 numeri interi positivi:
8=5+1+1+1
8=4+2+1+1
8=3+3+1+1
8=3+2+2+1
8=2+2+2+2
per ciascuno dei cinque casi dobbiamo considerare le partizioni dell'insieme dei maestri in 4 parti di tot elementi quanti sono indicati negli addendi, che dipendono dai coefficienti multinomiali e dal numero di ricorrenze dello stesso addendo nella somma. tutte queste partizioni daranno quello che ho chiamato nell'altro messaggio S(8, 4), e dovrà essere moltiplicato per 4! (perché ciascuno dei gruppi di maestri potrà essere assegnato ad una delle quattro scuole in maniera arbitraria):
dunque la formula finale sarà:
$[(((8), (5" "1" "1" "1)))/(3!)+(((8), (4" "2" "1" "1)))/(2!)+(((8), (3" "3" "1" "1)))/(2!*2!)+(((8), (3" "2" "2" "1)))/(2!)+(((8), (2" "2" "2" "2)))/(4!)]*4! =$
$=[(8!*4!)/(5!*3!)+(8!*4!)/(4!*2!*2!)+(8!*4!)/(3!*3!*2!*2!)+(8!*4!)/(3!*2!*2!*2!)+(8!*4!)/(2!*2!*2!*2!*4!)]=$
$=1344+10080+6720+20160+2520=40824$
risultato che coincide con l'altro, più compatto ma dipendente da una formula ricorsiva.
è chiaro? ciao.
supponendo vera la precedente ipotesi, propongo ora la soluzione alternativa (anche se certamente non è la migliore):
il numero 8 si può scrivere in 5 modi come somma di 4 numeri interi positivi:
8=5+1+1+1
8=4+2+1+1
8=3+3+1+1
8=3+2+2+1
8=2+2+2+2
per ciascuno dei cinque casi dobbiamo considerare le partizioni dell'insieme dei maestri in 4 parti di tot elementi quanti sono indicati negli addendi, che dipendono dai coefficienti multinomiali e dal numero di ricorrenze dello stesso addendo nella somma. tutte queste partizioni daranno quello che ho chiamato nell'altro messaggio S(8, 4), e dovrà essere moltiplicato per 4! (perché ciascuno dei gruppi di maestri potrà essere assegnato ad una delle quattro scuole in maniera arbitraria):
dunque la formula finale sarà:
$[(((8), (5" "1" "1" "1)))/(3!)+(((8), (4" "2" "1" "1)))/(2!)+(((8), (3" "3" "1" "1)))/(2!*2!)+(((8), (3" "2" "2" "1)))/(2!)+(((8), (2" "2" "2" "2)))/(4!)]*4! =$
$=[(8!*4!)/(5!*3!)+(8!*4!)/(4!*2!*2!)+(8!*4!)/(3!*3!*2!*2!)+(8!*4!)/(3!*2!*2!*2!)+(8!*4!)/(2!*2!*2!*2!*4!)]=$
$=1344+10080+6720+20160+2520=40824$
risultato che coincide con l'altro, più compatto ma dipendente da una formula ricorsiva.
è chiaro? ciao.
Adesso mi è tutto chiaro!!
Grazie mille per la disponibilità!
Grazie mille per la disponibilità!
prego. la soluzione che cercavi era quella complessa (funzioni suriettive) oppure quella semplicissima (funzioni arbitrarie)?
Sfortunatamente non conosco la soluzione del problema, quindi non lo sapremo mai...
Ancora grazie!
Ancora grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo