Prev: Number Representation Problem
Next: bisecting quadrilateral to get rhomboid, proof
From: Robert Israel on 24 Jan 2010 14:23
Mensanator <mensanator(a)aol.com> writes:

> On Jan 24, 11:45=A0am, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
> > TCL <tl...(a)cox.net> wrote:
> > > What is the closed form formula (if any) of the sum
> >
> > > P(n,0)+P(n,1)+....+P(n,n)
> >
> > > where P(n,i) is the number of permutations of n taken i at a time?
> >
> > It appears that you want the total number of arrangements of a set with n
> > elements, as discussed at
> > <http://www.research.att.com/~njas/sequences/A000522>.
> >
> > A simple formula for that total number of arrangements is
> >
> > [ e * n! ]
> >
> > where the square brackets denote the floor function.
>
> Yeah, but that breaks down at n =3D 18:
>
> 1 2 2
> 2 5 5
> 3 16 16
> 4 65 65
> 5 326 326
> 6 1957 1957
> 7 13700 13700
> 8 109601 109601
> 9 986410 986410
> 10 9864101 9864101
> 11 108505112 108505112
> 12 1302061345 1302061345
> 13 16926797486 16926797486
> 14 236975164805 236975164805
> 15 3554627472076 3554627472076
> 16 56874039553217 56874039553217
> 17 966858672404690 966858672404690
> 18 17403456103284421 17403456103284420 <--
> 19 330665665962404000 330665665962403968
> 20 6613313319248080001 6613313319248079872
> 21 138879579704209680022 138879579704209670144
> 22 3055350753492612960485 3055350753492612939776
> 23 70273067330330098091156 70273067330330098139136
> 24 1686553615927922354187745 1686553615927922288230400
> 25 42163840398198058854693626 42163840398198055595147264
> 26 1096259850353149530222034277 1096259850353149479833567232
> 27 29599015959535037315994925480 29599015959535034993433640960
> 28 828772446866981044847857913441 828772446866981067777072168960
> 29 24034400959142450300587879489790 24034400959142450684060116189184
>
> output of sum_of_perm.py
> # Python 3.1
> import math
> for n in range(1,30):
> print(n,end=3D' ')
> q =3D [1]
> for i in range(n,0,-1):
> q.append(q[-1]*i)
> print(sum(q),math.floor(math.exp(1)*math.factorial(n)))

Insufficient accuracy being used in evaluating e?

17403456103284421 is correct for n=18, according to Maple.

Note that n! e = sum_{k=0}^infty n!/k!
= sum_{k=0}^n n!/k! + sum_{k=n+1}^infty n!/k!

and sum_{k=n+1}^infty n!/k! < sum_{j=1}^infty 1/(n+1)^j = 1/n
--
Robert Israel israel(a)math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
From: Robert Israel on 24 Jan 2010 14:33
Mensanator <mensanator(a)aol.com> writes:


> >
> > > A simple formula for that total number of arrangements is
> >
> > > [ e * n! ]
> >
> > > where the square brackets denote the floor function.
> >
> > Yeah, but that breaks down at n =3D 18:
>
> Probably due to the limited precision of the calculation of e.
>
> But that's an important point, isn't it?
>
> To get EXACT answers, you need unlimited precision.

You can hardly expect an N-digit answer to be correct when using
less than N digits of precision. Since e * n! - x_n is approximately
1/(n+1), you'd want to calculate e with an accuracy of approximately
1/(n+1)!.
--
Robert Israel israel(a)math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
From: Mensanator on 24 Jan 2010 14:47
On Jan 24, 1:33�pm, Robert Israel
<isr...(a)math.MyUniversitysInitials.ca> wrote:
> Mensanator <mensana...(a)aol.com> writes:
>
> > > > A simple formula for that total number of arrangements is
>
> > > > [ e * n! ]
>
> > > > where the square brackets denote the floor function.
>
> > > Yeah, but that breaks down at n =3D 18:
>
> > Probably due to the limited precision of the calculation of e.
>
> > But that's an important point, isn't it?
>
> > To get EXACT answers, you need unlimited precision.
>
> You can hardly expect an N-digit answer to be correct when using
> less than N digits of precision. �

