[N] La formula di inversione di Mobius

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

F.V. ha proposto di dimostrare altrove la cosiddetta \"formula d\'inversione di Möbius\", in relazione a un problema di combinatorica assegnato da Catraga.
<BR>
<BR>Non me ne voglia alcuno se mi permetto d\'aprire un topic tutto nuovo per postare la soluzione del problema, ma per amore dell\'ordine, mi son detto che <!-- BBCode Start --><I>forse</I><!-- BBCode End -->, in vista d\'un futuro riassetto del forum, sarebbe stato meglio procedere a questo modo...
<BR>
<BR><!-- BBCode Start --><B>Lemma H.1</B><!-- BBCode End -->: comunque fissato un r intero > 0, sia S := {1, 2, ..., r}. Allora, per ogni k = 1, 2, ..., r, il numero di possibili k-uple (i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>k</sub>) di S<sup>k</sup> tali che: i<sub>1</sub> < i<sub>2</sub> < ... < i<sub>k</sub> è pari al coefficiente binomiale Bin(r, k) di ordine r su k.
<BR>
<BR>Dim.: per ogni k = 1, 2, ..., r, sia detto n(k) il numero di possibili k-uple distinte (i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>k</sub>) ottenute fissando k elementi differenti nell\'insieme S := {1, 2, ..., r} di modo tale che sia: i<sub>1</sub> < i<sub>2</sub> < ... < i<sub>k</sub>.
<BR>
<BR>Considerando che le possibili permutazioni della generica k-upla così costruita sono in numero pari a k!, e che fra le k! permutazioni così determinate n\'esiste una e una sola ordinata per componenti così come sopra precisato, se ne deduce che n(k) · k! eguaglia il numero di possibili disposizioni semplici degli r oggetti distinti di S in gruppi di k; ossia se ne conclude (in altri termini) che: n(k) · k! = r(r-1)...(r-k+1) = r!/(r-k)!, sicché: n(k) = r!/[(r-k)! · k!] = Bin(r, k), q.e.d.
<BR>
<BR><!-- BBCode Start --><B>Teorema H.1</B><!-- BBCode End -->: per ogni n intero > 0, risulta che: sum[d | n] µ(d) = Floor(1/n), ove µ(-) denota la mu di Möbius, Floor(-) la funzione che ad ogni x reale fa corrispondere la sua parte intera bassa (ossia il più grande intero <= x) e la somma a primo membro s\'intende estesa a tutti e soli i divisori interi positivi di n.
<BR>
<BR>Dim.: se n = 1, la tesi è banalmente soddisfatta, essendo: µ(1) = sum[d | 1] µ(d) = Floor(1/1) = 1. Assunto n > 1, si ponga dunque: n = prod[k=1...r] p<sub>k</sub><sup>a[k]</sup>, ove r è in N<sub>0</sub>; p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>r</sub> sono numeri primi (naturali) distinti ed a[k] è un intero positivo, per ogni k = 1, 2, ..., r.
<BR>
<BR>Allora, essendo S := {1, 2, ..., r}: sum[d | n] µ(d) = µ(1) + sum[k=1...r] sum[(i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>k</sub>) -> S<sup>k</sup> t.c. i<sub>1</sub> < i<sub>2</sub> < ... < i<sub>k</sub>] µ(p<sub>i<sub>1</sub></sub> · p<sub>i<sub>2</sub></sub> · ... · p<sub>i<sub>k</sub></sub>), pur di considerare che, per definizione, µ(d) è diverso da zero sse d = 1 oppure d non è divisibile per il quadrato di alcun numero primo.
<BR>
<BR>Di qui, ancora per definizione, si conclude che: sum[d | n] µ(d) = µ(1) + sum[k=1...r] sum[(i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>k</sub>) -> S<sup>k</sup> t.c. i<sub>1</sub> < i<sub>2</sub> < ... < i<sub>k</sub>] µ(p<sub>i<sub>1</sub></sub> · p<sub>i<sub>2</sub></sub> · ... · p<sub>i<sub>k</sub></sub>) = 1 + sum[k=1...r] sum[(i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>k</sub>) -> S<sup>k</sup> t.c. i<sub>1</sub> < i<sub>2</sub> < ... < i<sub>k</sub>] (-1)^k = [Per il lemma (H.1)] = 1 + sum[k=1...r] (-1)^k · Bin(r, k) = sum[k=0...r] (-1)^k · Bin(n, k) = [Dalla formula di Newton per lo sviluppo della potenza di un binomio] = (1-1)^r = 0 = Floor(1/n), dacché si è supposto n > 1. Di qui la tesi, q.e.d.
<BR>
<BR><!-- BBCode Start --><B>Corollario H.1</B><!-- BBCode End -->: per ogni n intero > 0, risulta che: µ(n) * u(n) = E(1/n), ove u(-) denota la funzione unità, definita ponendo u(n) := 1, per ogni n intero > 0; e \"*\" il prodotto convolutorio di Dirichlet per le funzioni aritmetiche.
<BR>
<BR>Dim.: è sufficiente osservare che, per ogni n intero > 0: µ(n) * u(n) := sum[d | n] µ(d) · u(n/d) := sum[d | n] µ(d) = E(1/n), in accordo al teorema (H.1), q.e.d.
<BR>
<BR>Veniamo così, e finalmente, al mirabile risultato enunciato da F.V.
<BR>
<BR><!-- BBCode Start --><B>Formula d\'inversione di Möbius</B><!-- BBCode End -->: siano f(-) e g(-) due qualsivoglia funzioni aritmetiche. Allora, per ogni n intero > 0: f(n) = sum[d | n, d > 0] g(d), sse: g(n) = f(n) * µ(n) := sum[d | n] f(d) · µ(n/d), ove \"*\" denota ancora la convoluzione di Dirichlet per le funzioni aritmetiche.
<BR>
<BR>Dim.: per ipotesi, comunque scelto un n intero > 0: f(n) = sum[d | n] g(d) = sum[d | n] g(d) · u(n/d) =: g(n) * u(n), ove u(-) rappresenta qui la cosiddetta <!-- BBCode Start --><I>funzione unitaria</I><!-- BBCode End -->, di cui ho già sopra fornito una definizione.
<BR>
<BR>Del resto, per ogni n intero > 0: f(n) = g(n) * u(n) <==> [Poiché la mu di Möbius è una funzione invertibile rispetto al prodotto convolutorio di Dirichlet] <==> f(n) * µ(n) = [g(n) * u(n)] * µ(n) = [Considerando che il prodotto di Dirichlet è un\'operazione associativa e commutativa] = g(n) * [u(n) * µ(n)] = g(n) * [µ(n) * u(n)] = [Per il corollario (H.1)] = g(n) * Floor(1/n) = sum[d | n] g(d) · Floor(d/n) = g(n) · Floor(n/n) = g(n) · 1 = g(n), q.e.d.
<BR>
<BR>EDIT: il server dell\'SNS mi gioca brutti scherzi, ultimamente...
<BR>
<BR>
<BR>\"[...] E sparve, ei dì nell\'ozio,
<BR>chiuse in sì breve sponda,
<BR>segno d\'immensa invidia
<BR>e di pietà profonda,
<BR>d\'inestinguibil odio
<BR>e d\'indomato amor.\"
<BR>
<BR>Alessandro Manzoni, da <!-- BBCode Start --><I>Il cinque maggio</I><!-- BBCode End --><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 17-09-2004 07:30 ]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

