I barili di balsamo

[axpgn]

Un mercante arabo possedeva dieci barili di un prezioso balsamo; essi erano numerati dall'uno al dieci: il barile numero uno conteneva la qualità migliore mentre il numero dieci la meno pregiata.
Il mercante li teneva disposti in due file da cinque, una sovrapposta all'altra ma aveva una regola ferrea: ogni barile non poteva essere posto sopra ad un altro di qualità migliore e neppure avere accanto alla sua destra uno più pregiato.
Un paio di esempi per chiarire:

$|(1,2,3,4,5),(6,7,8,9,10)|\ \ \ \ \ $ e $\ \ \ \ \ |(1,2,5,7,8),(3,4,6,9,10)|$

In quanti modi diversi il mercante arabo poteva disporre i suoi barili di balsamo?

Cordialmente, Alex

[orsoulx]

42

Ciao
B.

[nino_12]

Dovrebbe essere:
2 barili ------> 1 modo
4 barili ------> 2 modi
6 barili ------> 5 modi
8 barili ------> 14 modi

Se non ho sbagliato, si tratta dei numeri di Catalan.
Nel caso del quiz:
$C(n) = (C(n,n/2))/(n/2+1) $

Per $n=10$ ------> $(C(10,5))/6 = 42 $

Ciao
Nino

[axpgn]

Bravi!

Si, la formula è quella e si può riscrivere in questo modo $1/(n+1)((2n),(n))$ dove $2n$ rappresenta il numero totale di barili e sono proprio i numeri di Catalan.

Cordialmente, Alex

[orsoulx]

@axpgn
hai la dimostrazione che sia la successione riportata ?
Anche pensiero profondo ha dato la medesima risposta.
Ciao
B.

[Pachisi]

Si può creare una biiezione tra il numero di modi di ordinare $2n$ barili di balsamo e il numero di stringhe di lunghezza $2n$ che consistono di $n$ $X$ e $n$ $Y$ tali che se partiamo da sinistra, il numero di $Y$ è sempre minore o uguale del numero di $X$. Quest'ultime si chiamano parole di Dyck ed è noto che il loro numero è dato dai numeri di Catalan.
Ora, ritorniamo ai barili di balsamo. La nostra tabella avrà la forma $|(a_11,a_12,...,a_{1n}),(a_21,a_22,...,a_{2n})|\ \ \ \ \ $. Sia $a_{1i}=X$ e $a_{2i}=Y$ con $i=1,2,...,n$. Ora, leggiamo la nostra tabella in ordine ascendente. Per esempio, la tabella $ \ \ \ \ \ |(1,2,5,7,8),(3,4,6,9,10)| $ è rappresentata dalla parola $XXYYXYXXYY$. Ora, visto che $a_{11}=X$ è sempre il primo numero, e $a_{2n}=Y$ è sempre l'ultimo, la nostra parola avrà la forma $X.....Y$. Inoltre, visto che i numeri (che rappresentano i barili) sono sempre crescenti nelle due righe (a destra il balsamo deve essere meno pregiato), ma anche nelle colonne (il balsamo posto sotto ad un altro è meno pregiato), il numero di $Y$ in un momento qualsiasi dovrà essere minore o uguale del numero di $X$. Dunque, ogni tabella può essere rappresentata da una parola di Dyck. Visto che si hanno $C_n$ modi di creare una parola di Dyck di lunghezza $2n$, si avranno anche $C_n$ modi di ordinare $2n$ barili di balsamo.

[orsoulx]

Grazie Pachisi, sei veramente un mostro (nel senso buono del termine). Io ero arrivato solo a generare il numero di disposizioni possibili in maniera iterativa con un triangolo (vagamente tartagliesco). I risultati coincidono con i numeri di Catalan, ma da questo a dimostrarlo....
Ciao
B.

[Pachisi]

Grazie ancora per il complimento, comunque anche tu non scherzi (Tommy e il porcellino)...

[axpgn]

@orsoulx
No, non ho la dimostrazione; ho provato diversi approcci tra cui da uno di essi ho ricavato che il numero di modi totale è uguale al numero di modi in cui posso disporre la riga superiore e che questi modi sono in numero minore di $((2n-2),(n-1))$ se il numero totale di barili è $2n$.
Proseguendo posso dire che in ognuna di queste disposizioni della riga superiore lunghe $n-1$ (tolto il primo che è sempre $1$) i numeri "alti" (cioè superiori a $n$) sono al massimo $(n-1)/2$ e questo fatto si ripete in modo ricorsivo nelle "sottostringhe"; in questo modo ho potuto calcolare la soluzione (e di altri casi) ma non una formula.

@Pachisi
Ad una prima lettura pensavo di aver compreso tutto ma più la rileggevo e meno capivo ...
Ho alcuni dubbi, anzi parecchi ... ... tanto per iniziare $X$ e $Y$ sono simboli o numeri? cosa significa "... il numero di $Y$ è sempre minore o uguale del numero di $X$ ..." ? E quando dici "... leggiamo la nostra tabella in ordine ascendente ..." l'ordine qual è ? Perché la parola $XXYYXYXXYY$ non riesco proprio a "estrarla" da quella tabella ...

EDIT: forse ho capito qualcosa ...
- $X$ e $Y$ sono simboli come pensavo
- "il numero di $Y$ è sempre minore o uguale del numero di $X$" è riferito alle parole di Dick non alle disposizioni e quando parli di numero intendi la "quantità" di $X$ e di $Y$, giusto? Ma soprattutto quando dici "è sempre minore" intendi dire che man mano che componiamo la parola da sinistra non avremo MAI un numero di $Y$ superiore alle $X$; ho inteso giusto?
- per ordine "ascendente" intendi il numero identificativo del barile (e quindi ho capito come hai costruito la parola)

Credo che adesso mi torni tutto ...

Cordialmente, Alex

[Pachisi]

Si, giusto
Scusa per non essere stato abbastanza chiaro...

[orsoulx]

Il triangolo che ho usato è il seguente:

\( \begin{matrix} 1 & & & & \\ 1 & 1 & & & \\ 1 & 2 & 2 & & \\ 1 & 3 & 5 & 5 & \\ 1 & 4 & 9 & 14 & 14 \end{matrix} \).
A parte la prima, ogni nuova riga si ottiene dalla precedente iniziando con un 1 e procedendo verso destra sommando i due valori che si trovano sopra e a sinistra della posizione considerata; l'ultimo numero di ogni riga è uguale al penultimo.
Non è difficile dimostrare che l'n-esima riga così costruita fornisce, ordinatamente, il numero di disposizioni lecite di 2n barili aventi nella parte terminale della fila inferiore esattamente m valori consecutivi con m che va da n a 1 (numero di parole di Dyck di 2n simboli terminanti con esattamente m Y).
La somma dei valori riportati dell'n-esima riga (uguale ai due numeri finali della (n+1)-esima) è allora, grazie a Pachisi, l'n-esimo numero di Catalan.

Ciao
B.

[nino_12]

Dico anche la mia...

I numeri di Catalan si possono anche ricavare dalla verticale centrale del triangolo di Tartaglia, dividendo i valori per 1, 2, 3, ....

.......... 1
......1...2...1
...1...3....3....1
1...4....6....4....1

1/1
2/2
6/3
20/4
....