Giusto un po\' di combinatorica

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

<!-- BBCode Start --><B>Problema i)</B><!-- BBCode End -->: siano n un intero positivo, A e B due insiemi finiti di n elementi. Determinare il numero di tutte le possibili funzioni biunivoche di A in B.
<BR>
<BR><!-- BBCode Start --><B>NOTA</B><!-- BBCode End -->: essendo S un <!-- BBCode Start --><I>qualsivoglia</I><!-- BBCode End --> insieme... non vuoto, sarà detta <!-- BBCode Start --><B>partizione</B><!-- BBCode End --> di S ogni famiglia di sottoinsiemi non vuoti di S a due a due disgiunti la cui unione sia giust\'appunto eguale ad S. I sottoinsiemi di S che ne determinano una partizione sono chiamati i <!-- BBCode Start --><I>blocchi della partizione</I><!-- BBCode End -->. Ciò premesso...
<BR>
<BR><!-- BBCode Start --><B>Problema ii)</B><!-- BBCode End -->: diciamo {S(n, k)} la successione numerica a valori naturali definita ponendo ricorsivamente, per ogni n, k€N<sub>0</sub>:
<BR>
<BR><center>S(n+1, k) := S(n, k-1) + k*S(n, k), se 2 ≤ k ≤ n;</center>
<BR>
<BR>con l\'ulteriore assunzione che: S(n, 1) = S(n, n) := 1 ed S(n, k) := 0, se k > n. I termini della successione {S(n, k)} così introdotta sono detti i numeri di Stirling di II specie di indici n e k.
<BR>Dimostrare che, comunque considerati un intero positivo n ed un insieme A finito di n elementi, il numero delle partizioni di A in blocchi di ordine k è pari esattamente ad S(n, k), per ogni k€N<sub>0</sub>.
<BR>
<BR><!-- BBCode Start --><B>Problema iii)</B><!-- BBCode End -->: essendo n un intero positivo, determinare il numero B(n) di tutte le possibili partizioni di un insieme finito di n elementi. Tanto per la cronaca... la sequenza numerica dei B(n) ottenuta per questa via è detta classicamente la successione dei numeri di Bell.
<BR>
<BR>EDIT: ooops!!! <IMG SRC="images/forum/icons/icon_razz.gif"><BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 10-02-2004 13:48 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

Per il problema 1, si possono formare n! funzioni biunivoche, infatti il 1° elemento dell\'insieme a può essere associato a n elementi dell\'insieme B, il 2° di A a n-1 diB, e così via quindi io posso avere n! funzioni biunivoche, sicuramente non è giusto perchè sarebbe un problema postato da euler troppo facile quindi aspetto vostre correzioni....
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-02-09 21:17, psion_metacreativo wrote:
<BR>Per il problema 1, si possono formare n! funzioni biunivoche, infatti il 1° elemento dell\'insieme a può essere associato a n elementi dell\'insieme B, il 2° di A a n-1 diB, e così via quindi io posso avere n! funzioni biunivoche, <!-- BBCode Start --><B>sicuramente non è giusto perchè sarebbe un problema postato da euler troppo facile quindi aspetto vostre correzioni</B><!-- BBCode End -->...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Psion, te sei un caro ragazzo, ma mi sopravvaluti un tantino... <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>La tua risposta è corretta! E il problema è banale, sì come tu dici! Ma d\'altra parte, i giovanissimi dovranno pur formarsi le ossa da qualche parte, non credi? Penso ad esempio a quei piccinini del 1987 (affettuosamente parlando) che han deciso di censirsi per far sentire la loro voce in questa babele di problemi simìl universitari e d\'universitari verosimilmente pieni di problemi... <IMG SRC="images/forum/icons/icon_razz.gif"><BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 10-02-2004 13:49 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

che differenza cìè tra i due S segnati qui sotto?
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>
<BR><!-- BBCode Start --><B>S<sub>n(k-1)</sub></B><!-- BBCode End --> + k*<!-- BBCode Start --><B>S(n, k)</B><!-- BBCode End -->
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>cioè come mai in uno n e k sono pedici, mentre nell\'altro sembrano avere un altro significato?
Avatar utente
massiminozippy
Messaggi: 736
Iscritto il: 01 gen 1970, 01:00

Messaggio da massiminozippy »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-02-09 21:56, euler_25 wrote:
<BR> e d\'universitari pieni di problemi... <IMG SRC="images/forum/icons/icon_razz.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ben detto!!
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

si ma il mio dubbio chi me lo chiarisce?
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

