Nombre de parenthèses pour un nombre fixe de paires de "()"

Question

Dire que nous aimerions compter le nombre de différentes parenthèses de n paires de crochets mais en ayant un nombre fixe de paires "()". Comment comptons-nous ces parenthèses.

ex: pour n = 3. c'est-à-dire 3 paires de parenthèses, si nous voulons le nombre de parenthèses avec k = 2 paires de "()" le nombre de façons est de 3.

()(())

(())()

(()())

pour n = 4, k = 2, ce sera 6

((()()))

()((()))

(())(())

(()(()))

((()))()

((())())

Answer 1

Je suis assez sûr que ceci est A001263, aussi connu sous le nom de nombres de Narayana, et que la formule est

T(n,k) = C(n-1,k-1) C(n,k-1)/k with 1<=k<=n

Une interprétation de A001263 est que T(n,k) est le nombre de chemins Dyck de longueur n avec exactement k pics, et vous pouvez interpréter chaque étape Dyck comme étant soit ( ou ) et chaque pic comme ().