Opened 11 years ago

Closed 11 years ago

#6636 closed enhancement (fixed)

[with patch, positive review] Simplification of factorials and binomial coefficients is not very good

Reported by: jbandlow Owned by:
Priority: major Milestone: sage-4.1.2
Component: symbolics Keywords: symbolics, factorials, binomial coefficients
Cc: jbandlow, burcin, mhansen Merged in: Sage 4.1.2.alpha2
Authors: Karl-Dieter Crisman Reviewers: Mike Hansen
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Maple can simplify all but the first of the following examples:

%maple
print(simplify(binomial(n,2)+binomial(n+1,2)));
print(simplify(factorial(n)/factorial(n-2)/2 + factorial(n+1)/factorial(n-1)/2));
print(simplify(factorial(n+1)/factorial(n)));
print(simplify(binomial(n,k)*factorial(k)*factorial(n-k)));

returns

binomial(n,2)+binomial(n+1,2)
n^2
n+1
n!

Sage can simplify only the first:

var('n,k')
print (binomial(n,2) + binomial(n+1,2)).simplify_full()
print (factorial(n)/factorial(n-2)/2 + factorial(n+1)/factorial(n)/2).simplify_full()
print (factorial(n+1)/factorial(n)).simplify_full()
print (binomial(n,k)*factorial(k)*factorial(n-k)).simplify_full()

returns

n^2
1/2*(factorial(n - 2)*factorial(n + 1) + factorial(n)^2)/(factorial(n - 2)*factorial(n))
factorial(n + 1)/factorial(n)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/jason/.sage/sage_notebook/worksheets/admin/10/code/49.py", line 11, in <module>
    exec compile(ur'print (binomial(n,k)*factorial(k)*factorial(n-k)).simplify_full()' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "expression.pyx", line 4837, in sage.symbolic.expression.Expression.simplify_full (sage/symbolic/expression.cpp:19979)
  File "expression.pyx", line 4864, in sage.symbolic.expression.Expression.simplify_trig (sage/symbolic/expression.cpp:20076)
  File "expression.pyx", line 418, in sage.symbolic.expression.Expression._maxima_ (sage/symbolic/expression.cpp:3415)
  File "sage_object.pyx", line 364, in sage.structure.sage_object.SageObject._interface_ (sage/structure/sage_object.c:3384)
  File "sage_object.pyx", line 451, in sage.structure.sage_object.SageObject._maxima_init_ (sage/structure/sage_object.c:5065)
  File "expression.pyx", line 443, in sage.symbolic.expression.Expression._interface_init_ (sage/symbolic/expression.cpp:3544)
  File "/home/jason/sage-4.0/local/lib/python2.6/site-packages/sage/symbolic/expression_conversions.py", line 214, in __call__
    return self.arithmetic(ex, operator)
  File "/home/jason/sage-4.0/local/lib/python2.6/site-packages/sage/symbolic/expression_conversions.py", line 497, in arithmetic
    args = ["(%s)"%self(op) for op in ex.operands()]
  File "/home/jason/sage-4.0/local/lib/python2.6/site-packages/sage/symbolic/expression_conversions.py", line 206, in __call__
    operator = ex.operator()
  File "expression.pyx", line 3088, in sage.symbolic.expression.Expression.operator (sage/symbolic/expression.cpp:15127)
RuntimeError: cannot find SFunction in table

Attachments (1)

trac_6636-factorial-simplify.patch (3.3 KB) - added by kcrisman 11 years ago.
Needs #6197

Download all attachments as: .zip

Change History (9)

comment:1 Changed 11 years ago by jbandlow

  • Cc burcin added

comment:2 Changed 11 years ago by kcrisman

A related discussion on sage-devel is http://groups.google.com/group/sage-devel/browse_thread/thread/58db110fc55b11e5.

The lack of simplification is a bug, or at least very poorly exposed functionality, in Maxima. One would think that simplify would include this... but instead one needs to expose Maxima's *minfactorial*:

(%i1) fullratsimp(factorial(n)/factorial(n-1));
                                      n!
(%o1)                              --------
                                   (n - 1)!
(%i2) minfactorial(factorial(n)/factorial(n-1));
(%o2)                                  n

This should not be hard to add to simplify_full, though.

Also note that the last issue is addressed by #6197.

comment:3 Changed 11 years ago by kcrisman

  • Summary changed from Simplification of factorials and binomial coefficients is not very good to [with patch, needs review] Simplification of factorials and binomial coefficients is not very good

The following patch should fix all of the issues on this ticket - Maxima has quite a bit of simplifying capability, but prefers to leave things unsimplified for further processing, as a rule. See examples for what now works. I have also changed simplify_full() to take this in, and hope that simplification of binomials and factorials first is best. This needs the patch at #6197 to function properly, since otherwise binomial isn't recognized by sage as something it can pass to Maxima.

Changed 11 years ago by kcrisman

Needs #6197

comment:4 Changed 11 years ago by kcrisman

  • Cc mhansen added

This has been slightly changed because the doctest fix here actually belonged in #6197. Otherwise still ready for review!

comment:5 follow-up: Changed 11 years ago by mhansen

  • Authors set to Karl-Dieter Crisman
  • Reviewers set to Mike Hansen
  • Summary changed from [with patch, needs review] Simplification of factorials and binomial coefficients is not very good to [with patch, positive review] Simplification of factorials and binomial coefficients is not very good

Looks good to me.

We might want to improve simplify_full so that we don't have 4 round trips to Maxima (convert to maxima, run all of the simplification commands on the MaximaElement?, and then finally convert back to an Expression.)

comment:6 in reply to: ↑ 5 Changed 11 years ago by kcrisman

We might want to improve simplify_full so that we don't have 4 round trips to Maxima (convert to maxima, run all of the simplification commands on the MaximaElement?, and then finally convert back to an Expression.)

That makes a lot of sense. Once this is merged, do you mind opening a ticket on that?

comment:7 Changed 11 years ago by mhansen

Sure thing.

comment:8 Changed 11 years ago by mvngu

  • Merged in set to Sage 4.1.2.alpha2
  • Resolution set to fixed
  • Status changed from new to closed
Note: See TracTickets for help on using tickets.