'Mixing number' of permutations

[liskov at im.bas-net.by]

The following identity is known (B.Sury, Sum of the
reciprocals of the binomial coefficients, Eur. J. Comb.
14 (1993), 351-353):

sum(1/binomial(n,k),k=0..n)=(n+1)/2^n*sum(2^j/(j+1),j=0..n).

See also:

T.Mansour, Combinatorial identities and inverse binomial
coefficients, Adv. in Appl. Math. 28 (2002), 196-202

and references therein.

This sum takes part in a formula for the number of
ramified coverings of the projective plane with two
cyclic branch points; see A113947.

At the same time (cf. R.P.Stanley, Enumerative Combinatorics,
v.2, 1999, Ex.7.67(d)),

sum((-1)^k/binomial(n,k),k=0..n)=2(n+1)/(n+2)
for even n (vanishes for odd n).

Valery Liskovets


Brendan McKay <bdm at cs.anu.edu.au> wrote:

> The average is  sum(1/binomial(n,k),k=1..n-1).  I don't know
> if this has a closed form or a name.
>
> Proof:  There are clearly k! (n-k)! permutations that have a
> break after the k-th value, so the probability of a break in
> that place is 1/binomial(n,k).
>
> Asymptotically, the values k=1 and k=n-1 dominate, so the
> expectation is 2/n + O(1/n^2).
>
> Brendan.
>
>
> * Hugo Pfoertner <all at abouthugo.de> [060817 22:30]:
> > SeqFans,
> >
> > today Hauke Reddmann started a new thread in the NG sci.math
> >
> > http://groups.google.com/group/sci.math/msg/b1c1164b936c6dca
> >
> > <<
> > For easyness, I use the data of my lest chess tournament :-)
> > The finish in terms of the starting numbers was
> > 7 1 6 4 3 8 5 2|9|10|14 15 20 13 18 16 23 22 12 26 11 17 19 27 25 21
> > 24|28
> >
> > A | marks boundaries between consecutive number subsets that permute
> > to themselves. Note that I (the 16) also permute to myself, but there
> > are number crossing from both sides and so this is no boundary.
> >
> > Obvious question: How many boundaries occur in a random permutation?
> > Clearly a tournament is about the opposite of random, as the swap
> > numbers will be low.
> >
> > Example n=3
> >
> > 1|2|3
> > 1|3 2
> > 2 1|3
> > 2 3 1
> > 3 1 2
> > 3 2 1
> > --
> > Hauke Reddmann <:-EX8    fc3a501 at uni-hamburg.de
> > His-Ala-Sec-Lys-Glu Arg-Glu-Asp-Asp-Met-Ala-Asn-Asn
> > >>
> >
> > Is there anything in the OEIS that can answer his question? Any other
> > ideas?
> >
> > Can you please CC answers also to Hauke; AFAIK he is not member of the
> > Seqfan community.
> >
> > Hugo Pfoertner