combinazioni elementari

[Tibor Gallai]

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.

[sasha™]

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]

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.

[sasha™]

Ti ringrazio moltissimo per le delucidazioni, l'argomento è molto interessante, lo approfondirò appena possibile. Solo un ulteriore chiarimento:

$ $\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!

[SkZ]

penso usando

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 $.

[sasha™]

C'è qualche esercizio (facile, magari ) 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?)

[gian92]

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

[Tibor Gallai]

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.

[sasha™]

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]

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?

[gian92]

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™]

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...

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.

[gian92]

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™]

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]

Continuo a non aver chiara la traccia.

Chiedi chiarimenti nell'altro thread. Ha senso parlarne qui??