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 KilpatrickNov 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$– Mikhail KostenNov 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
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.