Amaton Posted June 25, 2013 Share Posted June 25, 2013 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]? Link to comment Share on other sites More sharing options...

John Posted June 25, 2013 Share Posted June 25, 2013 (edited) 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 Link to comment Share on other sites More sharing options...

Daedalus Posted June 26, 2013 Share Posted June 26, 2013 (edited) 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 Link to comment Share on other sites More sharing options...

Amaton Posted July 2, 2013 Author Share Posted July 2, 2013 (edited) 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 Link to comment Share on other sites More sharing options...

Daedalus Posted July 3, 2013 Share Posted July 3, 2013 (edited) 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 Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now