mikerickson
MrExcel MVP
- Joined
- Jan 15, 2007
- Messages
- 24,355
There is a supper club. They have a dining room with tables. Members come to a dinner (or not), sit at a table (don't switch tables) and eat.
If the club has n members, how many different dinners can they have? (denoted D
)
1) a member may or may not attend a dinner
2) the order of seating at a table does not matter.
ABC sitting a table is the same as CBA sitting at a table
3) the order of the tables does not matter.
AB at one table, C at another and D at another (denoted by AB, C, D) is the same a C, AB, D
Examples:
If n=0, there is only one possible dinner, the dinner where on one attends. D(0) = 1
If n=1, there are two possible dinners, the null dinner and the dinner where A sits alone.
D(1)=2
[no one]
A
If n=2, D(2)=4
[no one]
A (A attends, B does not)
B (B attends, A does not)
A, B (A and B sit at different tables)
AB (A and B sit at the same table)
n=3 D(3)=15
[-]
A
B
C
A, B
A, C
A, B, C
B, C
AB
AB, C
AC
AC, B
BC
BC, A
ABC
What is a general formula for D
?
I thought that I had a recursive rule.
Let D(n,k) be the number of possible dinners of a club with n members where the largest table size has exactly k diners.
D(3,3)=1, D(3,2)=6, D(3,1)=7, D(3,0)=1
D
= sum(k=0 to n) D(n,k)
INCORRECT RULE:
D(n, k)= COMBIN(n,k) * D(n-k)
This fails because it creates duplicates.
Does anyone have a notion of how to calculate D(N) other than "list them all"?
Thank you.
If the club has n members, how many different dinners can they have? (denoted D
1) a member may or may not attend a dinner
2) the order of seating at a table does not matter.
ABC sitting a table is the same as CBA sitting at a table
3) the order of the tables does not matter.
AB at one table, C at another and D at another (denoted by AB, C, D) is the same a C, AB, D
Examples:
If n=0, there is only one possible dinner, the dinner where on one attends. D(0) = 1
If n=1, there are two possible dinners, the null dinner and the dinner where A sits alone.
D(1)=2
[no one]
A
If n=2, D(2)=4
[no one]
A (A attends, B does not)
B (B attends, A does not)
A, B (A and B sit at different tables)
AB (A and B sit at the same table)
n=3 D(3)=15
[-]
A
B
C
A, B
A, C
A, B, C
B, C
AB
AB, C
AC
AC, B
BC
BC, A
ABC
What is a general formula for D
I thought that I had a recursive rule.
Let D(n,k) be the number of possible dinners of a club with n members where the largest table size has exactly k diners.
D(3,3)=1, D(3,2)=6, D(3,1)=7, D(3,0)=1
D
INCORRECT RULE:
D(n, k)= COMBIN(n,k) * D(n-k)
This fails because it creates duplicates.
Does anyone have a notion of how to calculate D(N) other than "list them all"?
Thank you.