ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 05 Mar 2012 02:17:03 -0600calculating n!/(n-k)! for k-permutationshttp://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/I was wondering if there is a way to calculate n!/(n-k)! in sage without using the factorial(n) method for n and n-k and then dividing.Sat, 03 Mar 2012 09:40:33 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/Answer by petropolis for <p>I was wondering if there is a way to calculate n!/(n-k)! in sage without using the factorial(n) method for n and n-k and then dividing.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13334#post-id-13334Sure, what you are looking for is the falling factorial.
<pre>
for n in (0..7) : [falling_factorial(n,k) for k in (0..n)]
[1]
[1, 1]
[1, 2, 2]
[1, 3, 6, 6]
[1, 4, 12, 24, 24]
[1, 5, 20, 60, 120, 120]
[1, 6, 30, 120, 360, 720, 720]
[1, 7, 42, 210, 840, 2520, 5040, 5040]
</pre>Sat, 03 Mar 2012 22:18:30 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13334#post-id-13334Comment by petropolis for <p>Sure, what you are looking for is the falling factorial.</p>
<pre>for n in (0..7) : [falling_factorial(n,k) for k in (0..n)]
[1]
[1, 1]
[1, 2, 2]
[1, 3, 6, 6]
[1, 4, 12, 24, 24]
[1, 5, 20, 60, 120, 120]
[1, 6, 30, 120, 360, 720, 720]
[1, 7, 42, 210, 840, 2520, 5040, 5040]
</pre>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20167#post-id-20167The pointer to the *very* suboptimal implementation as the quotient of two factorials did not make things better. And after all there is a function in Sage which does precisely (if implemented correctly) what the OP asked for:
"without using the factorial(n) method for n and n-k and then dividing."
"but I can already feel that the next time I see a question from petropolis I'll let it sit rather than take time to reply." I will have to live with this even so it will certainly damage the progress of my learning Sage considerably.
Sun, 04 Mar 2012 20:33:44 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20167#post-id-20167Comment by DSM for <p>Sure, what you are looking for is the falling factorial.</p>
<pre>for n in (0..7) : [falling_factorial(n,k) for k in (0..n)]
[1]
[1, 1]
[1, 2, 2]
[1, 3, 6, 6]
[1, 4, 12, 24, 24]
[1, 5, 20, 60, 120, 120]
[1, 6, 30, 120, 360, 720, 720]
[1, 7, 42, 210, 840, 2520, 5040, 5040]
</pre>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20171#post-id-20171+1 because this is a better solution, scaling only with a, but you can look at the source code yourself with "??" -- it has obvious inefficiencies of its own. [I removed my solution not because of your performance criteria but because for large numbers the factorial doesn't evaluate and I can't think of a clean way to get it to.] Patches are encouraged at trac.sagemath.org.Sun, 04 Mar 2012 02:33:09 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20171#post-id-20171Comment by petropolis for <p>Sure, what you are looking for is the falling factorial.</p>
<pre>for n in (0..7) : [falling_factorial(n,k) for k in (0..n)]
[1]
[1, 1]
[1, 2, 2]
[1, 3, 6, 6]
[1, 4, 12, 24, 24]
[1, 5, 20, 60, 120, 120]
[1, 6, 30, 120, 360, 720, 720]
[1, 7, 42, 210, 840, 2520, 5040, 5040]
</pre>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20168#post-id-20168Sorry that I hurt your feelings. However to call a bad solution a bad solution and to downvote a bad solution should not be discouraged as long as it is given in a polite form and the reason is explained in a comment, IMHO.
"we tend not to downvote answers which give correct results merely because they have suboptimal performance"
Well, read for example Richard P. Stanley's Enumerative Combinatorics. There you can read that generating combinatorial objects and than counting them is *no* solution of an enumeration problem. This is what I had in mind in the first place when I objected your answer.
Sun, 04 Mar 2012 20:33:34 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20168#post-id-20168Comment by G-Sage for <p>Sure, what you are looking for is the falling factorial.</p>
<pre>for n in (0..7) : [falling_factorial(n,k) for k in (0..n)]
[1]
[1, 1]
[1, 2, 2]
[1, 3, 6, 6]
[1, 4, 12, 24, 24]
[1, 5, 20, 60, 120, 120]
[1, 6, 30, 120, 360, 720, 720]
[1, 7, 42, 210, 840, 2520, 5040, 5040]
</pre>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20166#post-id-20166Even without a small size, I say a comment first explaining your point is best. Would you downvote a typo? Just point it out and let them fix it or delete it or whatever. And, MOST DEFINITELY, a correct answer that does not give optimal performance is not to be downvoted. Upvote the best answer. Then, everyone will know which one is best.Mon, 05 Mar 2012 02:16:19 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20166#post-id-20166Comment by DSM for <p>Sure, what you are looking for is the falling factorial.</p>
<pre>for n in (0..7) : [falling_factorial(n,k) for k in (0..n)]
[1]
[1, 1]
[1, 2, 2]
[1, 3, 6, 6]
[1, 4, 12, 24, 24]
[1, 5, 20, 60, 120, 120]
[1, 6, 30, 120, 360, 720, 720]
[1, 7, 42, 210, 840, 2520, 5040, 5040]
</pre>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20170#post-id-20170Incidentally, given our small size, a culture has developed in which we tend not to downvote answers which give correct results merely because they have suboptimal performance. [Even for an actually incorrect answer, I would tend to comment rather than downvote.] Vote up answers you like instead. I've been around long enough to fend for myself, but I can already feel that the next time I see a question from petropolis I'll let it sit rather than take time to reply -- and that was merely a threatened downvote! -- and probably beginners would feel even worse.Sun, 04 Mar 2012 02:44:28 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20170#post-id-20170Answer by DSM for <p>I was wondering if there is a way to calculate n!/(n-k)! in sage without using the factorial(n) method for n and n-k and then dividing.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13331#post-id-13331How about:
sage: Permutations(5)
Standard permutations of 5
sage: Permutations(5,3)
Permutations of {1,...,5} of length 3
sage: list(Permutations(5,3))
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 2], [1, 3, 4], [1, 3, 5], [1, 4, 2], [1, 4, 3], [1, 4, 5], [1, 5, 2], [1, 5, 3], [1, 5, 4], [2, 1, 3], [2, 1, 4], [2, 1, 5], [2, 3, 1], [2, 3, 4], [2, 3, 5], [2, 4, 1], [2, 4, 3], [2, 4, 5], [2, 5, 1], [2, 5, 3], [2, 5, 4], [3, 1, 2], [3, 1, 4], [3, 1, 5], [3, 2, 1], [3, 2, 4], [3, 2, 5], [3, 4, 1], [3, 4, 2], [3, 4, 5], [3, 5, 1], [3, 5, 2], [3, 5, 4], [4, 1, 2], [4, 1, 3], [4, 1, 5], [4, 2, 1], [4, 2, 3], [4, 2, 5], [4, 3, 1], [4, 3, 2], [4, 3, 5], [4, 5, 1], [4, 5, 2], [4, 5, 3], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 2, 1], [5, 2, 3], [5, 2, 4], [5, 3, 1], [5, 3, 2], [5, 3, 4], [5, 4, 1], [5, 4, 2], [5, 4, 3]]
sage: Permutations(5,3).cardinality()
60
sage: factorial(5)/factorial(5-3)
60
Although to be honest (since you commented about performance -- by the way, instead of giving separate answers, you can add comments to answers -- I'll do one here, to show you), all this does is hide the factorial. You can look at the source code for the routine by doing this:
age: P = Permutations(5,3)
sage: P.cardinality??
Type: instancemethod
Base Class: <type 'instancemethod'>
String Form: <bound method Permutations_nk.cardinality of Permutations of {1,...,5} of length 3>
Namespace: Interactive
File: /Applications/sage/local/lib/python2.6/site-packages/sage/combinat/permutation.py
Definition: P.cardinality(self)
Source:
def cardinality(self):
"""
EXAMPLES::
sage: Permutations(3,0).cardinality()
1
sage: Permutations(3,1).cardinality()
3
sage: Permutations(3,2).cardinality()
6
sage: Permutations(3,3).cardinality()
6
sage: Permutations(3,4).cardinality()
0
"""
if self.k <= self.n and self.k >= 0:
return factorial(self.n)/factorial(self.n-self.k)
else:
return 0
and so it's simply taking the factorial behind the scenes. If you *really* don't want to use any factorials for some inexplicable reason (maybe an allergy?) you could do something like
sage: sum(1 for p in Permutations(5,3))
60
but that would take a really long time when there are lots of permutations, whereas .cardinality() should be very quick, for obvious reasons.
Sat, 03 Mar 2012 10:11:06 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13331#post-id-13331Comment by petropolis for <p>How about:</p>
<pre><code>sage: Permutations(5)
Standard permutations of 5
sage: Permutations(5,3)
Permutations of {1,...,5} of length 3
sage: list(Permutations(5,3))
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 2], [1, 3, 4], [1, 3, 5], [1, 4, 2], [1, 4, 3], [1, 4, 5], [1, 5, 2], [1, 5, 3], [1, 5, 4], [2, 1, 3], [2, 1, 4], [2, 1, 5], [2, 3, 1], [2, 3, 4], [2, 3, 5], [2, 4, 1], [2, 4, 3], [2, 4, 5], [2, 5, 1], [2, 5, 3], [2, 5, 4], [3, 1, 2], [3, 1, 4], [3, 1, 5], [3, 2, 1], [3, 2, 4], [3, 2, 5], [3, 4, 1], [3, 4, 2], [3, 4, 5], [3, 5, 1], [3, 5, 2], [3, 5, 4], [4, 1, 2], [4, 1, 3], [4, 1, 5], [4, 2, 1], [4, 2, 3], [4, 2, 5], [4, 3, 1], [4, 3, 2], [4, 3, 5], [4, 5, 1], [4, 5, 2], [4, 5, 3], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 2, 1], [5, 2, 3], [5, 2, 4], [5, 3, 1], [5, 3, 2], [5, 3, 4], [5, 4, 1], [5, 4, 2], [5, 4, 3]]
sage: Permutations(5,3).cardinality()
60
sage: factorial(5)/factorial(5-3)
60
</code></pre>
<p>Although to be honest (since you commented about performance -- by the way, instead of giving separate answers, you can add comments to answers -- I'll do one here, to show you), all this does is hide the factorial. You can look at the source code for the routine by doing this:</p>
<pre><code>age: P = Permutations(5,3)
sage: P.cardinality??
Type: instancemethod
Base Class: <type 'instancemethod'>
String Form: <bound method Permutations_nk.cardinality of Permutations of {1,...,5} of length 3>
Namespace: Interactive
File: /Applications/sage/local/lib/python2.6/site-packages/sage/combinat/permutation.py
Definition: P.cardinality(self)
Source:
def cardinality(self):
"""
EXAMPLES::
sage: Permutations(3,0).cardinality()
1
sage: Permutations(3,1).cardinality()
3
sage: Permutations(3,2).cardinality()
6
sage: Permutations(3,3).cardinality()
6
sage: Permutations(3,4).cardinality()
0
"""
if self.k <= self.n and self.k >= 0:
return factorial(self.n)/factorial(self.n-self.k)
else:
return 0
</code></pre>
<p>and so it's simply taking the factorial behind the scenes. If you <em>really</em> don't want to use any factorials for some inexplicable reason (maybe an allergy?) you could do something like</p>
<pre><code>sage: sum(1 for p in Permutations(5,3))
60
</code></pre>
<p>but that would take a really long time when there are lots of permutations, whereas .cardinality() should be very quick, for obvious reasons.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20172#post-id-20172With all due respect: this is not a sane method to *calculate* the falling factorial. (Therefore I would downvote your answer but I am not allowed to do so.) And indeed the most efficient method to calculate the falling factorial does *not* use the factorial per se. Instead it uses the prime factorization of the factorial.Sat, 03 Mar 2012 22:26:05 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20172#post-id-20172Comment by DSM for <p>How about:</p>
<pre><code>sage: Permutations(5)
Standard permutations of 5
sage: Permutations(5,3)
Permutations of {1,...,5} of length 3
sage: list(Permutations(5,3))
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 2], [1, 3, 4], [1, 3, 5], [1, 4, 2], [1, 4, 3], [1, 4, 5], [1, 5, 2], [1, 5, 3], [1, 5, 4], [2, 1, 3], [2, 1, 4], [2, 1, 5], [2, 3, 1], [2, 3, 4], [2, 3, 5], [2, 4, 1], [2, 4, 3], [2, 4, 5], [2, 5, 1], [2, 5, 3], [2, 5, 4], [3, 1, 2], [3, 1, 4], [3, 1, 5], [3, 2, 1], [3, 2, 4], [3, 2, 5], [3, 4, 1], [3, 4, 2], [3, 4, 5], [3, 5, 1], [3, 5, 2], [3, 5, 4], [4, 1, 2], [4, 1, 3], [4, 1, 5], [4, 2, 1], [4, 2, 3], [4, 2, 5], [4, 3, 1], [4, 3, 2], [4, 3, 5], [4, 5, 1], [4, 5, 2], [4, 5, 3], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 2, 1], [5, 2, 3], [5, 2, 4], [5, 3, 1], [5, 3, 2], [5, 3, 4], [5, 4, 1], [5, 4, 2], [5, 4, 3]]
sage: Permutations(5,3).cardinality()
60
sage: factorial(5)/factorial(5-3)
60
</code></pre>
<p>Although to be honest (since you commented about performance -- by the way, instead of giving separate answers, you can add comments to answers -- I'll do one here, to show you), all this does is hide the factorial. You can look at the source code for the routine by doing this:</p>
<pre><code>age: P = Permutations(5,3)
sage: P.cardinality??
Type: instancemethod
Base Class: <type 'instancemethod'>
String Form: <bound method Permutations_nk.cardinality of Permutations of {1,...,5} of length 3>
Namespace: Interactive
File: /Applications/sage/local/lib/python2.6/site-packages/sage/combinat/permutation.py
Definition: P.cardinality(self)
Source:
def cardinality(self):
"""
EXAMPLES::
sage: Permutations(3,0).cardinality()
1
sage: Permutations(3,1).cardinality()
3
sage: Permutations(3,2).cardinality()
6
sage: Permutations(3,3).cardinality()
6
sage: Permutations(3,4).cardinality()
0
"""
if self.k <= self.n and self.k >= 0:
return factorial(self.n)/factorial(self.n-self.k)
else:
return 0
</code></pre>
<p>and so it's simply taking the factorial behind the scenes. If you <em>really</em> don't want to use any factorials for some inexplicable reason (maybe an allergy?) you could do something like</p>
<pre><code>sage: sum(1 for p in Permutations(5,3))
60
</code></pre>
<p>but that would take a really long time when there are lots of permutations, whereas .cardinality() should be very quick, for obvious reasons.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20174#post-id-20174This is an example of a comment.Sat, 03 Mar 2012 10:56:22 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20174#post-id-20174Answer by god.one for <p>I was wondering if there is a way to calculate n!/(n-k)! in sage without using the factorial(n) method for n and n-k and then dividing.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13330#post-id-13330Hi,
you are looking for the binomial coefficients
binomial(n,k)
which is explained
[here](http://www.sagemath.org/doc/reference/sage/rings/arith.html).Sat, 03 Mar 2012 09:48:47 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13330#post-id-13330Comment by G-Sage for <p>Hi,</p>
<p>you are looking for the binomial coefficients</p>
<pre><code>binomial(n,k)
</code></pre>
<p>which is explained
<a href="http://www.sagemath.org/doc/reference/sage/rings/arith.html">here</a>.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20165#post-id-20165This answer is wrong. binomial(n, k) = $\frac{n!}{k! (n-k)!}$, which is not the question.Mon, 05 Mar 2012 02:17:03 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20165#post-id-20165Answer by johnsa5 for <p>I was wondering if there is a way to calculate n!/(n-k)! in sage without using the factorial(n) method for n and n-k and then dividing.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13288#post-id-13288I am not looking for the binomial coefficient, what the binomial(n,k) calculates is n!/(k!(n-k)!). What I am looking for is a the number of ways to get k-permutations out of n elements. Sorry if I was not clear.Sat, 03 Mar 2012 10:01:08 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13288#post-id-13288Answer by johnsa5 for <p>I was wondering if there is a way to calculate n!/(n-k)! in sage without using the factorial(n) method for n and n-k and then dividing.</p>
http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13332#post-id-13332Thanks, I thought doing it this way might be really slow but after some testing it appears that even with large inputs it doesn't take long to calculate.Sat, 03 Mar 2012 10:22:16 -0600http://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13332#post-id-13332