On Feb 2, 2010, at 2:28 PM, robert bristow-johnson wrote:
Warren tells me that
C-1
SUM{ C!/n! }
n=1
has a closed form, but didn't tell me what it is. does someone
have the closed form for it? i fiddled with it a little, and i can
certainly see an asymptotic limit of
(e-1)(C!)
as C gets large, but i don't see an exact closed form for it. if
someone has such a closed form, would you mind sharing it?
Okay, I spent a little time working on this and figgered it out. The
fact that the number of distinct piles needed to represent all
possible manners of *relatively* ranking C candidates (no ties except
unranked candidates are tied for lowest rank) is
C-1
SUM{ C!/n! } = floor( (e-1) C! ) - 1
n=1
I was at first unconvinced that the right hand side is an exact
closed form for the left, but now accept that it is.
The proof requires as given:
inf
SUM{ 1/n! } = e ~= 2.718281828...
n=0
The floor(a) function which returns the only integer such that
a-1 < floor(a) <= a
and, if n is an integer, then
floor(a + n) = floor(a) + n for any a.
It also requires knowledge that if C and n are integers and C >= n, then
C!/n! = C(C-1)(C-2)(C-3)...(n+1) = integer
From that
inf C-1 inf
C! e = SUM{ C!/n! } = C! + SUM{ C!/n! } + C!/C! + SUM
{ C!/n! }
n=0 n=1 n=C+1
or
C-1 inf
C! e = C! + SUM{ C!/n! } + 1 + SUM{ C!/n! }
n=1 n=C+1
The first three terms on the RH are integers. The last term
inf
SUM{ C!/n! } = 1/(C+1) + 1/[(C+1)(C+2)] + 1/[(C+1)(C+2)(C+3)]
+ ...
n=C+1
is less than
inf
SUM{ C!/n! } < 1/C + 1/C^2 + 1/C^3 + ...
n=C+1
which is
inf inf
SUM{ C!/n! } < (1/C) SUM{ (1/C)^j } = (1/C)/[1 - (1/C)] =
1/(C-1)
n=C+1 j=0
which is less than 1 for any C > 2. So we know that the last term in
C-1 inf
C! e = C! + SUM{ C!/n! } + 1 + SUM{ C!/n! }
n=1 n=C+1
is less than 1.
Then applying the floor() function to both sides yields
C-1 inf
floor(C! e) = floor( C! + SUM{ C!/n! } + 1 + SUM{ C!/n! } )
n=1 n=C+1
which is
C-1 inf
floor(C! e) = C! + SUM{ C!/n! } + 1 + floor( SUM{ C!/n! } )
n=1 n=C+1
Since the argument of the floor() function on the right is less than
1, the returned value of the floor() function is known to be zero.
C-1
floor(C! e) = C! + SUM{ C!/n! } + 1
n=1
Resulting in
C-1
SUM{ C!/n! } = floor( (e-1) C! ) - 1
n=1
at least for any integer C greater than 2.
I do this kinda thing all the time at comp.dsp or the music-dsp
mailing list, but haven't done this before outside of those two
technical contexts. It was kinda fun.
Thanks Warren, for the hint.
--
r b-j [email protected]
"Imagination is more important than knowledge."
----
Election-Methods mailing list - see http://electorama.com/em for list info
