'Mixing number' of permutations
Henry Gould
gould at math.wvu.edu
Thu Aug 17 19:27:07 CEST 2006
My memory made a small made a mistake. Here is a correct statement which
I just picked up on the web at
<http://f2.org/maths/resnet/>
"When I read the rec.puzzles FAQ there was [November 2004: & still is]
no general solution to the resistance between opposite corners of an
arbitrary hypercube of 1-ohm resistors; solutions were only given for 3D
and 4D hypercubes. This problem seemed quite tractable - just
combinatorics. The same reasoning about symmetry for the cube case can
be applied to the arbitrary d-dimensional case: joining the
equipotential points results in d layers containing d(d-1 choose i)
resistors in parallel in the i'th layer, giving an overall resistance of
(sum from i=0 to d-1 of 1/(d-1 choose i)) / d. The values for the first
few d are:
d 2 3 4 5 6 7 8 9 10 11
resistance 1 5/6 2/3 8/15 13/30 151/420 32/105 83/315 73/315
1433/6930
As d gets larger, the resistance tends toward 2/d [more accurately, 2/d
+ 2/(d-1)^2] ; the dense layers in the middle become relatively perfect
conductors compared to the outermost layers."
So what I wanted to recall is (1/n)*sum(1/binomial(n-1,k),k=0..n-1). Se
were asked in a calculus class at University of Virginia in 1948 yo find
the resistance of a rhree dimensional cube and we extended it to n by
this formula, which you can get by using Kirchhoff's laws. The fractions
abovve may be adjusted or normalized and entered in the OEIS if not
already there.
Regards,
Henry Gould
Brendan McKay 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
>>
>
>
More information about the SeqFan
mailing list