Of course, that's why I posted the this addendum to my original
post. You have to be aware of the precision to which your math
system calculates e.

Am I correct in assuming no system calculates e to an infinite
number of places? So there will always be some n for which
[e*n!] does not give the correct answer?

> Since e * n! - x_n is approximately
> 1/(n+1), you'd want to calculate e with an accuracy of approximately
> 1/(n+1)!.
> --
> Robert Israel � � � � � � �isr...(a)math.MyUniversitysInitials.ca
> Department of Mathematics � � � �http://www.math.ubc.ca/~israel
> University of British Columbia � � � � � �Vancouver, BC, Canada

From: Mensanator on 24 Jan 2010 14:49
On Jan 24, 1:23�pm, Robert Israel
<isr...(a)math.MyUniversitysInitials.ca> wrote:
> Mensanator <mensana...(a)aol.com> writes:
> > On Jan 24, 11:45=A0am, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
> > > TCL <tl...(a)cox.net> wrote:
> > > > What is the closed form formula (if any) of the sum
>
> > > > P(n,0)+P(n,1)+....+P(n,n)
>
> > > > where P(n,i) is the number of permutations of n taken i at a time?
>
> > > It appears that you want the total number of arrangements of a set with n
> > > elements, as discussed at
> > > <http://www.research.att.com/~njas/sequences/A000522>.
>
> > > A simple formula for that total number of arrangements is
>
> > > [ e * n! ]
>
> > > where the square brackets denote the floor function.
>
> > Yeah, but that breaks down at n =3D 18:
>
> > 1 2 2
> > 2 5 5
> > 3 16 16
> > 4 65 65
> > 5 326 326
> > 6 1957 1957
> > 7 13700 13700
> > 8 109601 109601
> > 9 986410 986410
> > 10 9864101 9864101
> > 11 108505112 108505112
> > 12 1302061345 1302061345
> > 13 16926797486 16926797486
> > 14 236975164805 236975164805
> > 15 3554627472076 3554627472076
> > 16 56874039553217 56874039553217
> > 17 966858672404690 966858672404690
> > 18 17403456103284421 17403456103284420 � <--
> > 19 330665665962404000 330665665962403968
> > 20 6613313319248080001 6613313319248079872
> > 21 138879579704209680022 138879579704209670144
> > 22 3055350753492612960485 3055350753492612939776
> > 23 70273067330330098091156 70273067330330098139136
> > 24 1686553615927922354187745 1686553615927922288230400
> > 25 42163840398198058854693626 42163840398198055595147264
> > 26 1096259850353149530222034277 1096259850353149479833567232
> > 27 29599015959535037315994925480 29599015959535034993433640960
> > 28 828772446866981044847857913441 828772446866981067777072168960
> > 29 24034400959142450300587879489790 24034400959142450684060116189184
>
> > output of sum_of_perm.py
> > # Python 3.1
> > import math
> > for n in range(1,30):
> > � print(n,end=3D' ')
> > � q =3D [1]
> > � for i in range(n,0,-1):
> > � � q.append(q[-1]*i)
> > � print(sum(q),math.floor(math.exp(1)*math.factorial(n)))
>
> Insufficient accuracy being used in evaluating e?

I assume so.
�
>
> 17403456103284421 is correct for n=18, according to Maple.

How many places will Maple calculate e to?

Will it work for n=100? n=1000? n=1000000?

>
> Note that n! e = sum_{k=0}^infty n!/k!
> � � � � � � � �= sum_{k=0}^n n!/k! + sum_{k=n+1}^infty n!/k!
>
> and sum_{k=n+1}^infty n!/k! < sum_{j=1}^infty 1/(n+1)^j = 1/n
> --
> Robert Israel � � � � � � �isr...(a)math.MyUniversitysInitials.ca
> Department of Mathematics � � � �http://www.math.ubc.ca/~israel
> University of British Columbia � � � � � �Vancouver, BC, Canada- Hide quoted text -
>
> - Show quoted text -

