1
$\begingroup$

Suppose I have a sequence like A B C D E F G H I J I am finding total sub-sequences of even length such that they always have mid elements from index (4 to 6) ie. D to F assuming 1 based indexing.

So my approach is :

For D E to be mid element: $\binom{3}{1}$ $\binom{5}{1}$ + $\binom{3}{2}$ $\binom{5}{2}$ +$\binom{3}{3}$ $\binom{5}{3}$, as we can choose 1,2,3 elements from A B C and simultaneously 1,2,3 elements from F G H I J.

Similarly, for pair E F to be mid element : $\binom{4}{1}$ $\binom{4}{1}$ + $\binom{4}{2}$ $\binom{4}{2}$+ $\binom{4}{3}$ $\binom{4}{3}$ + $\binom{4}{4}$ $\binom{4}{4}$

Similarly, for pair D F to be mid element: $\binom{3}{1}$ $\binom{4}{1}$+$\binom{3}{2}$ $\binom{4}{2}$+$\binom{3}{3}$ $\binom{4}{3}$

Clearly answer will be sum of above terms.Can this result be generalised for a sequence of length n and i and j where i and j are start and end indices from where we choose the middle two elements?

$\endgroup$

1 Answer 1

1
$\begingroup$

First, your counting seems to forget the subsequences $[D,E]$, $[E,F]$, and $[D,F]$. The terms $\binom{3}{0}\binom{5}{0}$, $\binom{4}{0}\binom{4}{0}$, and $\binom{3}{0}\binom{4}{0}$ have been omitted.

This problem seems to be similar to the problem (here) I answered a minute ago, but with slightly different phrasing and constraints.

Making the appropriate changes:

$$ \sum^{(j-i-1)}_{x=0} \sum^{(j-i-1-x)}_{y=0} \binom{(n-j+x)+(i-1+y)}{(n-j+x)} $$

$\endgroup$

You must log in to answer this question.