ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 05 Mar 2012 09:16:19 +0100calculating n!/(n-k)! for k-permutationshttps://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 16:40:33 +0100https://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>
https://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>Sun, 04 Mar 2012 05:18:30 +0100https://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13334#post-id-13334Comment 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>
https://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 09:44:28 +0100https://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20170#post-id-20170Comment 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>
https://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 09:16:19 +0100https://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20166#post-id-20166Comment 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>
https://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.
Mon, 05 Mar 2012 03:33:34 +0100https://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20168#post-id-20168Comment 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>
https://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 09:33:09 +0100https://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>
https://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.
Mon, 05 Mar 2012 03:33:44 +0100https://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?comment=20167#post-id-20167Answer 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>
https://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 17:22:16 +0100https://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13332#post-id-13332Answer 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>
https://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 17:01:08 +0100https://ask.sagemath.org/question/8767/calculating-nn-k-for-k-permutations/?answer=13288#post-id-13288