Regoli e Calcolo Combinatorio
MinimO
matematica abbiamo fatto un patto reciproca non belligeranza,
vi chiedo supporto nella soluzione di un problema di prima elementare,
sarei curioso di conoscere la forumla che permetta di calcolare il
numero di combinazioni con i regoli-colori:
Faccio un esempio: il "muretto" del 4:
1+1+1+1
1+1+2
1+3
2+2
2+1+1
3+1
4
Ottengo 7 combinazioni con "ripetizioni" e 5 senza "ripetizioni"
(sempre che ripetizioni sia un termine corretto).
Da wikipedia mi sembra che il mio caso ricada in questa "definizione":
"combinazioni con ripetizioni per n oggetti di classe k rappresentano
il numero delle derivate parziali di ordine k calcolabili per una
funzione a n variabili".
Bene questa definizione, per quanto poetica, mi lascia come un vitello
che osserva passare un treno...
Grazie :)
Silvio Sergio
"MinimO" <glassate...@gmail.com> wrote in message
news:ifum8v$p12$1...@news.eternal-september.org...
Problema di prima elementare?
Se ho ben capito cio' di cui parli, e' la funzione di partizione.
La funzione di partizione è definita per ogni intero n come il numero di
modi in cui si può scrivere n come somma di interi, senza tener conto
dell'ordine degli addendi.
Vatti a vedere il link su wiki
http://it.wikipedia.org/wiki/Funzione_di_partizione_(matematica) e poi dimmi
se e' matematica delle elementari.
La formula che calcola il numero che stai chiedendo e' alla portata solo di
pochi eletti, altro che elementari.
Se invece l'ordine dei fattori conta (cioeè se 1+3 e 3+1 sono due partizioni
possibili e distinte) allora il problema diventa facilissimo e forse alla
portata anche dei bambini, per lo meno per numeri piccoli.
Infatti basta che scrivi 4 cifre "1". Tra una e l'altra, puoi metterci o
meno dei simboli "+", in tutti i modi possibili.
1 1 1 1 = 4
1 1 1+1 = 3+1
1 1+1 1 = 2+2
1 1+1+1 = 2+1+1
1+1 1 1 = 1+3
1+1 1+1 = 1+2+1
1+1+1 1 = 1+1+2
1+1+1+1 = 1+1+1+1
come vedi sono 8=2^3=2*2*2 perche' hai 3 buchi nei quali puoi metterci o non
metterci dei segni "+" (quindi 2 possibili scelte per ognuno dei 3 buchi).
Il caso che tu chiami "senza ripetizioni" se non ho capito male dovrebbe
contare solo le some che hanno tutti addenti differenti.
A occhio non mi sembra ci siano modi semplicei per contarle.
--
Silv:o)
MinimO
Gentilissimo,
in sostanza il problema di prima elementare (per davvero!) è costruire
fiscamente quelli che chiamano i "muretti" con tutte le combinazioni
possibili dei regoli, dove, come dicevi 3+1 e 1+3 sono due combinazioni
diverse.
Mi incuriosiva sapere se c'è una "formula" per sapere il numero di
combinazioni possibili.
Seguendo il tuo il tuo esempio, quello del 7 dovrebbe essere 2^6 (64).
Quindi qui ho ancora da "lavorare" :)
Stasera mi ci applico perchè ne ho fatti appena 51 :)
Grazie, ciao.
Silvio Sergio
> Seguendo il tuo il tuo esempio, quello del 7 dovrebbe essere 2^6 (64).
>
> Quindi qui ho ancora da "lavorare" :)
>
> https://spreadsheets.google.com/ccc?key=0AgoCVnSnw5iudC1qeXlOUWY4ZGtUWFBrM2hMNjF5S3c&hl=en&authkey=CO-ol5MC
>
> Stasera mi ci applico perchè ne ho fatti appena 51 :)
un modo per generare tutti le 64 partizioni e' quello classico utilizzato
per scrivere i numeri binari:
000000
000001
000010
000011
ecc..
in pratica fai così: (usa un fixed font per vedere gli schemini ben
allineati)
parti con i 7 mattoni senza nessun divisore
00: _ _ _ _ _ _ _
guardi l'ultimo spazio a destra e ci metti un divisore
01: _ _ _ _ _ _|_
torni indietro finche' non trovi un buco vuoto, ci metti il divisore e
svuoti tutti gli spazi a destra
02: _ _ _ _ _|_ _
riempi l'ultimo buco vuoto a destra
03: _ _ _ _ _|_|_
sei di nuovo a fine corsa: cerchi il primo buco libero e lo riempi,
svuotando gli altri
04: _ _ _ _|_ _ _
continui con l'algoritmo generale: riempi l'ultimo buco a destra
05: _ _ _ _|_ _|_
poi cerchi il primo buco libero da destra, lo riempi e svuoti il resto
06: _ _ _ _|_|_ _
di nuovo riempi l'ultimo buco a destra (come avrai ormai capito questa
operazione la fai in tutte le mosse pari)
07: _ _ _ _|_|_|_
ora cerchi il primo buco di destra e lo riempi svuotando il resto (e questo
farai in tutte le mosse pari)
08: _ _ _|_ _ _ _
siamo arrivati a 8, dovrai ripetere lo schema fino alla fine. Ti riporto gli
ultimi tre passi
..
61: _|_|_|_|_ _|_
62: _|_|_|_|_|_ _
63: _|_|_|_|_|_|_
se vuoi puoi sapere al volo come e' fatta la riga n: basta scrivere n in
binario. Un modo rapido e' questo:
per esempio n=27.
Dividi per 2: 13 col resto di 1: l'ultimo spazio a destra va riempito con un
divisore
27: _?_?_?_?_?_|_
Dividi per 2: 6 col resto di 1: il successivo spazio a destra va riempito
con un divisore
27: _?_?_?_?_|_|_
Dividi per 2: 3 col resto di 0: il successivo spazio a destra va lasciato
vuoto
27: _?_?_?_ _|_|_
Dividi per 2: 1 col resto di 1: il successivo spazio a destra va riempito
con un divisore
27: _?_?_|_ _|_|_
Dividi per 2: 0 col resto di 1: il successivo spazio a destra va riempito
con un divisore
27: _?_|_|_ _|_|_
Le succcessive divisioni darebbero sempre 0 col resto di 0, quindi tutti gli
spazi a destra saranno vuoti
27: _ _|_|_ _|_|_
viceversa la configurazione
??: _|_ _|_ _|_ _
vale
32 08 02
16 04 01
??: _|_ _|_ _|_ _ =32+8+2=42
Spero di esserti stato di aiuto, magari ho ecceduto nelle spiegazioni ma non
sapevo quanto del lavoro deve essere fatto dai bambini.
Messo cosi', l'algoritmo di costruzione di una configurazione dopo l'altra
credo possa essere messo in pratica anche da un bambino.
--
Ciao, Silv:o)
MinimO
grazie :)
Alessandro Cara
[cut]
> La formula che calcola il numero che stai chiedendo e' alla portata solo di
> pochi eletti, altro che elementari.
Hai bambini? Forse no. Per la verita' neanche io, ma se c'e' una cosa di
cui ormai ho imparato a non sorprendermi piu' e la "acutezza" e la
capacita' di apprendimento e le soluzioni "irrazionali" che un bambino
riesce a dare. Magari avessi ora, ancora, quella capacita'!
Se poi le cose da apprendere sono in forma di gioco si aprono soluzioni
infinite. ;-{)
--
ac (x=y-1)
Tetis
> Premettendo che io in questo gruppo sono un intruso e che io e la
> matematica abbiamo fatto un patto reciproca non belligeranza,
>
> vi chiedo supporto nella soluzione di un problema di prima elementare,
> sarei curioso di conoscere la forumla che permetta di calcolare il
> numero di combinazioni con i regoli-colori:
>
> Faccio un esempio: il "muretto" del 4:
> 1+1+1+1
> 1+1+2
> 1+3
> 2+2
> 2+1+1
> 3+1
> 4
> Ottengo 7 combinazioni con "ripetizioni" e 5 senza "ripetizioni"
> (sempre che ripetizioni sia un termine corretto).
1+2+1 perché non l'hai inclusa?
Tetis
> "MinimO" <glassatemidis...@gmail.com> wrote in message
> Infatti basta che scrivi 4 cifre "1". Tra una e l'altra, puoi metterci o
> meno dei simboli "+", in tutti i modi possibili.
>
> 1 1 1 1 = 4
> 1 1 1+1 = 3+1
> 1 1+1 1 = 2+2
> 1 1+1+1 = 2+1+1
> 1+1 1 1 = 1+3
> 1+1 1+1 = 1+2+1
> 1+1+1 1 = 1+1+2
> 1+1+1+1 = 1+1+1+1
>
> come vedi sono 8=2^3=2*2*2 perche' hai 3 buchi nei quali puoi metterci o non
> metterci dei segni "+" (quindi 2 possibili scelte per ognuno dei 3 buchi).
>
> Il caso che tu chiami "senza ripetizioni" se non ho capito male dovrebbe
> contare solo le some che hanno tutti addenti differenti.
M'era sembrato di capire che intendesse che se l'ordine non conta i
vari modi di riordinare la partizione sono ripetizioni della
partizione, quindi senza partizione penso intenda i diagrammi di Young
da 4 elementi che sono effettivamente 4, 3+1, 2+2, 2+1+1,1+1+1+1
ovvero cinque. Si può procedere in entrambe le direzioni: o si contano
prima le partizioni non ordinate con il trucco che dici e si
semplificano poi i doppioni, oppure si costruiscono i diagrammi di
Young (ricorsivamente) e per ogni diagramma di Young si considerano
tutti i riordinamenti che possono essere contati con il coefficienti
multinomiale al cui numeratore sta il fattoriale del numero di righe
ed al cui denominatore stanno i fattoriali delle molteplicità delle
righe equipotenti. Per esempio: 3+1+1 ---> 3!/(1!2!).
> A occhio non mi sembra ci siano modi semplicei per contarle.
Si contano per ricorsione scomponendo il problema in problemi più
semplici. Il problema parziale da risolvere è quello di esprimere per
ricorsione il numero di modi di ripartire un numero usando numeri non
più piccoli di un numero assegnato.
> --
> Silv:o)- Nascondi testo citato
>
> - Mostra testo citato -
MinimO
L'avevo premesso, sono un caprone :)
Silvio Sergio
>> La formula che calcola il numero che stai chiedendo e' alla portata solo
>> di
>> pochi eletti, altro che elementari.
>
> Hai bambini? Forse no. Per la verita' neanche io, ma se c'e' una cosa di
> cui ormai ho imparato a non sorprendermi piu' e la "acutezza" e la
> capacita' di apprendimento e le soluzioni "irrazionali" che un bambino
> riesce a dare. Magari avessi ora, ancora, quella capacita'!
> Se poi le cose da apprendere sono in forma di gioco si aprono soluzioni
> infinite. ;-{)
Con me sfondi una porta aperta, sono un appassionato praticante di ogni
forma di matematica ricreativa. Uno dei figli di Gardner.
Non ho bambini, ma ho fatto un bel po' di ripetizioni a bambini, sempre
condotte giocando, oltre ad aver allevato alla matemagia un paio di nipoti.
L'unico limite sono i loro insegnanti troppo spesso cerebrolesi :(
La frase che citavi rguardava la formula di Rademacher per il calcolo della
funzione di partizione, davvero abnorme per un rpoblema all'apparenza
affrontabile con un po' di sommatorie e fattoriali:
--
Silv:o)
Silvio Sergio
espresso
ha fatto il resto
--
Silv:o)