Siccome altrove Ossido mi ha fatto notare, e giustamente, che molte delle formule contenute nel messaggio precedente somigliano tanto - provo a citare testualmente - \"ai caratteri incisi sul disco di Festo o ai geroglifici dell\'isola di Pasqua\" (LOOOL!), beh... v\'inviterei - se mai dovessero non esservi chiari alcuni passaggi - a chiedere spiegazioni, anziché tacere! Son certo che qualcuno vi risponderà.
<BR>
<BR>Del resto, cosa avete da guadagnarci a starvene zitti e buoni aspettando che sia magari un altro a formulare la domanda che vi frulla per la testa da chissà quanti giorni e che proprio non trovate il coraggio di postare perché <!-- BBCode Start --><I>maybe</I><!-- BBCode End --> l\'orco cattivo potrebbe divorarvi in un solo boccone, uh? Nulla, appunto... Pensate piuttosto a quel che avete da perdere! Ah, quasi dimenticavo... questo discorso si riferisce naturalmente a questa come ad <!-- BBCode Start --><I>ogni altra discussione</I><!-- BBCode End --> del forum. E chiedo scusa ai boss se mi sono qui permesso d\'interpretare un ruolo che oggettivamente non mi compete. Saluti!
<BR>
<BR>
<BR>\"Chi è maestro da cima a fondo prende sul serio solo le cose che riguardano i suoi allievi, persino se stesso.\" - F. W. Nietzsche, <!-- BBCode Start --><I>Al di là del bene e del male</I><!-- BBCode End -->

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

Vabbé, ho capito... Dunque, perché non tutto sia perduto, vediamo un po\' di stuzzicarvi l\'appetito rivisitando, alla luce delle recenti <!-- BBCode Start --><I>scoperte</I><!-- BBCode End -->, un problema discusso qui sul forum, seppur per altra via, quantomeno una mezza dozzina di volte...
<BR>
<BR><!-- BBCode Start --><B>Teorema (di Gauss):</B><!-- BBCode End --> <!-- BBCode Start --><I>utilizzando la formula d\'inversione di Möbius</I><!-- BBCode End -->, dimostrare che, per ogni n intero > 0: n = sum[d | n] phi(n), ove phi(-) denota - al solito - la totiente di Eulero e la somma a secondo membro s\'intende estesa a tutti e soli i divisori naturali di n.
<BR>
<BR>
<BR>\"Il vizio e la virtù non sono per l\'artista che la materia prima della propria arte.\" - Oscar Wilde<BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 19-09-2004 18:21 ]

Bloccato