Parole di Dyck

[3m0o]

Dato un alfabeto con \(n\) lettere \( \mathcal{A} = \{ a_1,a_2,\ldots, a_n\}\), consideriamo una parola finita
costruita su questo alfabeto, i.e. \(w=w_1 w_2 \ldots w_r \), dove \(w_j \in \mathcal{A} \) per ogni \(1 \leq j \leq r \). Denotiamo con \(\ell(w)\) la lunghezza della parola \(w\). Denotiamo con \( N_j(w) \) il numero di occorrenze di \(a_j\) nella parola \(w\), ovvero \[N_j(w) = \sum_{k=1}^{\ell(w)} \mathbf{1}_{ \{a_j\}} (w_k). \]

Diciamo che una parola \(w=w_1 w_2 \ldots w_{\ell(w)} \) è \(n\)-Dyck di lunghezza \(L\) se le seguenti proprietà sono entrambe verificate:

1) Abbiamo che \( \ell(w)=L\) e abbiamo che \( N_1(w)=N_2(w) =\ldots = N_n(w) = \frac{L}{ n } \).

2) Per ogni \( 1 \leq \ell \leq \ell(w) \) abbiamo che \( N_j\left( w_1 w_2 \ldots w_{\ell} \right) \geq N_k \left( w_1 w_2 \ldots w_{\ell} \right) \) per ogni \(1 \leq j \leq k \leq n \).

Ad esempio con \(n=2\) ed \( \ell(w)=4\) abbiamo \(w= a_1 a_1 a_2 a_2 \) è \(2\)-Dyck di lunghezza \(4\) mentre invece la parola \(w=a_1 a_2 a_2 a_1 \) non lo è!

Denotiamo con \(D(n,L) \) la cardinalità del insieme delle parole su \( \mathcal{A}\) che sono \( n\)-Dyck di lunghezza \( L\).

Quante sono le parole che sono \( n\)-Dyck di lunghezza \( L\), in altre parole quanto vale \( D(n,L) \)?