From: Robert Israel on 24 Jan 2010 15:21
Mensanator <mensanator(a)aol.com> writes:

> On Jan 24, 1:23=EF=BF=BDpm, Robert Israel
> <isr...(a)math.MyUniversitysInitials.ca> wrote:
> > Mensanator <mensana...(a)aol.com> writes:
> > > On Jan 24, 11:45=3DA0am, David W. Cantrell <DWCantr...(a)sigmaxi.net>
> > > wro=
> te:
> > > > TCL <tl...(a)cox.net> wrote:
> > > > > What is the closed form formula (if any) of the sum
> >
> > > > > P(n,0)+P(n,1)+....+P(n,n)
> >
> > > > > where P(n,i) is the number of permutations of n taken i at a time?
> >
> > > > It appears that you want the total number of arrangements of a set
> > > > wi=
> th n
> > > > elements, as discussed at
> > > > <http://www.research.att.com/~njas/sequences/A000522>.
> >
> > > > A simple formula for that total number of arrangements is
> >
> > > > [ e * n! ]
> >
> > > > where the square brackets denote the floor function.
> >
> > > Yeah, but that breaks down at n =3D3D 18:
> >
> > > 1 2 2
> > > 2 5 5
> > > 3 16 16
> > > 4 65 65
> > > 5 326 326
> > > 6 1957 1957
> > > 7 13700 13700
> > > 8 109601 109601
> > > 9 986410 986410
> > > 10 9864101 9864101
> > > 11 108505112 108505112
> > > 12 1302061345 1302061345
> > > 13 16926797486 16926797486
> > > 14 236975164805 236975164805
> > > 15 3554627472076 3554627472076
> > > 16 56874039553217 56874039553217
> > > 17 966858672404690 966858672404690
> > > 18 17403456103284421 17403456103284420 =EF=BF=BD <--
> > > 19 330665665962404000 330665665962403968
> > > 20 6613313319248080001 6613313319248079872
> > > 21 138879579704209680022 138879579704209670144
> > > 22 3055350753492612960485 3055350753492612939776
> > > 23 70273067330330098091156 70273067330330098139136
> > > 24 1686553615927922354187745 1686553615927922288230400
> > > 25 42163840398198058854693626 42163840398198055595147264
> > > 26 1096259850353149530222034277 1096259850353149479833567232
> > > 27 29599015959535037315994925480 29599015959535034993433640960
> > > 28 828772446866981044847857913441 828772446866981067777072168960
> > > 29 24034400959142450300587879489790 24034400959142450684060116189184
> >
> > > output of sum_of_perm.py
> > > # Python 3.1
> > > import math
> > > for n in range(1,30):
> > > =EF=BF=BD print(n,end=3D3D' ')
> > > =EF=BF=BD q =3D3D [1]
> > > =EF=BF=BD for i in range(n,0,-1):
> > > =EF=BF=BD =EF=BF=BD q.append(q[-1]*i)
> > > =EF=BF=BD print(sum(q),math.floor(math.exp(1)*math.factorial(n)))
> >
> > Insufficient accuracy being used in evaluating e?
>
> I assume so.
> =EF=BF=BD
> >
> > 17403456103284421 is correct for n=3D18, according to Maple.
>
> How many places will Maple calculate e to?
>
> Will it work for n=3D100? n=3D1000? n=3D1000000?

Maple will use as many digits as you tell it to, up to 268435448
on a 32-bit system (I'm not sure if 64-bit systems could handle more).
Of course, time and memory could also be limitations. But n=10^6
might be doable. Since log[10]((10^6)!) ~ 5565709, you'd want at
least that many digits.
--
Robert Israel israel(a)math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
First  |  Prev  | 
Pages: 1 2
Prev: Number Representation Problem
Next: bisecting quadrilateral to get rhomboid, proof