From: Robin Chapman Newsgroups: rec.puzzles,sci.math Subject: Re: Cobinatorics question Date: Fri, 12 Jun 1998 07:54:59 GMT In article <6lofa9$mca$1@sucker.nl.uu.net>, "news.nl.net" wrote: > > How many possibilities are there to divide n people in groups? > If a "group" is a non-empty set, then the answer is B_n the n-th Bell number. Adopting the convention B_0 = 1 these satifty the recurrence B_{n+1} = B_n + (n choose 1) B_{n-1} + (n choose 2) B_{n-2} + ... + B_0. They occur as coefficients in the power series exp(exp(x) - 1) = B_0 + B_1 x + B_2 x^2/2! + B_3 x^3/3! + ... The first few values are n B_n 0 1 1 1 2 2 3 5 4 15 5 52 6 203 7 877 8 4140 9 21147 10 115975. They are related to Stirling numbers (of the second kind) S(n,k), which is the number of ways of dividing n people into k "groups". So B_n is the sum of S(n,k) over all k. For more on these ideas, see Wilf's generatingfunctionology, or Graham/Knuth/Patashnik's Concrete Mathematics. Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading