1
$\begingroup$

I have a $2 \times n$ chessboard where numbers are increasing from left to right and top to bottom. I want to show that the number of arrangements is the $nth$ catalan number.

for example one such arrangement with n = 3 could be:

$\pmatrix{1 3 4\\ 256}$

I think it would be easiest to use: $C_n = \frac{1}{n+1} {2n\choose n}$

What I see is that the first entry must be $1$ and the last entry must be $2n$ Also, if one row is complete (and valid) it completely determines the other row. So it suffices to satisfy one row. Thus we must do $2n\choose n$ to fill a row. However, a bunch of these combinations would not satisfy these conditions. What is the reason to divide by $n+1$?

I tried to use the sequence of $(n+1)$ $1$'s and $(n-1)$ $-1$'s trick (matching parenthesis example that is counted by catalan) but could not establish the proper bijection.

All help is greatly appreciated.

$\endgroup$
1
  • $\begingroup$ The objects you describe are called standard Young tableaux of shape $(n,n)$ (their entries are $1,2,\ldots,2n$, which you forgot to mention). $\endgroup$ Apr 1 '13 at 8:58
3
$\begingroup$

HINT: Given a properly filled in $2\times n$ chessboard, define a string $a_1,\dots,a_{2n}$ by setting $a_k=1$ if $k$ is in the top row of the chessboard, and $a_k=-1$ if $k$ is in the bottom row. For example, your board $\pmatrix{1 3 4\\ 256}$ generates the string $1,-1,1,1,-1,-1$.

Added: You may want to consider Marc van Leeuwen’s answer together with mine; the terminology is a bit different, but we’re describing the same bijection from opposite ends, so to speak.

$\endgroup$
1
  • $\begingroup$ Very pretty question and solution! $\endgroup$ Apr 1 '13 at 20:54
2
$\begingroup$

Given a matching string of $2n$ parentheses, if you consider the first $k$ symbols and count opening and closing parentheses among them, the two counts $(a,b)$ you find must satisfy $a\geq b$ (there are at least as many opening as closing parentheses). Now one can define a Young tableau corresponding to the string in which for any $k$ the numbers $\{1,\ldots,k\}$ fill a shape $(a,b)$ (the first $a$ positions of the first row, and the first $b$ of the second row). Supposing the numbers up to $k-1$ have already been placed, there there is a unique position for $k$, which is in the first row if symbol $k$ is an opening parenthesis, and in the second row if it is a closing parenthesis. This gives a bijection.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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