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

edit retag close merge delete

Sort by » oldest newest most voted

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]

more

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

( 2012-03-04 02:33:09 -0600 )edit

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.

( 2012-03-04 02:44:28 -0600 )edit
1

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.

( 2012-03-04 20:33:34 -0600 )edit
1

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.

( 2012-03-04 20:33:44 -0600 )edit

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.

( 2012-03-05 02:16:19 -0600 )edit

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

more

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

more