combinazioni elementari

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 27 mag 2010, 22:30

sasha™ ha scritto:Quella cosa viene fuori sostituendo n a 500 nel calcolo che ho fatto io oppure l'hai tirata fuori dal cilindro così?
Né l'una né l'altra.
A dire il vero il tuo calcolo non l'ho letto, ma potrebbe anche generalizzarsi.

Quella formula deriva dall'osservazione che i numeri cercati sono i coefficienti della serie di Taylor di

$ $\frac{1}{(1-x)(1-x^2)(1-x^3)(1-x^4)} $.

Quindi la risoluzione diventa meccanicamente algebrica, e consiste nello scomporre la frazionazza in frazioni semplici e costruire la formula finale pezzo per pezzo, a colpi di serie geometriche e simili.

In generale, con $ $k $ sacchetti invece di 4, i modi di partizionare $ $n $ monete sono asintotici a

$ $\frac{n^{k-1}}{k!(k-1)!} $.

Tutto ciò è studiatissimo dalla teoria, ed era arcinoto ai tempi di Dudeney, per questo mi stupisco che abbia dichiarato di averci speso del tempo, e di giudicarlo un problema difficile.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ » 27 mag 2010, 22:55

Serie di Taylor? Potresti spiegarlo in modo da far capire anche un ignorante come me? L'argomento è interessante, e mi piacerebbe capirci qualcosa in più.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 28 mag 2010, 00:49

E' un argomento avanzato che non sta bene in matematica ricreativa, speravo che bastassero quelle poche parole per dare un'idea.
La parola-chiave è generating functions, cercandola con google dovresti trovare molta più roba di quanta te ne possa spiegare io.

In pratica il discorso è questo: avrai già osservato che vale l'identità

$ $\frac{1}{1-x} = 1+x+x^2+x^3+x^4+\cdots $, dove $ $|x|<1 $.

Esistono moltissime identità come questa, che esprimono certe funzioni (nel nostro caso $ $1/(1-x) $) con sommatorie infinite di potenze di $ $x $ (nel nostro caso $ \sum_n x^n $). Per sapere di più su questo, cerca Taylor series.

In generale puoi variare i coefficienti delle potenze di $ $x $ per ottenere diverse sommatorie, che possono convergere a diverse funzioni. Quindi in generale avrai una somma del tipo

$ $\sum_{n=0}^{\infty}a_n x^n $.

Adesso il trucchetto è dire: pongo $ $a_n $ uguale al numero delle partizioni di $ $n $ monete in 4 sacchetti, ed ho così "codificato" la sequenza d'interesse con una serie di potenze. Fatto questo, posso trattare la serie di potenze con metodi algebrico/analitici, fino a tirarne fuori quel che voglio.

Nel nostro esempio la cosa non è banalissima (infatti è solo straightforward), ma si può fare facilmente con 2 sacchetti invece di 4, a scopo dimostrativo.
L'osservazione è che, svolgendo per esteso il prodotto

$ $(1+x+x^2+x^3+x^4+\cdots)(1+x^2+x^4+x^6+x^8+\cdots) $,

il coefficiente di $ $x^n $ è uguale al numero di modi di partizionare $ $n $ monete in 2 sacchetti. Infatti, ogni monomio del tipo $ $x^a\cdot x^{2b} $ può essere interpretato come la partizione che mette $ $a+b $ monete nel primo sacchetto e $ $b $ monete nel secondo sacchetto. La cosa si generalizza in modo ovvio a qualsiasi numero di sacchetti...

Grazie alla formula della serie geometrica, per $ $|x|<1 $, quel prodotto è ben definito e vale

$ $\frac{1}{(1-x)(1-x^2)} = \frac 1 {2(1-x)^2} + \frac 1 {4(1-x)} + \frac 1 {4(1+x)} = \sum_{n=0}^\infty \frac{2n+3+(-1)^n}{4}\ x^n $.

Quindi i modi di partizionare $ $n $ monete in 2 sacchetti sono $ $\frac{2n+3+(-1)^n}{4} = \left\lfloor \frac{2n+5}{4}\right\rfloor $. Ovviamente con 2 sacchetti si tratta di un overkill, perché ci si poteva arrivare con mezzi molto più elementari. Con più sacchetti (ad esempio 4) comincia a diventare un metodo conveniente, soprattutto perché automatico.

