2
$\begingroup$

I've written an algorithm which gives me all the possible ordered sequences of n numbers in k "cells", with k < n.

such as, for k = 3 and n = 5, I have:

an ordered sequence which will be put in cells : {1, 2, 3, 4, 5} and 3 cells in which this sequence has to remain ordered.

This gives me 10 possible ordered sequences: {1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4} {2, 3, 5} {2, 4, 5} {3, 4, 5}

The algorithm works fine (I've tested it many times), but I can't find a formula to determine how many sequences it can produce. I've searched on many websites but all I find is about permutations, or combinations, and this is not exactly what I'm doing here...

I have some results here:

Results of the algorithm

  • On the X axis, the number of "cells" (k)
  • On the Y axis, the number of numbers (n)
  • In the table, the number of sequences generated
  • In grey the number of sequences divided by n (thought this could help)

Anyone know how to calculate the number of possible ordered sequences given this conditions?

Sorry if this isn't very clear, I'm not so good with math English.

$\endgroup$
1
$\begingroup$

This is a truncated form of Pascal's triangle and you are choosing $k$ from $n$ items. The general term is $${n \choose k} = \dfrac{n!}{k!\,(n-k)!}.$$

$\endgroup$
1
  • $\begingroup$ Thanks a lot!!! It seemed familiar but I couldn't find what it was, should have been more serious about maths at school! (and I've been on this since yesterday.....) $\endgroup$
    – ppetrov
    Nov 11 '15 at 13:31

Your Answer

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

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