[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Axiom-developer] patch for binomial coefficient / bug 336

From: Martin Rubey
Subject: [Axiom-developer] patch for binomial coefficient / bug 336
Date: 28 Mar 2007 10:38:13 +0200
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4

I just did svn up, many thanks for including the patches. However, for some
reason the documentation I provided for iibinom was not included. I take the
oportunity to elaborate, here is the documentation patch:


Index: combfunc.spad.pamphlet
--- combfunc.spad.pamphlet      (Revision 470)
+++ combfunc.spad.pamphlet      (Arbeitskopie)
@@ -1,5 +1,5 @@
+\usepackage{axiom, amsmath, amsfonts}
 \title{\$SPAD/src/algebra combfunc.spad}
 \author{Manuel Bronstein, Martin Rubey}
@@ -88,6 +88,53 @@
     binomial   : (F, F) -> F
       ++ binomial(n, r) returns the number of subsets of r objects
       ++ taken among n objects, i.e. n!/(r! * (n-r)!);
+We currently simplify binomial coefficients only for non-negative integral
+second argument, using the formula
+$$ \binom{n}{k}=\frac{1}{k!}\prod_{i=0..k-1} (n-i),$$
+except if the second argument is symbolic: in this case [[binomial(n,n)]] is
+simplified to one.
+Note that there are at least two different ways to define binomial coefficients
+for negative integral second argument. One way, particular suitable for
+combinatorics, is to set the binomial coefficient equal to zero for negative
+second argument. This is, partially, also the approach taken in
+[[combinat.spad]], where we find
+   binomial(n, m) ==
+      n < 0 or m < 0 or m > n => 0
+      m = 0 => 1
+Of course, here [[n]] and [[m]] are integers. This definition agrees with the
+Alternatively, one can use the formula
+$$ \binom{n}{k}=\frac{\Gamma(n+1)}{\Gamma(k+1)\Gamma(n-k+1)}, $$
+and leave the case where $k\in\mathbb Z$, $n\in\mathbb Z$ and $k \leq n < 0$
+undefined, since the limit does not exist in this case:
+Since we then have that $n-k+1\geq 1$, $\Gamma(n-k+1)$ is finite. So it is
+sufficient to consider $\frac{\Gamma(n+1)}{\Gamma(k+1)}$. On the one hand, we
+$$\lim_{n_0\to n} \lim_{k_0\to k}\frac{\Gamma(n_0+1)}{\Gamma(k_0+1)} = 0,$$
+since for any non-integral $n_0$, $\Gamma(n_0+1)$ is finite. On the other
+$$\lim_{k_0\to k} \lim_{n_0\to n}\frac{\Gamma(n_0+1)}{\Gamma(k_0+1)}$$
+does not exist, since for non-integral $k_0$, $\Gamma(k_0+1)$ is finite while
+$\Gamma(n_0+1)$ is unbounded.
+However, since for $k\in\mathbb Z$, $n\in\mathbb Z$ and $0 < k < n$ both
+definitions agree, one could also combine them. This is what, for example,
+Mathematica does. It seems that MuPAD sets [[binomial(n,n)=1]] for all
+arguments [[n]], and returns [[binomial(-2, n)]] unevaluated. Provisos may help
+<<package COMBF CombinatorialFunction>>=
     permutation: (F, F) -> F
       ++ permutation(n, r) returns the number of permutations of
       ++ n objects taken r at a time, i.e. n!/(n-r)!;
@@ -539,6 +586,16 @@
                => ibinom l
            binomial(r1::R, r2::R)::F
+[[iibinom]] checks those cases in which the binomial coefficient may be
+evaluated explicitly. Note that up to [[patch--51]], the case where the second
+argument is a positive integer was not checked.(Issue~\#336) Currently, the
+naive iterative algorithm is used to calculate the coefficient, there is room
+for improvement here.
+<<package COMBF CombinatorialFunction>>=
          iibinom l ==
            (r1 := retractIfCan(first l)@Union(R,"failed")) case "failed" or

reply via email to

[Prev in Thread] Current Thread [Next in Thread]