0
$\begingroup$

For positive integer N the numbers 1,2,3,...,2N are arranged in two adjacent column. In how many ways they can be arranged so that:

  1. The numbers in each row arranged from smaller to bigger (from left to right)?
  2. The numbers in each of the two column are arranged from smaller to bigger (from bottom to top)?
$\endgroup$
  • 2
    $\begingroup$ Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. $\endgroup$ – Matthew Conroy Jan 1 '14 at 7:59
2
$\begingroup$

Try putting in the numbers in order from $1$ to $2N$. Label it $a$ if it goes into the first column and $b$ if it goes into the second column. Check that you can recover the original solution from the string of labels, so that it forms a bijection. What are the restrictions on the possible strings of labels? It might now be familiar to you.

$\endgroup$
  • 1
    $\begingroup$ @user7777777: Note that I took the question to require both conditions to hold simultaneously, which gives rise to the Catalan numbers, which I would encourage you to try too! You should try to be a bit more precise next time though. =) $\endgroup$ – user21820 Jan 1 '14 at 7:22
1
$\begingroup$

1) You may be interested in Catalan number.

Wiki says

"$C_n$ is the number of standard Young tableaux whose diagram is a 2-by-n rectangle. In other words, it is the number of ways the numbers 1, 2, ..., 2n can be arranged in a 2-by-n rectangle so that each row and each column is increasing. As such, the formula can be derived as a special case of the hook-length formula."

2) All you need is to separate $2N$ numbers into two sets of $N$ numbers. After separating them, you have only one way to arrange the $N$ number of each set.

Edit :

1) Forget Catalan number. Your answer tells us that your question is saying nothing about the arrangement in each colum. Now we can get your answer in the following way :

$$\binom{2N}{2}\cdot \binom{2N-2}{2}\cdots\binom{4}{2}\cdot\binom{2}{2}=\frac{(2N)!}{2^N}.$$

Imagine that you take two numbers as a pair, and take another pair, and so on. You can get the arrangement of yours in this way. Notice that each pair has only one way to arrange them.

2) The answer is $$\binom{2N}{N}$$ because this says that you take $N$ numbers from $2N$ numbers. Once you take $N$ numbers, this set of numbers has only one way to arrange from smaller to bigger. Then, we know the answer is this.

$\endgroup$
  • 1
    $\begingroup$ @user7777777: I added a bit. I hope this helps. $\endgroup$ – mathlove Jan 1 '14 at 7:01
  • 1
    $\begingroup$ Yea I know. I usually try to "talk" rather than just provide a single answer, but it definitely takes time. $\endgroup$ – user21820 Jan 1 '14 at 7:20
  • 1
    $\begingroup$ @user7777777: Imagine that you have $1,2,3,4,5,6$. This is $N=3$ case. First you take two numbers as a pair, for example, $2,5$. How many ways can we arrange these numbers from smaller to larger? The answer is one because we have to arrange them as $2,5.$ So $2$ should be in the left colum and 5 should be in the right colum. Do you get the point? $\endgroup$ – mathlove Jan 1 '14 at 7:32
  • 1
    $\begingroup$ You are right, but we can use $C(,)$ because the number in the left colum is smaller than the number in the right colum. So, once you use C(,), then the place of each number of the pair is automatically decided. $\endgroup$ – mathlove Jan 1 '14 at 7:49
  • 1
    $\begingroup$ @user7777777: Once you take a pair of two number using C(,), the place of each number of the pair is automatically decided because the smaller should be in the left colum and the bigger should be in the right colum. This means that if we want to arrange numbers in each row under the condition of yours, all we need is to select a pair of two numbers using C(,). $\endgroup$ – mathlove Jan 1 '14 at 7:56

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.