Cfrgtkky

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.

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 $min text{med}(a_n)$, then for some $kle 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_{min 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 $min text{med}(a_n)$,
$$
sum_{min 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_{min 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.