Il succo del discorso è che codifichi un'intera sequenza con una funzione generatrice, e il tuo scopo è esprimere quella funzione come serie di potenze. Quindi sposti un problema che è essenzialmente combinatorio in un problema che è essenzialmente algebrico, e risolubile in modi algoritmici. Andando avanti su questa strada, si scopre che certe operazioni combinatorie molto naturali (unioni, accoppiamenti, etc) si traducono pari-pari in operazioni altrettanto naturali su funzioni generatrici (somme, prodotti, etc). Dopo aver sistematizzato tutto il macchinario, ragionerai quasi solo in termini di funzioni generatrici, e quasi mai in termini di oggetti combinatori.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ » 28 mag 2010, 15:52

Ti ringrazio moltissimo per le delucidazioni, l'argomento è molto interessante, lo approfondirò appena possibile. Solo un ulteriore chiarimento:
Tibor Gallai ha scritto:$ $\frac{1}{(1-x)(1-x^2)} = \frac 1 {2(1-x)^2} + \frac 1 {4(1-x)} + \frac 1 {4(1+x)} = \sum_{n=0}^\infty \frac{2n+3+(-1)^n}{4}\ x^n $.
Non ho capito questo passaggio. Come si passa da quel prodotto a quella sommatoria?

EDIT: Niente, ho capito. Grazie di tutto! :D

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 28 mag 2010, 18:34

penso usando
Tibor Gallai ha scritto:In pratica il discorso è questo: avrai già osservato che vale l'identità

$ $\frac{1}{1-x} = 1+x+x^2+x^3+x^4+\cdots $, dove $ $|x|<1 $.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ » 28 mag 2010, 21:34

C'è qualche esercizio (facile, magari :lol: ) per il quale si deve applicare questa serie? Vorrei provare un po', ringrazio in anticipo chi me ne posterà uno.

(O mi conviene aprire un nuovo topic?)

Avatar utente
gian92
Messaggi: 558
Iscritto il: 12 nov 2007, 13:11
Località: roma

Messaggio da gian92 » 28 mag 2010, 23:37

dimostra che $ e^{i\pi}+1=0 $

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 29 mag 2010, 01:03

Mah, quello mi sembra il modo migliore per offuscargli le idee.
E' estremamente probabile, anzi estremamente sicuro che non conosca una definizione coerente di esponenziale complesso...

Per proseguire, puoi cimentarti in questo problema, che nessuno ha cagato ma è un buon banco di prova per usare le funzioni generatrici:
viewtopic.php?t=11033
Forse però il salto è troppo grosso.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ » 29 mag 2010, 14:33

So scrivere i complessi in forma esponenziale, ma da lì a capire perché effettivamente vale l'uguaglianza direi che ne passa...

Del problema non ho capito la traccia. Cosa vuol dire che una permutazione si decompone in cicli di lunghezza pari o dispari? Che, applicando n volte la permutazione, si torna all'ordinamento iniziale? E devo dimostrare che le permutazioni con n pari sono tante quante quelle con n dispari?

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 29 mag 2010, 21:42

sasha™ ha scritto:So scrivere i complessi in forma esponenziale, ma da lì a capire perché effettivamente vale l'uguaglianza direi che ne passa...
Puoi anche porla come definizione, se vuoi. Nel qual caso il problema è banale. Oppure puoi definire esponenziale e funzioni trigonometriche complesse come serie di potenze (che forse era la via che voleva farti seguire Tizio), ma per dimostrare che ciò che fai ha senso c'è tanta di quella sovrastruttura da aggiungere che imho la cosa finisce per confondere, più che chiarire.
Del problema non ho capito la traccia. Cosa vuol dire che una permutazione si decompone in cicli di lunghezza pari o dispari? Che, applicando n volte la permutazione, si torna all'ordinamento iniziale? E devo dimostrare che le permutazioni con n pari sono tante quante quelle con n dispari?
Appunto, questa è una buona occasione per ravvivare quel thread, invece di perseverare nell'OT da questa parte. O no?
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
gian92
Messaggi: 558
Iscritto il: 12 nov 2007, 13:11
Località: roma

Messaggio da gian92 » 29 mag 2010, 21:54

Tibor Gallai ha scritto:
sasha™ ha scritto:So scrivere i complessi in forma esponenziale, ma da lì a capire perché effettivamente vale l'uguaglianza direi che ne passa...
Puoi anche porla come definizione, se vuoi. Nel qual caso il problema è banale. Oppure puoi definire esponenziale e funzioni trigonometriche complesse come serie di potenze (che forse era la via che voleva farti seguire Tizio), ma per dimostrare che ciò che fai ha senso c'è tanta di quella sovrastruttura da aggiungere che imho la cosa finisce per confondere, più che chiarire.
si, Tizio voleva fargli seguire quella strada.
poi però mi sono reso conto che effettivamente non era un buon esercizio se uno non ha mai visto cose del genere.

sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ » 29 mag 2010, 22:08

