New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Trivial bounds on binomial coefficients #8462

Open
pelegm opened this Issue Nov 17, 2014 · 5 comments

Comments

Projects
None yet
3 participants
@pelegm
Copy link
Contributor

pelegm commented Nov 17, 2014

This is a suggestion; I am ready to implement it, but I'll need a hint about how possible/easy it might be, and where to start.

In #5415 it is reported that limits of expressions involving function of several arguments, such as binomial(n, k), fail. Perhaps trivial bounds on binomial coefficients may help to solve this issue for the case where all such functions are binomial coefficients.

The trivial bounds are

\left(\frac{n}{k}\right)^k \le {n\choose k} \le \left(\frac{en}{k}\right)^k

Here's an illustration:

limit(binomial(n, n/2), n, oo)

fail with MRV set computation for functions in several variables not implemented.. But using the lower bound, we know that binomial(n, n/2) is at least 2**(n/2), and SymPy knows that the limit of this is infinity.

Similarly,

limit(binomial(n, n/2) * 3 ** (-n), n, oo)

fails, but the trivial upper bound yields that binomial(n, n/2) is at most (2*E)**(n/2), and since the expression is positive, the limit is 0 (as limit((2*E)**(n/2) * 3**(-n), n, oo) shows).

@certik

This comment has been minimized.

Copy link
Member

certik commented Nov 17, 2014

The limit code is using the Gruntz algorithm. I don't know if it can be extended for binomial expressions. If it can, that would be awesome.

@pelegm

This comment has been minimized.

Copy link
Contributor

pelegm commented Nov 18, 2014

Well, it seems that if you just replace the binomial with its definition using factorials, gruntz handles it quite well.

@skirpichev

This comment has been minimized.

Copy link
Contributor

skirpichev commented Nov 18, 2014

Probably, you can add the _eval_rewrite_as_tractable helper.

@pelegm

This comment has been minimized.

Copy link
Contributor

pelegm commented Nov 18, 2014

Could you elaborate?

@skirpichev

This comment has been minimized.

Copy link
Contributor

skirpichev commented Nov 18, 2014

Read the Gruntz thesis, ch. 5.

skirpichev added a commit to diofant/diofant that referenced this issue Dec 26, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment