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
    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$.2011-04-02
  • 0
    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.2011-04-02
  • 0
    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.2011-04-02
  • 0
    Btw, with no blanks or repetitions, the counts are called the Catalan numbers.2011-04-02

1 Answers 1