# Combinatoric homework like question

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.

-
It looks like you are allowing placing a subset of the numbers. If you place all numbers, you get 1, 2, 5, 14, 42... If you place a subset of a a particular size $s$, then you multiply by the number of choices for the subset $K \choose s$ and the number of choices for the location $N \choose s$. –  Douglas Zare Apr 2 '11 at 21:08
If you want to be able to place multiple copies of a number, then you have a harder combinatorial problem, but one which might be solved by generalizations of the Robinson-Schensted correspondence. –  Douglas Zare Apr 2 '11 at 21:10
If you can solve the problem without blanks, then you can express the count with blanks as a sum over the choices for where to put the blanks. So, try not allowing any blanks first. That will have a greater chance to be in the Encyclopedia. –  Douglas Zare Apr 2 '11 at 21:20
Btw, with no blanks or repetitions, the counts are called the Catalan numbers. –  Douglas Zare Apr 2 '11 at 21:20
add comment

## 1 Answer

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.

-
add comment