Parentesi

[Cavia1]

La proprietà associativa, per esempio del prodotto, di solito la si enuncia per tre numeri: (ab)c=a(bc).
Srcivendola per 4 numeri diventa:
((ab)c)d=(a(bc))d=(ab)(cd)=a((bc)d)=a(b(cd))
e le parentesi si possono mettere in 5 modi diversi.
Per 5 numeri i modi diventano 14 e per 6 diventano 42.
In quanti modi diversi si possono mettere le parentesi con 10 numeri?
E con n numeri?

Il problema è stato posto sul giornalino "Il Leonardo" n.24


Cavia

[Principe2]

sembra che valga la seguente formula:
indicando con P(n) le parentesi relative ad n numeri, se n>3 si ha:

P(n) = 2P(n-1) + 2P(n-2) + ..... + 2P(4) + 2P(3)

applicando questa formula, se non ho sbagliato a spingere i tasti della calcolatrice si ottiene P(10) = 3402

la seconda richiesta suppongo sia di trovare P(n) in funzione di n e non degli P precedenti... altrimenti per trovare P(1000) ci vorrebbe un mese... ma per adesso non mi viene in mente nulla.

ciao, ubermensch

[tony19]

ciao a tutti.

                        n-5

azzardo un     m = 7*2*3

dove 

    m = numero dei modi, 

    n = numero dei numeri   (pare biblica!)

vale per n >= 5, MA, se si arrotonda il risultato all'unità,

anche per 1 <= n <=4. strano, no?

               n      m

                1      0

                2      1

                3      2

                4      5

                5     14

                6     42

                7    126

                8    378

                9   1134

               10   3402

               11  10206

(ammesso che l'estrapolazione di quella sequenza sia corretta)

tony

*Edited by - tony on 26/02/2004 05:34:58

[Principe2]

pare corretta... hai provato a dimostrarla!!

ciao, ubermensch

p.s. per non vedere che ogni P(n) è il triplo del precedente occorre proprio essere ciechi!!

[tony19]

*quote:

---

... per non vedere che ogni P(n) è il triplo del precedente occorre proprio essere ciechi!!

---

sì, uebermensch, ma i tripli che ogni non-cieco nota nella tabella da me prodotta
non dimostrano niente, perchè sono generati dalla mia formula triplicante,
che potrebbe benissimo essere errata.

la sequenza data era {1, 2, 5, 14, 42}, e di tripli ne contiene uno solo;
gli altri che ho mostrato, se vuoi, sono estrapolazioni di quell'unico!

ciao, tony

[Principe2]

caro tony la tua formula è esattissima; la dimostro per induzione:

per n=5 si ha P(5) = 7*2 = 14 ed è giusta;
supponiamo per ipotesi induttiva che P(n-1) = 2*7*3^((n-1)-5)
allora, dalla formula che ho dato io si ha:

1) P(n-1)= 2P(n-2) + 2P(n-3) + .... + 2P(4) + 2P(3)
2) P(n) = 2P(n-1) + 2P(n-2) + ..... + 2P(4) + 2P(3)

quindi, sostituendo la 1 nella 2 si ha:

P(n) = 2P(n-1) + P(n-1) = 3P(n-1)

ricordando, l'ipotesi induttiva, si ha P(n) = 3*(2*7*3^((n-1)-5)
che equivale alla tesi.
ne consegue che la formula di Tony vale per ogni n > 4.

ciao, ubermensch

[Cavia1]

Non concordo sulla formula di tony, che è costruita ad hoc per n=5 e n=6!!. Infatti con 7 numeri ci sono 132 modi di disporre le parentesi e non 126, come ho ottenuto scrivendoli scimmiescamente tutti! E poi non concordo sulla formula ricorsiva di ubermensch. Per esempio si otterrebbe che P(4)=2P(3)=4, mentre invece p(4)=5 e la formula che ha la pretesa di valere da 4 in poi è già sbagliata per il primo valore!
Lo scrivere i 132 modi di disporre le parentesi in 7 numeri è stato comunque utile, perché mi ha fatto intuire una formula ricorsiva, diversa da quella di uber e che devo collaudare. Il fatto è che sul n.25 del Leonardo si anticipa che la rubrica col problema delle parentesi avrà il titolo "relazioni ricorsive". Ne deduco che sia questa la strada, come uber ha intuito prima di me!

