4
$\begingroup$

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

  1. Which topics do I need to know to be able to solve this question?
  2. 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

Number of ways to arrange people in two rows, so that nobody stands behind or to the right of someone taller

How many ways to line up n objects with distinct heights

$\endgroup$
  • $\begingroup$ "increasing numbers" is a bit misleading -- one often looks at successive numbers in a permutation, so people may tend to take this to mean increases from one number to the next -- it seems that you mean increases from one "high water mark" to the next (and that the first number is always counted as an increase). $\endgroup$ – joriki Jul 5 '16 at 15:53
  • $\begingroup$ @joriki I know I couldn't phrase it well. Also the title is a little off. I'm open to suggestions. $\endgroup$ – Taylan Jul 5 '16 at 16:01
  • $\begingroup$ Hmm might be recursive. f(n,x,2) = nf((n-1),x,1) = n[(1+.... + (n-2))]f((n-2),(x-1), 1) etc. something can be done by that but it'd be complicated. $\endgroup$ – fleablood Jul 5 '16 at 17:52
  • $\begingroup$ I just found out that the solution has something to do with the Stirling Numbers but not sure what. $\endgroup$ – Taylan Jul 6 '16 at 16:57
  • $\begingroup$ You should be able to attack this using recursion. The tallest stake will divide the problem into two independent subproblems. $\endgroup$ – Greg Martin Jul 6 '16 at 17:19

Your Answer

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

Browse other questions tagged or ask your own question.