Psion, è semplicemente che ho fatto un po\' di casini di battitura! Rimedio subito, comunque... <IMG SRC="images/forum/icons/icon_razz.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

anch\'io avevo capito che era un problema di battitura ma con i tuoi problemi non si può mai dire... <IMG SRC="images/forum/icons/icon_biggrin.gif">
J4Ck202
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da J4Ck202 »

iii) Se passi alle funzioni generatrici dovresti avere
<BR>che Bell(n) e\' il coefficiente di x^n nello sviluppo di
<BR>taylor di e^(e^x) attorno allo 0. Stasera faccio i conti
<BR>e se non ho detto boiate completo la dimostrazione.
<BR>
<BR>
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

ii)
<BR>
<BR>east side-west side <IMG SRC="images/forum/icons/icon_biggrin.gif">
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

talpuz esattamente cosa intendi?
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

è il titolo di un libro di un certo Herbert Wilf
<BR>che parla di combinatoria
<BR>
<BR>in particolare di problemi di \"conteggio\" tipo quello posto da Euler (partizioni di un\'insieme, partizioni di un\'intero, coefficienti binomiali, ecc)
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

Come come? E la gente ci avrebbe pure il coraggio di scrivere libri su queste robette...? E peggio ancora... ce n\'è dell\'altra che si spinge persino ad acquistarli? Beh, come sono cambiati i tempi... <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>Salvo
<BR>
<BR>P.S.: ovviamente sto cazzeggiando, mio buon Talpuz. <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>P.P.S.: comunque, leva quegli apostrofi lì... passi per uno, ma due in uno stesso rigo è davvero troppo, non credi anche tu? <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>@Jack: c\'è un modo mooolto più semplice di risolvere il problema, senza bisogno di tirare in ballo funzioni generatrici e quant\'altro, anche se personalmente trovo la via che hai imboccato te decisamente più gagliarda!!! <IMG SRC="images/forum/icons/icon_biggrin.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

<!-- BBCode Start --><B>Problema iv)</B><!-- BBCode End -->: dati che siano due qualsivoglia insiemi X ed Y finiti, rispettivamente dotati di m ed n elementi, con min{m, n} > 0, determinare:
<BR>a) il numero di tutte le possibili funzioni di X in Y;
<BR>b) il numero di tutte le possibili iniezioni di X in Y;
<BR>c) il numero di tutte le possibili funzioni f(-): X --> Y che siano dotate <!-- BBCode Start --><I>esattamente</I><!-- BBCode End --> di un unico punto fisso in X, ossia per le quali esista (univocamente determinato) un x€X tal che f(x) = x, ammettendo che sia X un sottoinsieme (proprio o improprio) di Y.
<BR>d) il numero di tutte le possibili funzioni f(-): X --> Y che siano dotate <!-- BBCode Start --><I>esattemente</I><!-- BBCode End --> di k punti fissi in X, con 1 ≤ k ≤ n, assunto che sia X un sottoinsieme (proprio o improprio) di Y.
<BR>
<BR>EDIT: ho semplicemente aggiunto il problema d) come generalizzazione del precedente problema c). Mi sembrava carino e siccome ho appena finito di risolverlo, non ho saputo resistire alla tentazione di proporvelo... ghghgh!!! <IMG SRC="images/forum/icons/icon_razz.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 11-02-2004 18:57 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
oscar
Messaggi: 99
Iscritto il: 01 gen 1970, 01:00
Località: Ciriè Ciriè Eleyson

Messaggio da oscar »

il 2, inducendo
<BR>se si suppone il numero delle partizioni di un insieme di n elementi in blocchi di ordine k pari a S(n, k)
<BR>1)quanto supposto é palese per n=1
<BR>2)aggiungendo un elemento e all\'insieme, il numero di partizioni ora possibili é S(n+1, k) dato da
<BR>S(n, k)*k
<BR>(numero partizioni possibili con e appartenente a uno qualunque dei blocchi in cui l\'insieme era giá stato diviso)
<BR>+S(n, k-1)
<BR>(ovvero numero partizioni possibili considerando e come blocco unitario)
<BR>
<BR>spero sia comprensibile (e magari pure giusto)
<BR>ciau <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>edit avevo scritto una x di troppo e una n di meno -.-<BR><BR>[ Questo Messaggio è stato Modificato da: oscar il 11-02-2004 19:17 ]
il vaut mieux une tête bien faite qu'une tête bien pleine --Michel Eyquem de Montaigne--
Bloccato