Esercizio di combinatoria (numero di terne tali che...)
Sia $X={1,2,...,n}$
Calcolare il numero di terne ordinate $(A,B,C)$ di sottoinsiemi di $X$ a due a due disgiunti con $A U B U C=X$
Non sono pratico di esercizi di combinatoria, forse non è neanche la sezione giusta.
Gradirei comunque un qualsiasi hint, non una soluzione completa (almeno per ora), perchè al momento brancolo nella penombra piuttosto scura.
Vi dico a grandi linee la mia grossolana idea: chiamo $a=|A|$, $b=|B|$, $c=|C|$. Poichè i tre insiemi devono formare una partizione di $X$, deve essere $a+b+c=n$.
L'insieme $A$ (con $a$ elementi) posso sceglierlo in $((n),(a))$ modi, l'insieme $B$ è un insieme di b elementi scelti fra $n-b$ (devono essere a due a due disgiunti), quindi B lo scelgo in $((n-a),(b))$ modi. Infine l'insieme C posso sceglierlo in $((n-a-b),(c))=((c),(c))=1$ modi. Quindi ho $((n),(a))*((n-a),(b))$ scelte, una volta scelti $a$ e $b$ (e una volta scelti $a$ e $b$ ho che $c$ è univoco). I modo di scegliere una coppia $(a,b)$ sono $n-c+1$, cioè il numero di soluzioni di $a+b=n-c$.
Ma qui mi blocco, probabilmente è un approccio totalmente sbagliato.
Vi ringrazio per l'aiuto che sicuramente mi offrirete.
Calcolare il numero di terne ordinate $(A,B,C)$ di sottoinsiemi di $X$ a due a due disgiunti con $A U B U C=X$
Non sono pratico di esercizi di combinatoria, forse non è neanche la sezione giusta.
Gradirei comunque un qualsiasi hint, non una soluzione completa (almeno per ora), perchè al momento brancolo nella penombra piuttosto scura.
Vi dico a grandi linee la mia grossolana idea: chiamo $a=|A|$, $b=|B|$, $c=|C|$. Poichè i tre insiemi devono formare una partizione di $X$, deve essere $a+b+c=n$.
L'insieme $A$ (con $a$ elementi) posso sceglierlo in $((n),(a))$ modi, l'insieme $B$ è un insieme di b elementi scelti fra $n-b$ (devono essere a due a due disgiunti), quindi B lo scelgo in $((n-a),(b))$ modi. Infine l'insieme C posso sceglierlo in $((n-a-b),(c))=((c),(c))=1$ modi. Quindi ho $((n),(a))*((n-a),(b))$ scelte, una volta scelti $a$ e $b$ (e una volta scelti $a$ e $b$ ho che $c$ è univoco). I modo di scegliere una coppia $(a,b)$ sono $n-c+1$, cioè il numero di soluzioni di $a+b=n-c$.
Ma qui mi blocco, probabilmente è un approccio totalmente sbagliato.
Vi ringrazio per l'aiuto che sicuramente mi offrirete.
Risposte
I numeri di Stirling di seconda specie dovrebbero fare al caso tuo.
La sezione è sbagliata. Ad ogni modo, prova con questa intuizione.
Hai tre urne in fila: A, B, C. Distribuisci gli elementi di X, ordinatamente dal primo all'ultimo, nelle tre urne.
Hai tre urne in fila: A, B, C. Distribuisci gli elementi di X, ordinatamente dal primo all'ultimo, nelle tre urne.
"fields":
La sezione è sbagliata.
Spero di aver rimediato. Se così non fosse chiedo l'intervento di fields, visto che ora ha i poteri.
"Tipper":
I numeri di Stirling di seconda specie dovrebbero fare al caso tuo.
sì, dai un'occhiata anche qui:
https://www.matematicamente.it/forum/pro ... 31673.html
ti sono noti i numeri di Stirling di seconda specie?
facci sapere. ciao.
"adaBTTLS":
i numeri di Stirling di seconda specie
In questo caso i numeri di Stirling non sono appropriati: la partizione di X non è richiesta essere in parti non vuote.
"fields":
[quote="adaBTTLS"]
i numeri di Stirling di seconda specie
In questo caso i numeri di Stirling non sono appropriati: la partizione di X non è richiesta essere in parti non vuote.[/quote]
è vero che le parti possono essere anche vuote? faccelo sapere, perché io e Tipper abbiamo interpretato in tal senso... ciao.
"adaBTTLS":
[quote="fields"][quote="adaBTTLS"]
i numeri di Stirling di seconda specie
In questo caso i numeri di Stirling non sono appropriati: la partizione di X non è richiesta essere in parti non vuote.[/quote]
è vero che le parti possono essere anche vuote? faccelo sapere, perché io e Tipper abbiamo interpretato in tal senso... ciao.[/quote]
alvinlee chiede solo che gli insiemi che partizionano X siano disgiunti a coppie: $AnnB=AnnC=BnnC=\emptyset$
@ fields
alvinlee88 ha parlato di partizioni: se è così, le parti non possono essere vuote.
però l'esercizio non è completo, perché si parla di terne ordinate... se però le terne ordinate sono non degli elementi ma dei sottoinsiemi come alvinlee88 ha scritto, allora il conto è presto fatto...
ciao.
alvinlee88 ha parlato di partizioni: se è così, le parti non possono essere vuote.
però l'esercizio non è completo, perché si parla di terne ordinate... se però le terne ordinate sono non degli elementi ma dei sottoinsiemi come alvinlee88 ha scritto, allora il conto è presto fatto...
ciao.
comunque, se le parti devono essere non vuote, le partizioni sono S(n,3), altrimenti , se possono anche essere vuote, le partizioni sono
S(n,1)+S(n,2)+S(n,3)
quelle ordinate:
nella prima ipotesi S(n,3)*3!
nella seconda ipotesi S(n,1)*3+S(n,2)*3!+S(n,3)*3! (non ho dimenticato un ! ma era solo per non distinguere tra due insiemi vuoti).
quando ho mandato il messaggio precedente, non avevo letto la risposta di fields.
ciao.
S(n,1)+S(n,2)+S(n,3)
quelle ordinate:
nella prima ipotesi S(n,3)*3!
nella seconda ipotesi S(n,1)*3+S(n,2)*3!+S(n,3)*3! (non ho dimenticato un ! ma era solo per non distinguere tra due insiemi vuoti).
quando ho mandato il messaggio precedente, non avevo letto la risposta di fields.
ciao.
"adaBTTLS":
alvinlee88 ha parlato di partizioni: se è così, le parti non possono essere vuote.
alvinlee ha scritto soltanto $AuuBuuC=X$. Chiaramente: $\emptysetuu\emptyset uuX=X$.
stiamo andando troppo velocemente.... nessuno legge i messaggio dell'altro... aspetto un po' per replicare. qual è la definizione di partizione di un insieme?
Io direi di limitarci al testo formale del problema, che ammette un'unica interpretazione:
"alvinlee88":
Sia $X={1,2,...,n}$
Calcolare il numero di terne ordinate $(A,B,C)$ di sottoinsiemi di $X$ a due a due disgiunti con $A U B U C=X$
ed in tal caso una combinazione con tre numeri di stirling ti sembra corretta?
certo che, in tal caso appunto, c'è un modo estremamente più semplice per trovare la soluzione (per questo io avevo suggerito di dare un'occhiata al link del topic a cui avevo appena risposto): io sono ancora convinta che alvinlee88 parlasse di partizioni, ma se non è così, la risposta è semplicemente $3^n$ perché basta immaginare un insieme ordinato come ad esempio Y={1,2,3} e la risposta è semplicemente "il numero delle funzioni da X a Y.
si potrebbe anche fare una verifica, con qualche valore di n però, altrimenti con n generico ed una funzione ricorsiva la vedo brutta...
però è inutile andare avanti senza il "conforto" di alvinlee88.
ciao.
certo che, in tal caso appunto, c'è un modo estremamente più semplice per trovare la soluzione (per questo io avevo suggerito di dare un'occhiata al link del topic a cui avevo appena risposto): io sono ancora convinta che alvinlee88 parlasse di partizioni, ma se non è così, la risposta è semplicemente $3^n$ perché basta immaginare un insieme ordinato come ad esempio Y={1,2,3} e la risposta è semplicemente "il numero delle funzioni da X a Y.
si potrebbe anche fare una verifica, con qualche valore di n però, altrimenti con n generico ed una funzione ricorsiva la vedo brutta...
però è inutile andare avanti senza il "conforto" di alvinlee88.
ciao.
"adaBTTLS":
ed in tal caso una combinazione con tre numeri di stirling ti sembra corretta?
Certo che sì. E, probabilmente, usando la formula per i numeri di Stirling, è possibile anche derivare la formula $3^n$. Naturalmente questo sarebbe un modo abominevole di complicare un problema semplice
quindi secondo te quello che ci si doveva aspettare dal problema era solo questa semplice formuletta? quando si parla di terna ordinata si può anche intendere uno e il vuoto?
($phi$,
, 
), ( 
) ?
($phi$,
, ), ( ) ?
"adaBTTLS":
quindi secondo te quello che ci si doveva aspettare dal problema era solo questa semplice formuletta?
Così chiedeva il problema. E comunque: semplicità=bellezza
"adaBTTLS":
quando si parla di terna ordinata si può anche intendere uno e il vuoto?
Non capisco cosa intendi.
Intanto grazie a tuti, scusate se vi rispndo solo ora.
1) Mi scuso per aver sbagliato sezione
2) Il testo formale è quello riportato da fields, io nella mia "oscura" idea ho parlato di partizioni, ma a sproposito, in quanto dal testo non si evince che gli insiemi debbano essere non vuoti. Quindi non si tratta di partizioni, gli insiemi possono anche essere vuoti.
3) Non conoscevo i numeri di stirling, li ho guardati ora su wikipedia, e su questo documento piuttosto ben fatto
http://www2.dm.unito.it/paginepersonali ... i/bell.pdf
Stavolta però non ci aiutano in quanto non si cercano delle partizioni.
EDIT: in realtà con la formula di adaBTTLS ci aiutano.
Comunque mi piace la soluzione di adaBTTLS, $3^n$, e con un caso particolare anche la sua formula da lo stesso valore. Probabilmente si può dimostrare che sono equivalenti, ma ha ragione fields a dire di non complicarci la vita.
Mi ero fissato che la soluzione fosse il numero di modi di mettere n elementi in 3 scatole, $((n+2),(2))$, ma non è così perchè in questo mod, per esempio CON $n=2$ considero le due terne $A=emptyset$, $B={1}$, $C={2}$ e $A=emptyset$, $B={2}$, $C={1}$ la stessa, mentre in realtà ai fini del problema sono diverse.
Mi sento terribilmente stupido. Devo migliorare molto su questi argomenti. Probabilmente posterò qualche altro esercizio qui.
Grazie ancora una volta a tutti.
1) Mi scuso per aver sbagliato sezione
2) Il testo formale è quello riportato da fields, io nella mia "oscura" idea ho parlato di partizioni, ma a sproposito, in quanto dal testo non si evince che gli insiemi debbano essere non vuoti. Quindi non si tratta di partizioni, gli insiemi possono anche essere vuoti.
3) Non conoscevo i numeri di stirling, li ho guardati ora su wikipedia, e su questo documento piuttosto ben fatto
http://www2.dm.unito.it/paginepersonali ... i/bell.pdf
Stavolta però non ci aiutano in quanto non si cercano delle partizioni.
EDIT: in realtà con la formula di adaBTTLS ci aiutano.
Comunque mi piace la soluzione di adaBTTLS, $3^n$, e con un caso particolare anche la sua formula da lo stesso valore. Probabilmente si può dimostrare che sono equivalenti, ma ha ragione fields a dire di non complicarci la vita.
Mi ero fissato che la soluzione fosse il numero di modi di mettere n elementi in 3 scatole, $((n+2),(2))$, ma non è così perchè in questo mod, per esempio CON $n=2$ considero le due terne $A=emptyset$, $B={1}$, $C={2}$ e $A=emptyset$, $B={2}$, $C={1}$ la stessa, mentre in realtà ai fini del problema sono diverse.
Mi sento terribilmente stupido. Devo migliorare molto su questi argomenti. Probabilmente posterò qualche altro esercizio qui.
Grazie ancora una volta a tutti.
mi spiego meglio. si può parlare anche di "coppie ordinate", la sostanza non cambia.
una coppia ordinata è un elemento del prodotto cartesiano tra due insiemi (che io sappia, non vuoti), e quindi io, pur potendomi immaginare un insieme vuoto di coppie ordinate, non immagino una coppia ordinata con un solo elemento... e quindi anche quando sento parlare di "terne di insiemi" ho qualche perplessità sul fatto che uno o due di questi tre insiemi possa essere vuoto.
in parole povere:
alvinlee88 aveva parlato di terne ordinate, aveva parlato di partizioni, (tra parentesi, io avevo appena risposto ad un'altra persona con i numeri di Stirling di seconda specie facendo però notare che, anche in quel caso, andava specificato il criterio.... perché anche lì la risposta poteva essere questa bella semplice formuletta), Tipper aveva appena citato i numeri di Stirling...
è giusta la tua osservazione di attenersi strettamente al testo, però secondo me il testo non era così chiaro...
ed io "mi sono lasciata condizionare da altre chiacchiere", però ho come la sensazione che non era la soluzione più semplice quella che si cercava.
è chiaro ? ciao.
P.S. [OT]:
ho dato un'occhiata al tuo sito. potresti essere la persona adatta a dare un'opinione sui temi che si stanno dibattendo tra la sezione Congetture e ricerca libera e la sezione Filosofia della scienza. hai visto il topic postato da me nella sezione Congetture e ricerca libera: "logica temporale"? che ne pensi? grazie anticipatamente.
una coppia ordinata è un elemento del prodotto cartesiano tra due insiemi (che io sappia, non vuoti), e quindi io, pur potendomi immaginare un insieme vuoto di coppie ordinate, non immagino una coppia ordinata con un solo elemento... e quindi anche quando sento parlare di "terne di insiemi" ho qualche perplessità sul fatto che uno o due di questi tre insiemi possa essere vuoto.
in parole povere:
alvinlee88 aveva parlato di terne ordinate, aveva parlato di partizioni, (tra parentesi, io avevo appena risposto ad un'altra persona con i numeri di Stirling di seconda specie facendo però notare che, anche in quel caso, andava specificato il criterio.... perché anche lì la risposta poteva essere questa bella semplice formuletta), Tipper aveva appena citato i numeri di Stirling...
è giusta la tua osservazione di attenersi strettamente al testo, però secondo me il testo non era così chiaro...
ed io "mi sono lasciata condizionare da altre chiacchiere", però ho come la sensazione che non era la soluzione più semplice quella che si cercava.
è chiaro ? ciao.
P.S. [OT]:
ho dato un'occhiata al tuo sito. potresti essere la persona adatta a dare un'opinione sui temi che si stanno dibattendo tra la sezione Congetture e ricerca libera e la sezione Filosofia della scienza. hai visto il topic postato da me nella sezione Congetture e ricerca libera: "logica temporale"? che ne pensi? grazie anticipatamente.
@ alvinlee88
perché non dai un'occhiata al mio post, in questa sezione: "funzioni tra insiemi finiti" ? ed anche alle soluzioni di jacopo. manca il quinto caso ed è qui che entrano in ballo i numeri di Stirling.
ciao.
P.S. ovviamente il messaggio precedente era rivolto a fields.
perché non dai un'occhiata al mio post, in questa sezione: "funzioni tra insiemi finiti" ? ed anche alle soluzioni di jacopo. manca il quinto caso ed è qui che entrano in ballo i numeri di Stirling.
ciao.
P.S. ovviamente il messaggio precedente era rivolto a fields.
"adaBTTLS":
mi spiego meglio. si può parlare anche di "coppie ordinate", la sostanza non cambia.
una coppia ordinata è un elemento del prodotto cartesiano tra due insiemi (che io sappia, non vuoti), e quindi io, pur potendomi immaginare un insieme vuoto di coppie ordinate, non immagino una coppia ordinata con un solo elemento... e quindi anche quando sento parlare di "terne di insiemi" ho qualche perplessità sul fatto che uno o due di questi tre insiemi possa essere vuoto.
Formalizziamo, per dileguare ogni dubbio.
Una tripla ordinata di sottinsiemi di un insieme $X$ è un elemento di $\mathcal{P}(X)\times \mathcal{P}(X)\times \mathcal{P}(X)$. Poiche' $\emptyset \in \mathcal P(X)$, certamente $(\emptyset,\emptyset,\emptyset)\in \mathcal{P}(X)\times \mathcal{P}(X)\times \mathcal{P}(X)$.
ps: ora rispondo al tuo topic nella sezione "congetture e ricerca libera". Per quanto riguarda la filosofia, grazie per l'invito, ma quel che posso risponderti è: "Grazie, ma non pratico"
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo