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