2
$\begingroup$

I am interested in counting the following. How many words using $n-1$ copies of $u$ and ${n \choose 2} - n+1$ copies of $d$ begin with $uu$ and, in general, the $k^{th}$ $u$ is among the first ${k \choose 2} + 1$ letters in the word?

This is a generalization of a Dyck path. I need to start at the origin, end at $(n-1,2(n-1)-{n \choose 2})$, and always stay above the corresponding curve.

I'm looking for a reference or an argument that gives a formula analogous to the Catalan numbers. I can write down the answer as a messy sum.

Thanks!

$\endgroup$
1
  • $\begingroup$ It would just be more fun to read this question if you were giving some background on why you consider such paths. $\endgroup$ Nov 26, 2014 at 19:14

1 Answer 1

3
$\begingroup$

(After the original question was edited). Now this is simply http://oeis.org/A107877. Your words are in one-to-one correspondence to those mentioned in a comment by David Scambler. To come from your words to his, you need to add $d$ after each $u$, and then to replace $k$th $u$ by $k$ consecutive $u$'s.

$\endgroup$
1
  • $\begingroup$ Thanks a lot!! I noticed a slight mistake in my question. I meant that I want $n-1$ copies of $u$. But this doesn't seem to change your solution much, as now I simply know that the final string of letters must be $d$s. Thanks again! $\endgroup$
    – user160371
    Nov 26, 2014 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.