EDIT
I've found a formula to solve this question, but I don't understand the reasoning behind it. Can someone explain this formula?
$s(n - 1, x + y - 2) \times C(x + y - 2, x - 1)$
$s$ being Stirling number of the first kind
$C$ being the combinations
For x, y and n in the example question below:
$s(5 - 1, 2 + 3 - 2) \times C(2 + 3 - 2, 2 - 1) = s(4, 3) \times C(3, 1) = 6 \times 3 = 18$
ORIGINAL POST
I have two main questions about this
- Which topics do I need to know to be able to solve this question?
- How to apply those topics to solve this question?
It is fine if you just know the answer to the 1st question. Just point me in the right direction.
Abstract question
How many ways are there to arrange $n$ distinct numbers so when counted from left to right there are only $x$ increasing numbers (doesn't have to be adjacent) and when counted from right to left there are only $y$ increasing numbers (doesn't have to be adjacent)?
$n \geq 1$
$1 \leq x \leq n$
$1 \leq y \leq n$
Example question
How many ways are there to arrange n=5 stakes of different heights in a line so when looked from the left of the line you can only see x=2 stakes, when looked from the right of the line you can only see y=3 stakes (because they get behind of the long ones)?
Explanation
Let's say stakes are the height of 1cm, 2cm, 3cm, 4cm and 5cm. Arranging the stakes like this 1cm 5cm 2cm 4cm 3cm would meet the given condition. Because if you look from the left of the line you can only see 1cm and 5cm (hence x=2) stakes. If you look from the right of the line you can only see 3cm, 4cm and 5cm (hence y=3) stakes.
The answer of this question is
18
and the possible arrangements are:
1, 5, 2, 4, 3
1, 5, 3, 4, 2
1, 5, 4, 2, 3
2, 1, 5, 4, 3
2, 5, 1, 4, 3
2, 5, 3, 4, 1
2, 5, 4, 1, 3
3, 1, 5, 4, 2
3, 2, 5, 4, 1
3, 5, 1, 4, 2
3, 5, 2, 4, 1
3, 5, 4, 1, 2
4, 1, 5, 3, 2
4, 2, 5, 3, 1
4, 3, 5, 2, 1
4, 5, 1, 3, 2
4, 5, 2, 3, 1
4, 5, 3, 1, 2
Related questions