Cavia

[Principe2]

effettivamente ho dimenticato di modificare il messaggio: la mia formula ricorsiva vale (anzi varrebbe) per n>4 e non per n>3

ciao, ubermensch

[Principe2]

la faccenda si complica!
questa è la formuletta ricorsiva che ho trovato, verificata fino a P(11):
premessa: nelle parentesi metto solo gli indici:

poniamo P(k) = 0 se k <= 2

per n pari, n>=6, """"dovrebbe valere""":

P(n) = 2P(n-1) + 2P(n-2) + 2a(1)P(3)P(n-3) + 2a(2)P(4)P(n-4) + ....
.... + 2a(n/2-1)P(n/2+1)P(n/2-1) + 2P(n/2)

dove a(i) = 1 se n/2 > P(i+2), a(i) = 1/P(i+2) se n/2 = P(i+2)


per n dispari, n>=5

P(n) = 2P(n-1) + 2P(n-2) + 2a(1)P(3)P(n-3) + 2a(2)P(4)P(n-4) + ..... + 2a((n-1)/2)P((n+1)/2)P((n-1)/2)

dove a(i) = 1 se (n-1)/2 >= P(i+2), a(i) = 1/P(i+2) se (n-1)/2 < P(i+2)

faccio un paio di esempi:

applicando la formula per n pari si ottiene:

P(6) = 2P(5) + 2P(4) + 2P(3) = 28 + 10 + 4 = 42

applicando quella per n dispari, si ottiene:

P(7) = 2P(6) + 2P(5) + 2P(3)P(4) = 84 + 28 + 2*2*5 = 132

a me sembra giusta, in caso domani ti posto una dimostrazione molto molto intuitiva.. (quindi una non-dimostrazione... una giustificazione)

ciao, ubermensch

[Cavia1]

Considero il caso di 5 numeri: abcde
Posso separarli in 4 modi diversi:
a|bcde, ab|cde, abc|de, abcd|e
Nel primo caso le parentesi le posso mettere in P(1) modi per a e in p(4) modi per bcde per un totale di P(1)P(4) modi
nel secondo caso in P(2) modi per ab e in P(3) modi per cde, per un totale di P(2)P(3) modi, ecc.
Dunque:
P(5)=P(1)P(4)+P(2)P(3)+P(3)P(2)+P(4)P(1).
In generale:
P(n)=P(1)P(n-1)+P(2)P(n-2)+ ... +P(n-1)P(1)

In particolare:
P(1)=1
P(2)=P(1)P(1)=1
P(3)=P(1)P(2)+P(2)P(1)=2
P(4)=P(1)P(3)+P(2)P(2)+P(3)P(1)=5
P(5)=P(1)P(4)+P(2)P(3)*P(3)P(2)+P(4)P(1)=14
ecc...
P(10)=4862

Mi sembra addirittura che valga la formula
P(n)=(2n-2)!/(n!(n-1)!)
ma non è semplice verificarlo per induzione usando la relazione ricorsiva sopra!





Cavia

[Principe2]

sembra proprio che le nostre due formule si equivalgano:
ti faccio un esempio:

con la tua:

p(7)=p(1)p(6)+p(2)p(5)+p(3)p(4)+p(4)p(3)+p(5)p(2)+p(6)p(1)

sostituiamo p(1)=1,p(2)=1 si ha:

p(7)=2p(6)+2p(5)+2p(3)p(4) che è la mia

inutile dire che la tua è molto più elegante; la mia è un gran casino... però almeno pare giusta
un'altra cosa: avevo posto p(k)=0 per k<=2; ebbene ho copiato male dal foglio; non c'entra niente!!

ora tocca provare a dimostrare quella coi fattoriali

ciao, ubermensch