Ask Your Question
0

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

asked 2012-03-03 09:40:33 -0500

johnsa5 gravatar image

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 flag offensive close merge delete

3 answers

Sort by ยป oldest newest most voted
2

answered 2012-03-03 22:18:30 -0500

petropolis gravatar image

updated 2012-03-03 22:18:57 -0500

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]
edit flag offensive delete link more

Comments

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

DSM gravatar imageDSM ( 2012-03-04 02:33:09 -0500 )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.

DSM gravatar imageDSM ( 2012-03-04 02:44:28 -0500 )edit

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.

petropolis gravatar imagepetropolis ( 2012-03-04 20:33:34 -0500 )edit

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.

petropolis gravatar imagepetropolis ( 2012-03-04 20:33:44 -0500 )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.

G-Sage gravatar imageG-Sage ( 2012-03-05 02:16:19 -0500 )edit
0

answered 2012-03-03 10:01:08 -0500

johnsa5 gravatar image

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.

edit flag offensive delete link more
0

answered 2012-03-03 10:22:16 -0500

johnsa5 gravatar image

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-03-03 09:40:33 -0500

Seen: 558 times

Last updated: Mar 03 '12