I have an arbitrary long list that looks as following: {a,b,c,d,e,f}
Now I would like to create ordered combinations in this list that need to have a length of 3, 4 or 5. To clarify, ordered combinations of length 3 are: {(a,b,c), ((b,c,d), (c,d,e), (d,e,f)}
and length 4 are {(a,b,c,d), (b,c,d,e), (c,d,e,f)}
and at last we obtain {(a,b,c,d,e), (b,c,d,e,f)}
for length 5. The amount of elements in these three created lists is equal to 4+3+2.
If I wouldn't have set this restriction, all ordered pairs would have the length of n+n-1 ... 1+0
(with n being the length of the original list).
Now the question that I have is:
How could I express these restricted combinations (from length 3,4 or 5) of a list in mathematical terms? And does this have a name?
Thanks in advance, any help is appreciated.
Best Answer
If your original list has $n$ elements there are $n-k+1$ "ordered combinations" of length $k$ since such a combination can start at any element between the $1$st and the $(n-k)$th. So you have to sum the numbers $n-k+1$ for the values of $k$ in your range.
If that range consists of consecutive numbers (like your $3,4,5$) that's easy, because the numbers of your combinations will be consecutive integers too, in reverse order. In your example $n=6$ so you want to add $$6-3+1,\quad 6-4+1, \quad6-5+1$$ which is $$ 4,3,2. $$
Now the sum of the numbers from $1$ to $A$ is $$ \frac{A(A+1)}{2} $$ so he sum of the numbers from $B+1$ to $A$ is $$ \frac{A(A+1)}{2} - \frac{B(B+1)}{2} \ . $$ In your example you want the sum from $2$ to $4$ so $B=1$ and $A=4$ and you get $$ \frac{4(4+1)}{2} - \frac{1(1+1)}{2} = 10 - 1 = 9. $$
PS Your "ordered combinations" don't have any particular name. The only binomial coefficient you need is $\binom{m}{2}$ for finding the two triangular numbers to subtract.