Looking for a function

[Amaton]

Hey

 

I was toying around with an idea that vaguely resembles vertex-edge graphs. We have two locations: A and B. The objective is to get from A to B going from point to point in the region in between. One is not allowed to go back to a point already taken.

 

It was a simple observation that given [math]n[/math] path points, there exist [math]n+n(n-1)+n(n-1)(n-2)+...+n![/math] possible unique pathways one can take.

 

For example, with 4 path points in between, (labelled m, n, p, q), one can take [math]4+4(3)+4(3)(2)+4(3)(2)(1)=64[/math] pathways.

 

The number of terms in the above general formula changes according to how large [math]n[/math] is. So question: Is there a more preferred function [math]f(n)[/math] where I can simply plug in [math]n[/math]?

[John]

Well, what you're doing with the sum is counting k-permutations for k = 1 to k = n, e.g. in your example, the sum is equal to [math]{_4P_1}+{_4P_2}+{_4P_3}+{_4P_4} = \frac{4!}{(4-1)!}+\frac{4!}{(4-2)!}+\frac{4!}{(4-3)!}+\frac{4!}{(4-4)!}[/math]. I don't know of a special function that does this, but you can express the sum using sigma notation of course, i.e. given [math]n[/math] points, you have [math]\sum\limits_{k=1}^n {_nP_k} = \sum\limits_{k=1}^n \frac{n!}{(n-k)!}[/math].

 

Having said that, I just did a search and found this discussion, which you might find interesting: http://math.stackexchange.com/questions/161314/what-is-the-sum-of-following-permutation-series-np0-np1-np2-cdots-npn

Edited June 25, 2013 by John

[Daedalus]

Well, what you're doing with the sum is counting k-permutations for k = 1 to k = n, e.g. in your example, the sum is equal to [math]{_4P_1}+{_4P_2}+{_4P_3}+{_4P_4} = \frac{4!}{(4-1)!}+\frac{4!}{(4-2)!}+\frac{4!}{(4-3)!}+\frac{4!}{(4-4)!}[/math]. I don't know of a special function that does this, but you can express the sum using sigma notation of course, i.e. given [math]n[/math] points, you have [math]\sum\limits_{k=1}^n {_nP_k} = \sum\limits_{k=1}^n \frac{n!}{(n-k)!}[/math].

 

Having said that, I just did a search and found this discussion, which you might find interesting: http://math.stackexchange.com/questions/161314/what-is-the-sum-of-following-permutation-series-np0-np1-np2-cdots-npn

 

The summation [math]\sum\limits_{k=1}^n {_nP_k} = \sum\limits_{k=1}^n \frac{n!}{(n-k)!}[/math] can be expressed using the incomplete gamma function as

 

[math]f(n)=e\,\Gamma(n+1,1)-1[/math]

 

where

[math]e=2.71828...[/math] and [math]\Gamma(s,\,x)=\int\limits_{x}^{\infty}\frac{t^{s-1}}{e^t}\,dt[/math]

Edited June 26, 2013 by Daedalus

[Amaton]

Well, what you're doing with the sum is counting k-permutations for k = 1 to k = n, e.g. in your example, the sum is equal to [math]{_4P_1}+{_4P_2}+{_4P_3}+{_4P_4} = \frac{4!}{(4-1)!}+\frac{4!}{(4-2)!}+\frac{4!}{(4-3)!}+\frac{4!}{(4-4)!}[/math]. I don't know of a special function that does this, but you can express the sum using sigma notation of course, i.e. given [math]n[/math] points, you have [math]\sum\limits_{k=1}^n {_nP_k} = \sum\limits_{k=1}^n \frac{n!}{(n-k)!}[/math].

 

Thanks. That series is actually fine by me. I failed to see the permutations in my expression (I really need to refresh on basic probability), though it follows the model intuitively. Each distinct pathway is just one of the possible permutations of points in between A and B.

 

 

The summation [math]\sum\limits_{k=1}^n {_nP_k} = \sum\limits_{k=1}^n \frac{n!}{(n-k)!}[/math] can be expressed using the incomplete gamma function as

 

[math]f(n)=e\,\Gamma(n+1,1)-1[/math]

 

where

[math]e=2.71828...[/math] and [math]\Gamma(s,\,x)=\int\limits_{x}^{\infty}\frac{t^{s-1}}{e^t}\,dt[/math]

 

Neat, thanks. So [math]f(n)=e\displaystyle\int_{1}^\infty \dfrac{t^n}{e^t} dt\,-\,1[/math]. Never thought an integral representation would be relevant.

Edited July 2, 2013 by Amaton

[Daedalus]

Neat, thanks. So [math]f(n)=e\displaystyle\int_{1}^\infty \dfrac{t^n}{e^t} dt\,-\,1[/math]. Never thought an integral representation would be relevant.

 

What's even cooler is that the gamma function, which is the same integral with the lower limit set to zero and the upper limit set to infinity, actually produces the same sequence as factorials except it is defined over the reals.

Edited July 3, 2013 by Daedalus