3
$\begingroup$

I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end.

$$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i \binom{n-i}{k-1}}{ \displaystyle{n \choose k}}$$

Is there any way to simplify the numerator so that the whole expression simplifies into a nice closed formula? A combinatorial approach would be greatly appreciated.

$\endgroup$
  • $\begingroup$ A quick (but perhaps not too helpful) simplification of the numerator, eliminating the zero terms: $$\sum_{i=1}^{n-k+1} i\binom{n-i}{k-1}$$ $\endgroup$ – Zubin Mukerjee Jan 6 '15 at 6:02
  • 1
    $\begingroup$ @ZubinMukerjee: That is not equivalent, the terms with $n<i\leq n+k-1$ are not zero. But on the other hand it looks like this is probably what OP wanted to write in the first place. $\endgroup$ – Marc van Leeuwen Jan 6 '15 at 6:27
  • $\begingroup$ @MarcvanLeeuwen Isn't the convention for positive integers $a,b$ this? $$\binom{-a}{b}=0$$ $\endgroup$ – Zubin Mukerjee Jan 6 '15 at 13:56
  • 2
    $\begingroup$ @ZubinMukerjee: No it isn't. Instead $$ \binom{-a}b=\frac{(-a)(-a-1)\ldots(-a-b+1)}{b!} = (-1)^b\binom{a+b-1}b$$ which is nonzero when $a>0$. $\endgroup$ – Marc van Leeuwen Jan 6 '15 at 14:26
  • $\begingroup$ @MarcvanLeeuwen This is mind-blowing, and makes so much sense! Does it correspond to an extension of Pascal's triangle above the first row? It reminds me of when I first realized that you could continue the Fibonacci numbers in the other direction for $$\dots, -5,3,-2,1,-1,0,1,1,2,3,5, \dots$$ $\endgroup$ – Zubin Mukerjee Jan 6 '15 at 15:42
5
$\begingroup$

Consider the number of ordered pairs $(a, S)$ such that $S$ is a $k$-element subset of $\{1,2, \dots, n\}$ and $a \le \min S$.

One way of counting:

Fix $\min S$.

If $\min S = i$, the number of sets = $\binom{n-i}{k-1}$ (choose $k-1$ from $\{i+1, i+2, \dots, n\}$. For each such $S$, you have $i$ possibilities for $a$.

Thus the number of $(a,S)$ pairs = $\sum_{i=1}^{n-k+1} i\binom{n-i}{k-1}$

Now count that differently: either $a = \min S$ or not.

If $a \neq \min S$, then the number is $\binom{n}{k+1}$ (pick $k+1$ elements basically)

If $a = \min S$, the number is $\binom{n}{k}$.

Thus the numerator you seek is $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$

So your expression simplifies to $\dfrac{n+1}{k+1}$.

(Note, I have assumed you wanted the sum upto $n-k+1$)

$\endgroup$
  • $\begingroup$ You don't seem to account for the factor $i$ in the summand. $\endgroup$ – Marc van Leeuwen Jan 6 '15 at 6:14
  • $\begingroup$ @MarcvanLeeuwen: You, are right! I missed the i. $\endgroup$ – Aryabhata Jan 6 '15 at 6:16
  • $\begingroup$ @MarcvanLeeuwen: I attempted to fix it. Thanks for pointing out the mistake. $\endgroup$ – Aryabhata Jan 6 '15 at 6:27
  • $\begingroup$ Aryabhata : Thank you very much. Can you please put the bounds on the summation symbol to make it more clear? $\endgroup$ – aghost Jan 6 '15 at 16:39
6
$\begingroup$

Write the numerator (after replacing the upper bound by $n$ or $n-k+1$, which I suppose was intended) as $\sum_{i=0}^n\binom i1\binom{n-i}{k-1}$. This summation then gives $\binom{n+1}{k+1}$ because of the more general formula $$ \sum_{i=0}^k\binom im\binom{k-i}n=\binom{k+1}{m+n+1} $$ that I mentioned with a combinatorial proof in this answer; put $(k,m,n):=(n,1,k-1)$ to get the special case needed here.

The proof specialises for this special case $\sum_{i=0}^n\binom i1\binom{n-i}{k-1}=\binom{n+1}{k+1}$ as follows. Locate, in the subset of $k+1$ elements out of $n+1$ for the right hand side, the second-smallest element, and let $i$ be the number of elements strictly smaller than that element. Then $\binom i1$ choices remain for the smallest element, and $\binom{n-i}{k-1}$ choices for the set of $k-1$ larger elements, and all possibilities are counted by the left hand side.

All in all your formula simplifies to $\left.\binom{n+1}{k+1}\right/\binom nk=\frac{n+1}{k+1}$.

$\endgroup$
  • $\begingroup$ See also this question and the list of questions I linked to in the comments below that question. $\endgroup$ – Marc van Leeuwen Jan 6 '15 at 14:41
0
$\begingroup$

I am very bad in combinatorics (as in so many other areas) so I shall not prove anything.

Intrigued by the expression (almost by the upper bound for the summation) and using a CAS, what was found is that $$\sum_{i=1}^{n+k-1} i \binom{n-i}{k-1}=\frac{(k-1) \binom{-k}{k-1} \Big(k (k+n-1)+n+1\Big)+n (n+1) \binom{n-1}{k-1}}{k (k+1)}$$ where appears a generalized binomial coefficient $\binom{-k}{k-1}$.

Hoping this could be of some use.

$\endgroup$
0
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{{\ds{\sum_{j\ =\ 1}^{n\ +\ k\ -\ 1}j{n - j \choose k - 1}}\over \ds{n \choose k}}:\ {\large ?}.\qquad}$ Lets $\ds{\quad n + k - 1 \equiv m}$.


\begin{align}&\color{#66f}{\large\sum_{j\ =\ 1}^{m}j{n - j \choose k - 1}} =\sum_{j\ =\ 1}^{m}j\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{n - j} \over z^{k}} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{n} \over z^{k}}\sum_{j\ =\ 1}^{m}j\pars{1 \over z + 1}^{j} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{n} \over z^{k}}\bracks{% {1 + z \over z^{2}} - {\pars{1 + z}^{-m + 1} \over z^{2}} -m\,{\pars{1 + z}^{-m} \over z}}\,{\dd z \over 2\pi\ic} \\[5mm]&={n + 1 \choose k + 1} - {n - m + 1 \choose k + 1} - m{n - m \choose k} \\[5mm]&=\color{#66f}{\large{n + 1 \choose k + 1} - {2 - k \choose k + 1} -\pars{n + k - 1}{1 - k \choose k}}\,,\qquad \boxed{\ds{\quad n + k \geq 2\quad}} \end{align}

$\endgroup$

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.