Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

number of seatings

10 views
Skip to first unread message

Ed Jones

unread,
Aug 8, 2003, 10:34:59 PM8/8/03
to

In how many ways can n people be seated in m chairs if there is 1 person per
chair and its not necessary to seat all/any of the people? I have a solution
but it's not near as pretty as I'd like. I'm looking for a formula that does
not require summation.

Using recursion results in an equation with two variables (n people and m
chairs):

a(n,m) = a(n,m-1) + n*a(n-1,m-1) = a(n-1,m) + m*a(n-1,m-1) which also yields
(m-n)*a(n,m) = =m*a(n,m-1) - n*a(n-1,m)

For example, such a seating with 3 people and 2 chairs would result in
a(3,2) = a(3,1) + 3*a(2,1) = 4 + 3*3 = 13.

Using the fact that a(i,j)=a(j,i)and a(n,1) = n+1, I figured I could make
the assumption that n>m and reduce the recursion algebraically for m-1 steps
to get an answer but it gets ugly very quickly. It's been a long time since
I've worked with characteristic equations with more than one index and I'm a
bit rusty. A solution using this would be greatly appreciated. Heck, even a
URL describing how to do multivariable generating functions would be
appreciated.

I can solve it using counting techniques as:

a(n,m) = Sumfrom_0_to_min{m,n}[C(n,i)*P(m,i)] so that

a(3,2) = C(3,0)P(2,0) + C(3,1)P(2,1) + C(3,2)P(2,2) = 1+6+6 = 13 as above.

This requires 2*(min{m,n}+1) calulations. By the way, for you
graph-theorists, this is the same as the number of subgraphs of K(m,n)
(distinct vertices) with no vertex having degree more than 1. Anyhow, my gut
tells me:
a)there is a simpler way of doing it that results in a simple calculation or
two and,
b)I'll probably be embarassed when I see it.

Here is some sample data (I'll bet the columns don't line up, sorry):

C H A I R S
0 1 2 3 4 5 6
7 8
0 1 1 1 1 1 1 1
1 1
1 1 2 3 4 5 6 7
8 9
P 2 1 3 7 13 21 31 43
57 73
E 3 1 4 13 34 73 136 229
358 529
O 4 1 5 21 73 209 501 1045 1961
3393
P 5 1 6 31 136 501 1546 4051 9276
19081
L 6 1 7 43 229 1045 4051 13327 37633
93289
E 7 1 8 57 358 1961 9276 37633 130922
394353

Thanks!

The Last Danish Pastry

unread,
Aug 9, 2003, 6:10:12 AM8/9/03
to
I may have no idea about your problem, but I _can_ line your columns up for
you, when viewed in a fixed-width font such as Courier:

| C H A I R S
| 0 1 2 3 4 5 6 7 8
|
| 0 1 1 1 1 1 1 1 1 1
| 1 1 2 3 4 5 6 7 8 9
|P 2 1 3 7 13 21 31 43 57 73
|E 3 1 4 13 34 73 136 229 358 529
|O 4 1 5 21 73 209 501 1045 1961 3393
|P 5 1 6 31 136 501 1546 4051 9276 19081
|L 6 1 7 43 229 1045 4051 13327 37633 93289
|E 7 1 8 57 358 1961 9276 37633 130922 394353

--
Clive Tooth
http://www.clivetooth.dk


0 new messages