0
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Nov 5, 2018 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$ Nov 5, 2018 at 20:52
  • 1
    $\begingroup$ This problem was taken from a contest that closed 12 November 2018. $\endgroup$
    – quid
    Nov 13, 2018 at 8:23

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .