Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to find out the average case analysis of median of 3 - quick select. The recurrence relation is
\begin{equation} C_{n,j} = 1 + \sum_{k=1}^{j-1}\pi_{n,k}C_{n-k,j-k} + \sum_{k=j+1}^{n} \pi_{n,k}C_{k-1,j} \end{equation} where $$\pi_{n,k} = \frac{(n-k)(k-1)}{{{n}\choose{3}}}.$$

First we consider $$C_j(x) = \sum_{n} C_{n,j}x^n.$$ Multiplying by ${{n}\choose{3}}\; x^{n-3}$ and summing over $n$ on both sides $$\sum_{n\geq 3}{{n}\choose{3}} x^{n-3}\; C_{n,j} =\sum_{n\geq 3}{{n}\choose{3}}(1+\sum_{k=1}^{j-1}\pi_{n,k}C_{n-k,j-k} + \sum_{k=j+1}^{n} \pi_{n,k}C_{k-1,j} )\; x^{n-3} $$ We expand out the binary coefficients, since ${n\choose 3}=n(n-1)(n-2)/6$, so we get $$\begin{aligned}\frac{1}{6} &\; \sum_{n\geq 3}n(n-1)(n-2) \;x^{n-3}\; C_{n,j}\\ &=\sum_{n\geq 3} \frac{n(n-1)(n-2)}{6} x^{n-3} +\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} \\ &\qquad+\sum_{n\geq 3} \sum_{k=j+1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3}\end{aligned} $$ But look, the left hand side is precisely $$\frac{1}{6} \sum_{n\geq 3}n(n-1)(n-2) \;x^{n-3}\; C_{n,j}=\frac{C^{'''}_{j}(x)}{6}$$ so we have $$ \begin{aligned} 1/6 C_j^{'''}(x) &= \sum_{n\geq 3} n(n-1)(n-2)/6\; x^{n-3} +\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} \\ &\qquad+\sum_{n\geq 3} \sum_{k=j+1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} \\ &= 1/6\; \sum_{n\geq 3} n(n-1)(n-2)\; x^{n-3} \rightarrow (1)\\ &\qquad +\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} \rightarrow (2)\\ &\qquad +\sum_{n\geq 3} \sum_{k=j+1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} \rightarrow (3) \end{aligned}$$

Lets solve each parts named $(1), (2)$ and $(3)$ separately. $$\tag{1} \sum_{n\geq 3} n(n-1)(n-2)\; x^{n-3} = \frac{d^4}{dx^4}\sum_{n\geq 0} x^{n} = \frac{d^4}{dx^4} (\frac{1}{(1-x)}) = \frac{6}{(1-x)^4} $$

The second term (2) $$\tag{2} \sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} = $$ Since, $C_j(x) = \sum C_{n,j}x^n$ we have $C_{j-k}(x) = \sum C_{n,j-k}x^n$ or $C_{j-k}(x) = \sum C_{n-k,j-k}x^{n-k}$
This term,$ \sum_{n\geq 3}(n-k)C_{n-k,j-k}x^{n-3} $ can be rewritten as $\sum_{n\geq 3}(n-k)C_{n-k,j-k}x^{n-k}\;x^{k-3} = x\; C_{j-k}^{'}\;x^{k-3} =C_{j-k}^{'}\;x^{k-2}$
$\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} = \sum_{k=1}^{j-1} (k-1)x^{k-2}C_{j-k}^{'}\;$

The third term (3) is $$\begin{aligned} \sum_{n\geq 3} &\sum_{k=j+1}^{n}& (k-1)(n-k)C_{k-1,j}\; x^{n-3} \\ &= \sum_{n\geq 3} \sum_{k=1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} \;\rightarrow (3.1)\\ &\qquad - \sum_{n\geq 3} \sum_{k=1}^{j} (k-1)(n-k)C_{k-1,j}\; x^{n-3}\; \rightarrow (3.2)\end{aligned}$$ We have $$\tag{3.1} \sum_{n\geq 3} \sum_{k=1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} = \sum_{n\geq 2} \sum_{k=1}^{n} (k-1)(n+1-k)C_{k-1,j}\; x^{n-2}$$ Here, $a = k-1, b = n+1 -k ;\;a+b = n $
$=1/x^2\;\sum_{n\geq 0} \sum_{a+b=n} (a)(b)C_{b,j}\; x^{n} = 1/x^2 \;[\sum_{a\geq 0} a\;x^a] \;[\sum_{b\geq 0} bC_{b,j}\;x^b ]$
$= 1/x^2 \; x \frac{d}{dx} \frac{1}{(1-x)} \; x \; \frac{d}{dx}\sum_{b=1}^{\infty} C_{b,j} \;x^b $
Since, $C_{b,j} x^b = C_j$
hence, $ = \frac{C^{'}}{(1-x)^2} $

{3.2}: How can we solve this? $\sum_{n\geq 3} \sum_{k=1}^{j} (k-1)(n-k)C_{k-1,j}\; x^{n-3} = $

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.