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.

  • $\begingroup$ 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? $\endgroup$ – Joey Kilpatrick Nov 5 '18 at 20:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Mikhail Kosten Nov 5 '18 at 20:52
  • 1
    $\begingroup$ This problem was taken from a contest that closed 12 November 2018. $\endgroup$ – quid Nov 13 '18 at 8:23

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.