From: axel@neurose.uet.e-technik.th-darmstadt.de (Axel Glaeser) Newsgroups: sci.math Subject: P: Variations and Permutations Date: 16 Oct 1995 09:14:10 GMT Keywords: Variation Permutation Hi everybody, I have the following problem: I have p differnt balls. They should be distributed to n similar boxes in a way that no box is empty. My questions are: 1. How many possibilities do exist for solving this problem? For small numbers of n and p the results lokk like this: n p possibilities 3 4 6 2 3 3 2 4 7 4 5 10 x x 1 2. How would an algorithm look like, which calculates all these possibilities? I hope this problem is not too trivial for this newsgroup. Thanks in advance for anybody who can give me usefull hints! ******************************************************** A.Glaeser@uet.th-darmstadt.de A. Glaeser Technical University of Darmstadt Institute of Telecommunications and Electroacoustics Merckstr. 25 64283 Darmstadt Germany ******************************************************** ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: P: Variations and Permutations Date: 19 Oct 1995 05:44:53 GMT Keywords: Variation Permutation In article <45t7p2$rqc@rs18.hrz.th-darmstadt.de>, Axel Glaeser wrote: >I have p differnt balls. They should be distributed to n similar boxes in a way >that no box is empty. > 1. How many possibilities do exist for solving this problem? > 2. How would an algorithm look like, which calculates all these possibilities? Based on your accompanying table, you seem to mean "indistinguishable" boxes. Your questions ask, "How may p different people be divided into n teams?" Who's in the box with ball #1? You have 2^(p-1) ways to answer that question. For each answer, you need to count the number of ways to pack the remaining balls into the remaining boxes. Thus if we call the number F(p,n), you have F(p,n) = Sum_{i=0}^{i=p-1} (p-1 choose i)*F(i,n-1). This gives you your recursive relationship (starting with F(p,1)=1 for all p). Actually it's a little cleaner to work with n and q = p-n (q >= 0). If we set G(q,n)=F(q+n,n), then G may be computed recursively with G(q,1)=1 for all q, and G(q,n+1) = Sum( (n+q choose q-k)*G(k,n), k=0..q ) Summing and cancelling leads, after a bit, to G(q, n) = Sum( Sum( (q+r choose q-k)*G(k,r), k=0..q-1), r=1..n-1)+1 from which we can obtain closed formulae G(0,n)=1 G(1,n)=n(n+1)/2 G(2,n)=n(n+1)(n+2)(3n+1)/24 G(3,n)=n^2(n+1)^2(n+2)(n+3)/48 which agree with the poster's tabulated values. (In general, G(q,n) is a polynomial of degree 2q in n.) Possibly there is an even more succint calculation of all the G(q,n)'s -- surely this is a known problem. As far as a method of enumerating all the partitions, one may simply use the description above to create a recursive routine: procedure package(S=set of balls); return a collection of subsets begin pick s1 in S; let S1=S-{s1}; for T subseteq S1 do let U = complement of T in S1 foreach P in package(U), spit out "T union{s1} , P" od end dave ============================================================================== From: "Timothy Chow" Date: Mon, 17 Feb 1997 14:59:37 -0500 (EST) To: rusin@math.niu.edu Subject: www.math.niu.edu/~rusin/known-math [deletia] 3. The number of ways to group p people into n teams is called the Stirling number of the second kind. A good reference is Graham, Knuth, and Patashnik's book _Concrete_Mathematics_. [deletia] Tim. ==============================================================================