Associated Topics || Dr. Math Home || Search Dr. Math

### Onto Functions and Stirling Numbers

```Date: 09/22/2002 at 23:51:10
From: Tom
Subject: Onto Functions and Stirling Numbers

Hello Dr. Math,

I don't know if you can help me with this question but how would I
show for m >= 3

s(m, m-2) = (1/24)m(m-1)(m-2)(3m-1)

where s(m,n) are referred to as the Stirling numbers of the first
kind?

Is there a formula for the Stirling numbers of the first kind that I
could use?

Thank you.
```

```
Date: 09/23/2002 at 13:06:47
From: Doctor Anthony
Subject: Re: Onto Functions and Stirling Numbers

We use S(n,m) to denote Stirling Numbers of the First Kind. It
represents the number of ways to seat n people at m circular tables
with at least one person at each table. The arragements at any one
table are not distinguished if one can be rotated into another.
The ordering of the tables is NOT taken into account. Briefly,
these numbers count the number of arrangements of n objects into
m non-empty circular permutations.

The generating function for S(n,m) is the coefficient of x^m in the
expansion of x(x-1)(x-2)....(x-n+1)

The numbers satisfy the recurrence relation

S(n+1,r) = S(n,r-1) + n.S(n,r)

We have  S(n,1) = (n-1)!
S(n,n) = 1
S(n,n-1) = C(n,2)  (select 2 persons for one table)

We get the following table using the recurrence relation:

r
|   1    2    3    4    5    6 ....
------|-------------------------------------
1   |   1
2   |   1    1
n  3   |   2    3    1
4   |   6   11    6    1
5   |  24   50   35   10    1
6   | 120  274  225   85   15    1

And using the generating function, S(5,2)

is coefficient of  x^2 in  x(x-1)(x-2)...(x-5+1)
= x(x-1)(x-2)(x-3)(x-4)

= x^5 - 10x^4 + 35x^3 - 50x^2 + 24x

and we can see that |coefficient| of x^2 is 50.

The other coefficients also give the required terms in row 5 of above
table.

Example.
--------
In how many ways can six people be seated round 3 identical tables if
there is at least one person at each table?

From the above table we find   S(6,3) = 225

To get the recurrence relation from first principles, suppose we have
distributed 5 people in S(5,2) or S(5,3) ways. That is, all five are
at all 3 tables or at only 2 tables and we then add a sixth person.
If only at two tables, then the 6th person MUST go to the empty table.
He could be placed in one way and we get a term S(5,2) in this
situation.

If the 5 people are distributed at 3 tables there will be 5 gaps that
the extra person could occupy, and so the contribution in this
situation to the new total is  5 x S(5,3).

It follows that   S(6,3) = S(5,2) + 5 x S(5,3)

Check from the table above:

S(5,2) + 5 x S(5,3)

50 + 5 x 35  =  225  =  S(6,3)

Now turning to your question, we are asked to show

S(m,m-2) = (1/24)m(m-1)(m-2)(3m-1)

We showed earlier that S(m,m-1) = C(m,2)

That is, we have m people and have to select two to sit together at
one of the tables.  It does not matter which table, and with just two
at the table you cannot change the order.

For S(m,m-2) we have m-2 tables and m people.  We could have 3 at one
table and 1 at each of the other tables. The 3 persons are chosen in
C(m,3) ways and they can be arranged in 2 ways at the table.  This
gives 2 x C(m,3) arrangements.  Alternatively we could have 2 at two
tables and 1 at each of the other tables.  This could be done in
C(m,4) x C(4,2)/2 ways.

Notice that we divide by 2 because the number of WAYS of dividing 4
into 2 groups of 2 is C(4,2)/2, since when we select 2 that
automatically selects the other 2.

Combining these answers we get

S(m,m-2) = 2 x C(m,3) + C(m,4) x C(4,2)/2

2 x m(m-1)(m-2)     m(m-1)(m-2)(m-3)x 3
= ----------------- + --------------------
3!                   4!

m(m-1)(m-2)[8 + 3(m-3)]
=  -----------------------
24

m(m-1)(m-2)(3m-1)
= -------------------
24

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search