combinat1 http://www.openmath.org/cd/combinat1.ocd 2003-04-01 1999-05-17 2 0 experimental alg1 arith1 fns1 fns2 integer1 interval1 linalg1 linalg2 list2 logic1 relation1 This CD defines some basic combinatorics definitions. Written by S. Dalmas (INRIA Sophia Antipolis) for the Esprit OpenMath project. binomial The binomial coefficients. binomial(n, m) is the number of ways of choosing m objects from a collection of n distinct objects without regard to the order. binomial(n,m) = n!/(m!*(n-m)!) 4 2 6 multinomial The multinomial coefficients. multinomial(n, n1, ... nk) is the number of ways of choosing ni objects of type i (i from 1 to k) without regard to order, in such a way that the total number of objects chosen is n. multimomial(n, n1, ... nk) is equal to n!/(n1!*n2! ...*nk!). multimomial(n, n1, ... nk) is equal to n!/(n1!*n2! ...*nk!) where n=n1+...+nk 8 2 3 3 560 Stirling1 The Stirling numbers of the first kind. (-1)^(n-m)*Stirling1(n,m) is the number of permutations of n symbols which have exactly m cycles. Note that there are a few slightly different definitions of these numbers. Stirling1(n,m) = the sum k=0 to n-m of (-1)^k * binomial(n-1+k, n-m+k) * binomial(2n-m,n-m-k) * Stirling2(n,m) 2 10 7 -9450 Stirling2 The Stirling numbers of the second kind. Stirling2(n, m) is the number of partitions of a set with n elements into m non empty subsets. Note that there are a few slightly different definitions of these numbers. Stirling2(n,m) = 1/m! * the sum from k=0 to m of (-1)^(m-k) * binomial(m,k) * k^n 7 3 301 Fibonacci The Fibonacci numbers, defined by the linear recurrence: Fibonacci(0) = 0, Fibonacci(1) = 1, and Fibonacci(n + 1) = Fibonacci(n) + Fibonacci(n - 1). Note that some authors define Fibonacci(0) = 1. Fibonacci(0) = 0, Fibonacci(1) = 1, and Fibonacci(n + 1) = Fibonacci(n) + Fibonacci(n - 1) 10 55 Bell The Bell numbers: Bell(n) is the total number of possible partitions of a set of n elements. Bell(n) = the sum from k=0 to n of Sterling2(n,k) 7 877