Next: , Previous: Random Numbers, Up: Scientific Functions

8.6 Combinatorial Functions


The k g (calc-gcd) [gcd] command computes the Greatest Common Divisor of two integers. It also accepts fractions; the GCD of two fractions is defined by taking the GCD of the numerators, and the LCM of the denominators. This definition is consistent with the idea that ‘a / gcd(a,x)’ should yield an integer for any ‘a’ and ‘x’. For other types of arguments, the operation is left in symbolic form.


The k E (calc-extended-gcd) [egcd] command computes the GCD of two integers ‘x’ and ‘y’ and returns a vector ‘[g, a, b]’ where g = gcd(x,y) = a x + b y’.


The k d (calc-double-factorial) [dfact] command computes the “double factorial” of an integer. For an even integer, this is the product of even integers from 2 to ‘N’. For an odd integer, this is the product of odd integers from 3 to ‘N’. If the argument is an integer-valued float, the result is a floating-point approximation. This function is undefined for negative even integers. The notation ‘N!!’ is also recognized for double factorials.

The k c (calc-choose) [choose] command computes the binomial coefficient ‘N’-choose-‘M’, where ‘M’ is the number on the top of the stack and ‘N’ is second-to-top. If both arguments are integers, the result is an exact integer. Otherwise, the result is a floating-point approximation. The binomial coefficient is defined for all real numbers by N! / M! (N-M)!’.

The H k c (calc-perm) [perm] command computes the number-of-permutations function ‘N! / (N-M)!’.

The k b (calc-bernoulli-number) [bern] command computes a given Bernoulli number. The value at the top of the stack is a nonnegative integer ‘n’ that specifies which Bernoulli number is desired. The H k b command computes a Bernoulli polynomial, taking ‘n’ from the second-to-top position and ‘x’ from the top of the stack. If ‘x’ is a variable or formula the result is a polynomial in ‘x’; if ‘x’ is a number the result is a number.


The k s (calc-stirling-number) [stir1] command computes a Stirling number of the first kind, given two integers ‘n’ and ‘m’ on the stack. The H k s [stir2] command computes a Stirling number of the second kind. These are the number of ‘m’-cycle permutations of ‘n’ objects, and the number of ways to partition ‘n’ objects into ‘m’ non-empty sets, respectively.


The normal k p command performs one iteration of the primality test. Pressing k p repeatedly for the same integer will perform additional iterations. Also, k p with a numeric prefix performs the specified number of iterations. There is also an algebraic function ‘prime(n)’ or ‘prime(n,iters)’ which returns 1 if ‘n’ is (probably) prime and 0 if not.




The k t (calc-totient) [totient] command computes the Euler “totient” function, the number of integers less than ‘n’ which are relatively prime to ‘n’.

The k m (calc-moebius) [moebius] command computes the Moebius “mu” function. If the input number is a product of ‘k’ distinct factors, this is ‘(-1)^k’. If the input number has any duplicate factors (i.e., can be divided by the same prime more than once), the result is zero.