Medians which lie in sequence of even length.

Question

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.

Answer 1

Reposing the answer now that the contest has ended

---

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.