[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:
Martin
Index: combfunc.spad.pamphlet
===================================================================
--- combfunc.spad.pamphlet (Revision 470)
+++ combfunc.spad.pamphlet (Arbeitskopie)
@@ -1,5 +1,5 @@
\documentclass{article}
-\usepackage{axiom}
+\usepackage{axiom, amsmath, amsfonts}
\begin{document}
\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
+
+\begin{verbatim}
+ binomial(n, m) ==
+ n < 0 or m < 0 or m > n => 0
+ m = 0 => 1
+\end{verbatim}
+
+Of course, here [[n]] and [[m]] are integers. This definition agrees with the
+recurrence
+
+$$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.$$
+
+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
+have
+$$\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
+hand,
+$$\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
+here.
+
+<<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>>=
+
else
iibinom l ==
(r1 := retractIfCan(first l)@Union(R,"failed")) case "failed" or
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Axiom-developer] patch for binomial coefficient / bug 336,
Martin Rubey <=