# calculating n!/(n-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.

calculating n!/(n-k)! for k-permutations

add a comment

2

Sure, what you are looking for is the falling factorial.

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]

+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.

Incidentally, 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.

Sorry 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.

The 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.

Even 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.

0

0

Asked: **
2012-03-03 09:40:33 -0600
**

Seen: **434 times**

Last updated: **Mar 03 '12**

Finding the permutation that sorts a list

Need to shift a permutation (1,2,3)(4,5)->(6,7,8)(9,10)

Counting cycles of induced permutations

Permutations indexed from zero

the permutation of subscripts of a multivariate polynomial

Orbits on group actions acting on sets

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.