1

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.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
mroWsymaS
  • 115

1 Answers1

0

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.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • Woah! Thanks a lot, I understand almost everything. Very clear and you answer exactly what I asked. Thanks! Could you maybe elaborate a bit further on the last PS? I just do not understand that part perfectly. – mroWsymaS Mar 14 '19 at 13:07
  • I belief I understand after a while. – mroWsymaS Mar 14 '19 at 13:39
  • @mroWsymaS Glad to help. You can accept the answer (check box) and vote it up. The PS says first that these selections from a list have no special mathematical name. In Python they would be slices: https://www.programiz.com/python-programming/methods/built-in/slice . I added the second part saying that binomial coeffecients aren't really part of the solution only because you included them in the question title. $N(N+1)/2$ just happens to be both the sum of the numbers from $1$ to $N$ and the number of ways to choose a pair from an $N-1$ element set. – Ethan Bolker Mar 14 '19 at 13:43
  • Accepted your answer! Thanks a lot (again). – mroWsymaS Mar 15 '19 at 19:09