Sum of the reciprocals of the binomial coefficients:     Torsten Sillke, 1997
----------------------------------------------------


    P(n)

(A)     = 1/n Sum[ 1/BinomialCoefficient[n-1,k], {k,0,n-1} ]

(B)     = 2^(-n) Sum[ 2^k / k, {k,1,n} ]

(C)     = 2^(-n+1) Sum[ BinomialCoefficient[n,k] / k, {k odd} ]

(D)     = (-I Pi)/2^n - 2 LerchPhi[2, 1, n+1]

It is easy to show for A, B, and C the recursion:

     P(0) = 0 
     P(n) = P(n-1)/2 + 1/n

Table:
   n :   0     1     2     3     4     5     6      7
 P(n):   0     1     1    5/6   2/3   8/15 13/30 151/420

Application of sums of inverses of binomial coefficients are:
  - random splitters  (see V. Strehl)
  - resistance between opposite vertices in a hypercube (see D. Singmaster)
  - (see reference in L. Comtet)
  - probabilistic remark (G. Letac)

Asymptotic expansion (divergent) (see L. Comtet):
  I(n) = Sum[ 1/BinomialCoefficient[n,k], {k,0,n} ] = (n+1) P(n+1)
       = hyper_2f1(1, 1, -n, -1) 
  I(n)/2 = 1 + Sum[ b[p] n^(-p-1), {p >= 0} ] 
  where the integers b[p] have as GF:
  Sum[ b[p] z^p / p!, {p >= 0} ] = (2 - exp(z))^(-2).

    p :  0     1     2     3     4     5     6      7
  b[p]:  1     2     8    44   308  2612 25988 296564


References:
-----------

L. Comtet, 
   Advanced Combinatorics,
   Reidel, Dordrecht, Holland, 1974
   Problem 7.15: Sum of the inverses of the binomial and 
        multinomial coefficients, p 294


R. L. Graham, D. E. Knuth, O. Pataschnik;
   Concrete Mathematics,
   Addison Wessley, Reading (1994) 2nd Ed.
   Exercise 6.100


Toufik Mansour;
   Gamma Function, Beta Function and Combinatorial Identities,
   arXiv:math.CO/0104026v1 (2001)


F. Nedemeyer, Y. Smorodinsky;
   Resistances in the multidimensional cube,
   Quantum 7:1 (Sept./Oct. 1996) 12-15 and 63


A. M. Rockett;
   Sums of the inverses of binomial coefficients,
   The Fibonacci Quarterly 19 (1981) 433-437


D. Singmaster (Problem poser);
   SIAM Review, 22 (1980) 504, (Solution)
   Problem 79-16, Resistances in an n-Dimensional Cube


T. Trif;
   Combinatorial sums and series involving inverses of binomial coefficients,
   The Fibonacci Quarterly 38 (2000) 79-84
   

G. Letac;
   Problemes de probabilites,
   Presses Universitaires de France (1970), p14


Volker Strehl; 
   The average number of splitters in a random permutation,
   personal communications, June 1994, see below
   (analysis of the quicksort algorithm)


B. Sury, 
   Sum of the reciprocals of the binomial coefficients, 
   Europ. J. Combinatorics 14 (1993), 351-353.


It follows the Note of V. Strehl.
- - - - - - - - - - LATEX FILE BEGINS HERE - - - - - - - - - -
\documentclass[a4paper]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
The average number of splitters in a random permutation
\end{center}

If $\sigma = (\sigma_1 , \sigma_2 , \ldots , \sigma_n)$ is a permutation
of $[n] := \{1,2,\ldots,n\}$, then we say that ``$\sigma$ splits at $j$''
or ``$j$ is a splitter in $\sigma$'' if $\sigma_i < \sigma_j$ for
all $j < i$ and $\sigma_j < \sigma_k$ for all $j<k$ (so that necessarily
$s_j=j$). Splitting properties of random permutations
are of interest because of the appearance of that concept
in the {\em quicksort} algorithm (see e.g. section 2.2
in {\sc H. Wilf}s book {\em Algorithms and Complexity}, Prentice-Hall, 1986).

In this note I give a very short proof of the fact that the average number
of splitters in a random permutation of $n$ elements behaves as $2/n$
for large $n$.

\begin{itemize}
\item
Counting splitters is easy: $j$ appears as a splitter in
precisely $(j-1)!\,(n-j)!$ permutations of $[n]$, so that there
is a total of
\[
s_n := \sum_{j=0}^n (j-1)!\,(n-j)! 
= (n-1)! \sum_{j=0}^{n-1} {n-1 \choose j}^{-1}
\]
splitters in permutations of $[n]$.
\item
In order to deal with the reciprocals of binomial coefficients
it is useful to remember (the $\beta$-integral)
\[
{1 \over a+b+1} {a+b \choose a}^{-1} =
\int_{0}^{1} t^a\,(1-t)^b dt
\]
for integers $a,b \geq 0$, which can be proved by simple induction 
using partial integration.
\item
Let us now consider
\[
b_n := \sum_{k=0}^n {n \choose k}^{-1}
= 
(n+1) \int_0^1 \sum_{k=0}^n t^k(1-t)^{n-k} dt
= (n+1)\,a_n
\]
Note that the $a_n$ satisfy a very simple recursion:
\[
a_{n+1} = {a_n \over 2} + {1 \over n+2}~~,~~a_0 = 1
\]
This can be seen as follows:
\begin{eqnarray*}
a_{n+1} - {a_n \over 2} &=&
\int_0^1 t^{n+1} dt +
\int_0^1 
\sum_{k=0}^n \left[ t^k (1-t)^{n+1-k} - {1 \over 2}
t^k (1-t)^{n-k} \right] \, dt 
\\
&=&
{1 \over n+2} +
\int_0^1 \left[
\sum_{k=0}^n t^k (1-t)^{n-k} \right] \left({1 \over 2} -t \right)\,dt
\end{eqnarray*}
where the last integral vanishes for reasons of symmetry!
\item
Now $\overline{s}_n = s_n/n! = b_{n-1} / n = a_{n-1}$, 
the average number of splitters in permutations of $[n]$,
satisfies the recursion
\[
\overline{s}_{n+1} = {\overline{s}_n \over 2} + {1 \over n+1}~~,~~
\overline{s}_1 = 1
\]
from which it follows immediately that 
$n \cdot \overline{s}_n \rightarrow_{n \rightarrow \infty} 2$.
\end{itemize}
\vfill
V. Strehl, june 15, 1994.
\end{document}
- - - - - - - - - - LATEX FILE ENDS HERE - - - - - - - - - -

http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/sum_reciprocal_binomials
mailto:Torsten.Sillke@uni-bielefeld.de