1
$\begingroup$

The problem is:

In how many ways can numbers from [1-K] be placed in a row of N elements that there is not a triple a, b, c where a > b > c and pos(a) < pos(b) < pos(c) in a above mentioned row.

I wrote a small program that calculates this using dynamic programming, but I wonder if there is a simple formula.

Thanks.

edit: No luck with the OnLine Encyclopedia, but thanks, it looks like a great tool.

Here are the first 10 numbers in the sequence for K=N=1..10:

2, 5, 27, 191, 1373, 9605, 65509, 438835, 905761, 19106231

edit2:

yep, number repetition is allowed.

  • 0
    Btw, with no blanks or repetitions, the counts are called the Catalan numbers.2011-04-02

1 Answers 1

3

The standard method for approaching such problems starts as follows:

1) Try to make the problem as simple as possible. Let $K=N$ instead of having an extra factor of $N \choose K$.

2) Compute the first few values, at least the first $4$.

3) Go to Sloane's Online Encyclopedia of Integer Sequences, and search for that sequence.

Since you have written a program which can calculate the first few values, please report the results.

If the sequence is not in the Encyclopedia, or it is in there but there is no clear connection between those descriptions and yours, then you probably have to do some work. In this case, you should find that it is a very well-known sequence.