Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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


yep, number repetition is allowed.

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.