Prev: Number Representation Problem
Next: bisecting quadrilateral to get rhomboid, proof
From: TCL on 24 Jan 2010 11:14
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?
-TCL
From: David W. Cantrell on 24 Jan 2010 12:45
TCL <tlim1(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.

David W. Cantrell
From: David W. Cantrell on 24 Jan 2010 12:58
David W. Cantrell <DWCantrell(a)sigmaxi.net> wrote:
> TCL <tlim1(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.

I should have specified that the above formula is valid for n >= 1.
Consider n = 0 as a special case.

David
From: Mensanator on 24 Jan 2010 13:52
On Jan 24, 11:45 am, 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 = 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=' ')
q = [1]
for i in range(n,0,-1):
q.append(q[-1]*i)
print(sum(q),math.floor(math.exp(1)*math.factorial(n)))


>
> David W. Cantrell

From: Mensanator on 24 Jan 2010 14:10
On Jan 24, 12:52 pm, Mensanator <mensana...(a)aol.com> wrote:
> On Jan 24, 11:45 am, 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 = 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.

>
> 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=' ')
>   q = [1]
>   for i in range(n,0,-1):
>     q.append(q[-1]*i)
>   print(sum(q),math.floor(math.exp(1)*math.factorial(n)))
>
>
>
>
>
> > David W. Cantrell

 |  Next  |  Last
Pages: 1 2
Prev: Number Representation Problem
Next: bisecting quadrilateral to get rhomboid, proof