Partial permutation of time sequence data that keep order of events

Question

Suppose you have sequence S of N elements that are descending ordered by time. How many ways can you take K element subsets from S preserving time descending ordering?

example for sequence S={A,B,C,D,E,F}

k=2
subsequences=[AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF, DE, DF, EF]
result=15

Wrong sequences (not descending ordered by time) are BA, CA, DA, DC and so on.

k=3
subsequences=[ABC, ABD, ..., ACD, ACE, ..., AEF, ..., DEF]
result=(n-2)+(n-3)+(n-4)+(n-5)    # AB_ + AC_ + AD_ + AE_ 
            +(n-3)+(n-4)+(n-5)    #     + BC_ + BD_ + BE_
                  +(n-4)+(n-5)    #.          + CD_ + CE_
                        +(n-5)    #                 + DE_
      =4(n-5)+3(n-4)+2(n-4)+(n-2)
      =20

I have tried for k=4 but I don't see any pattern and it seems to be so many possible results. I have tried with some variations of permutation and by trying to write the formula down, but I can't get it.

Target is to calculate for example how many 10 element subsequences can you get from 200 element sequence.

I will be grateful for any help!

Answer 1

You get ${N \choose k}$ such sequences, because that is the number of $k$-element subsets of an $N$-element set. Each subset corresponds to just 1 order preserving sequence: Just order the elements in the subset as you require them to be 'right'.