# Medians which lie in sequence of even length.

Given a sequence of numbers say [1,2,2,2,4,3,3] from this sequence how many sub-sequences in order can be formed in which the median will lie in the sub-sequences itself. I have found that for all sequences of odd length it will hold true. Therefore total number of sequences with odd length are nC1+nC3+nC5+...+nCn for current array n=7. Now I have also figured out that all the sequences of length 2 which can be formed are 3C2 + 2C2 i.e C(3,2) + C(2,2) That is it will be only possible if we have both the same in above example it will be [2,2] [2,2] [2,2] [3,3] the elements will be treated different if they are at different indices in sequence. How I will find number of other sequences of length 4,6... and other even length sequences.

• Can you clarify? When you say "in order", do you mean that the subsequences must be non-decreasing? Or just that the indices of the elements must be increasing? – Joey Kilpatrick Nov 5 '18 at 20:45
• I mean to say that the in the sub-sequence the order in which number are present should be followed that is for a sub-sequence Ai,Aj,Ak,Al...., 1<=i<j<k<l<.. and so on where i,j,k,l are positions of numbers in original sequence. – Mikhail Kosten Nov 5 '18 at 20:52
• This problem was taken from a contest that closed 12 November 2018. – quid Nov 13 '18 at 8:23

First note that the problem does not change if we first sort the sequence. So the number of subsequences that contain its own median in the sequence $$[1,2,2,2,4,3,3]$$ is the same as that of $$[1,2,2,2,3,3,4]$$.
Suppose that we had a (sorted) even length subsequence $$a_1,...,a_{2n}$$ that contained its own median. Then the elements $$a_{n}$$ and $$a_{n+1}$$ must be equal. As in your post, you identified that the possibilities in your example for the elements $$a_{n}$$ and $$a_{n+1}$$ were $$[2,2]$$ (with multiplicity $$3$$) and $$[3,3]$$. The only possibilities for the median are those elements that appear multiple times in the array.
For an even length subsequence $$a_n$$, let the possible medians be the set $$\text{med}(a_n)$$. For any element $$a$$ in the sequence, let $$l(a)$$ be the number of elements in the sequence less than $$a$$ and let $$g(a)$$ be the number of elements in the sequence greater than $$a$$. To construct a subsequence from a given $$m\in \text{med}(a_n)$$, then for some $$k\le g(m), l(m)$$, select $$k$$ elements that are less than $$m$$ and $$k$$ elements that are greater than $$m$$, and add them to the subsequence. The number of ways to do this is $$\sum_{m\in \text{med}(a_n)}\left( \sum^{min\{g(m),l(m)\}}_{i=0}\binom{g(m)}{i}\binom{l(m)}{i} \right)$$ However, this solution has a major issue. It assumes that there are always exactly $$2$$ elements in the subsequence equal to the median $$m$$. There must be at least $$2$$, but there could be more. Consider the subsequence $$[1,2,2,2]$$ from the example sequence. To fix this issue, let $$n(m)$$ be the multiplicity of $$m\in \text{med}(a_n)$$, $$\sum_{m\in \text{med}(a_n)}\left( \sum^{(n(m)-2)}_{x=0} \sum^{(n(m)-2-x)}_{y=0} \left( \sum^{min\{g(m)+x,l(m)+y\}}_{i=0}\binom{g(m)+x}{i}\binom{l(m)+y}{i} \right) \right)$$ Using Vandermonde's identity, we can simplify the innermost sum, $$\sum_{m\in \text{med}(a_n)}\left( \sum^{(n(m)-2)}_{x=0} \sum^{(n(m)-2-x)}_{y=0} \binom{(g(m)+x)+(l(m)+y)}{(g(m)+x)} \right)$$ This equals the number of even length subsequences that contain their own median.