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!
| 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