Tibor Gallai ha scritto:
sasha™ ha scritto:So scrivere i complessi in forma esponenziale, ma da lì a capire perché effettivamente vale l'uguaglianza direi che ne passa...
Puoi anche porla come definizione, se vuoi. Nel qual caso il problema è banale. Oppure puoi definire esponenziale e funzioni trigonometriche complesse come serie di potenze (che forse era la via che voleva farti seguire Tizio), ma per dimostrare che ciò che fai ha senso c'è tanta di quella sovrastruttura da aggiungere che imho la cosa finisce per confondere, più che chiarire.
Non mi riferivo all'Identità di Eulero, ma al perché un complesso in forma polare è uguale al suo modulo per $ e^{i\theta} $. C'è da sfruttare la formula per la quale $ $ e = \sum_{n=0}^{\infty} \frac1{n!} $ $ ? Però non so come si eleva a un complesso...
Tibor Gallai ha scritto:
sasha™ ha scritto:Del problema non ho capito la traccia. Cosa vuol dire che una permutazione si decompone in cicli di lunghezza pari o dispari? Che, applicando n volte la permutazione, si torna all'ordinamento iniziale? E devo dimostrare che le permutazioni con n pari sono tante quante quelle con n dispari?
Appunto, questa è una buona occasione per ravvivare quel thread, invece di perseverare nell'OT da questa parte. O no?
Continuo a non aver chiara la traccia. :lol:

Avatar utente
gian92
Messaggi: 558
Iscritto il: 12 nov 2007, 13:11
Località: roma

Messaggio da gian92 » 29 mag 2010, 22:20

sasha™ ha scritto:
Tibor Gallai ha scritto:
sasha™ ha scritto:So scrivere i complessi in forma esponenziale, ma da lì a capire perché effettivamente vale l'uguaglianza direi che ne passa...
Puoi anche porla come definizione, se vuoi. Nel qual caso il problema è banale. Oppure puoi definire esponenziale e funzioni trigonometriche complesse come serie di potenze (che forse era la via che voleva farti seguire Tizio), ma per dimostrare che ciò che fai ha senso c'è tanta di quella sovrastruttura da aggiungere che imho la cosa finisce per confondere, più che chiarire.
Non mi riferivo all'Identità di Eulero, ma al perché un complesso in forma polare è uguale al suo modulo per $ e^{i\theta} $. C'è da sfruttare la formula per la quale $ $ e = \sum_{n=0}^{\infty} \frac1{n!} $ $ ? Però non so come si eleva a un complesso...
è la stessa cosa , quello che dici tu è:
$ \rho \cdot e^{i\theta}=\rho(\cos \theta+i\sin \theta) $
vedi cosa succede per $ \theta=\pi $

sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ » 29 mag 2010, 23:01

Lo so che $ \rho \cdot e^{i\theta}=\rho(\cos \theta+i\sin \theta) $, e che per $ \theta=\pi $ ottengo l'Identità di Eulero.
Quello che non so fare è giustificare la formula $ \rho \cdot e^{i\theta}=\rho(\cos \theta+i\sin \theta) $.
Se non sapessi che è vera, come potrei dimostrarla? Sfruttando $ $ e = \sum_{n=0}^{\infty} \frac1{n!} $ $ o cos'altro?

EDIT: E se combinassi quella con queste:

$ ${sen\,} \theta = \theta - \frac{\theta^3}{3!} + \frac{\theta^5}{5!} - \frac{\theta^7}{7!} + \cdots = \sum_{n=0}^\infty \frac{{(-1)}^n \theta^{2n+1}}{(2n+1)!}$ $

$ $\cos \theta = 1 - \frac{\theta^2}{2!} + \frac{\theta^4}{4!} - \frac{\theta^6}{6!} + \cdots = \sum_{n=0}^\infty \frac{{(-1)}^n \theta^{2n}}{(2n)!}$ $ ?

EDIT 2: Mi sa che così non viene nemmeno troppo difficile, quasi quasi ci provo.

Dunque, $ $ e^{i\theta} = \sum_{n=0}^{\infty} \frac{{(i\theta)}^n}{n!} $ $, no?

Bé, scomporre da qui è banale, l'esponente di $ i $, oltre a darmi il segno, mi indica anche la presenza (o meno) dell'unità immaginaria, che c'è con tutti gli esponenti dispari (e infatti moltiplica il seno), i segni sono ovviamente alterni e quindi vale l'uguaglianza. Uao, mi sento realizzato.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 29 mag 2010, 23:19

sasha™ ha scritto:Continuo a non aver chiara la traccia. :lol:
Chiedi chiarimenti nell'altro thread. Ha senso parlarne qui??
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Rispondi