Combinations Problem (math not excel)

[mikerickson]

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.

 

[StephenCrump]

Can it be that easy?

Yes. It follows directly from the recursive relationship you identified:

Is there an upper limit to the number of people who can sit at a table? If so, the member/table problem will start to diverge from the Bell numbers once n exceeds that number.

You'll also get divergence if you put some bounds at the lower end. I'm not tempted to join Mike's "club" if 25 of us come for dinner and we all sit at separate tables .

 

[mikerickson]

One thing I wondered about though. Is there an upper limit to the number of people who can sit at a table? If so, the member/table problem will start to diverge from the Bell numbers once n exceeds that number.

No limit to the number of people at a table or the number of tables in the room.

Thanks to all for all of this, I see that I have a bit of studying to understand the math behind this.

 

[pgc01]

Yes. It follows directly from the recursive relationship you identified:

Yes, that's what I noticed at the end. I was pleasantly surprised that the solution was such a simple formula.

 

[pgc01]

Now, a perfect ending to this thread will be to come up with a closed formula (no loops, no recursion) for a Bell number.

No one in the world has ever been able to do it, but that does not not frighten us.