combinazioni elementari

[sasha™]

E allora mi dichiaro ufficialmente confuso.

Bof, allora separo tutte le 500 monetine. Posso formare fino a 250 mucchietti da 2, diciamo che ne faccio k. Allora posso fare (500 - 2k)/3 mucchietti da tre (arrotondato per difetto), al massimo.

Il risultato è la somma per k da 0 a 250 della parte intera di k(500 - 2k)/3?

Non sviluppo il calcolo per mancanza di tempo, ma è giusto? E, in ogni caso, prima cosa ho sbagliato?

EDIT: cazzata, mancano i mucchietti da 4. Correggo dopo.

[SkZ]

Contro-bonus: quanti sono i modi di ripartire le 500 monetine in mucchietti, ognuno dei quali non contenga più di 4 monetine? (nuovamente, l'ordine non fa differenza)

Mmh. Divido le monetine in 125 mucchietti da 4. Ogni mucchietto da 4 può restare com'è, o venire diviso come 1-1-1-1, 1-1-2, 1-3, 2-2. In totale può essere diviso in 5 modi diversi. Mi verrebbe da dire 625, ma mi sa che così non considero tutti i casi.

in verita' ne consideri molti multipli, dato che nel tuo caso l'ordine conta
visto che l'ordine non conta puoi smontare un mucchietto solo se hai smontato i precedenti

[Tibor Gallai]

Il punto è che (insisto) la domanda non è posta a caso, e si può rispondere senza fare calcoli.

[SkZ]

posso andare da 125 mucchi a 500, ordinati per numero di monete
ogni volta che ho una coppia di 2 mucchi da 2 posso sostituirla con la coppia 1-3

[sasha™]

A me viene, dopo calcoli lungherrimi che, al momento, sono troppo stanco per riportare, 251*125*84 - (334*125 + 331*124 + 329*123 + 326*122 + 323*121 + ... + 6*2 + 3*1), dove il primo termine diminuisce secondo la serie -3 -2 -3, e il secondo diminuisce sempre di uno. Numericamente quanto vale? Ed è giusto?

[Tibor Gallai]

Allora.

Se la somma è
$ $251\cdot 125\cdot 84-\left(\sum_{i=0}^{41}3i(8i+1)+\sum_{i=0}^{41}(3i+1)(8i+3)+\sum_{i=0}^{41}(3i+2)(8i+6)\right) $,
è giusta come ordine di grandezza ma è un po' scazzata per difetto.

Rinnovo il consiglio di non fare calcoli per risolverlo.

[sasha™]

Sì, la somma è quella. Di quanto esce più piccola del previsto?

[Tibor Gallai]

Di 21084, ma insisto nel dire che sia un'informazione completamente irrilevante.
(ma forse nemmeno tanto, e chi ha orecchie per intendere, intenda)

[taifu]

è lo stesso risultato del problema iniziale, una partizione di n in k parti la puoi vedere anche come una partizione di n in parti di grandezza ciascuna minore uguale a k, un modo semplice di vedere questo è tramite i diagrammi di Young http://en.wikipedia.org/wiki/Young_diagram (scambiando le righe con le colonne)

[Tibor Gallai]

Oh, benissimo.

[sasha™]

Lo volevo scrivere io, ci ero arrivato oggi durante la lezione di storia!

[Clara]

Era questo il famoso problema senza foglio...?

[Hector]

BONUS:trovare una formula unica per $ n $ penny. La soluzione non mi sembra affatto banale.

Infatti, la parola giusta è "straightforward":

$ $\left\lfloor\frac{2n^3+30n^2+9(15+(-1)^n)n+319}{288}\right\rfloor $.

solo una cosa: questa come l'hai tirata fuori??

[io.gina93]

BONUS:trovare una formula unica per $ n $ penny. La soluzione non mi sembra affatto banale.

Infatti, la parola giusta è "straightforward":

$ $\left\lfloor\frac{2n^3+30n^2+9(15+(-1)^n)n+319}{288}\right\rfloor $.

solo una cosa: questa come l'hai tirata fuori??

me lo chiedevo anch'io...

[sasha™]

Era questo il famoso problema senza foglio...?

Sì, era questo. E il bello è che oggi mi è venuta in mente la soluzione mentre pensavo a tutt'altro.


Quella cosa viene fuori sostituendo n a 500 nel calcolo che ho fatto io oppure l'hai tirata fuori dal cilindro così?