Thanks:  0
Likes:  0

Thread: Combinations Problem (math not excel)

1. Combinations Problem (math not excel)

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(n))

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(n)?

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(n) = 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.

2. Re: Combinations Problem (math not excel)

These are always tricky types of problems. Without really analyzing it, I would refer you to the Online Encyclopedia of Integer Sequences. Plugging in 1,2,4,15 results in several hits, including:

https://oeis.org/A181442

I do not claim that the formula there is the one for your problem, but it's certainly worth looking at.

3. Re: Combinations Problem (math not excel)

Hi Mike

Interesting problem.

I would divide it according to the number of the diners that attend.

1 - all the diners attend
In this case I think you want all the possible ways that a set can be divided in disjointed subsets.
This is given by a Bell number. This is a known number that has a recursive formula to be calculated.
Result: B(n)

2 - one diner does not come.
There are n diners and so n possibilities.
Result: n * B(n-1)

3 - 2 diners do not come.
There are n*(n-1)/2 = C(n,2) possibilities.
Result: C(n,2) * B(n-2)

... and so on.

In conclusion, the formula would be

D(n) = B(n) + n * B(n-1) + C(n,2) * B(n-2) ...
or
D(n) = C(n,0) * B(n) + C(n,1) * B(n-1) + C(n,2) * B(n-2) ...

C(n,k) * B(n-k)

for k=0 ... n-1

You can calculate the Bell numbers with recursion and then do a loop or...

this is interesting to solve recursively. You'll have a double recursion, the Bell number is calculated with recursion and the sum of all the terms is also calculated recursively.

I'm at a lunch break but if no one solves it until tonight (GMT) I'll give it a go.

If you're not familiar with the Bell numbers, the recursive formula for the Bell number is:

B(0)=1, B(1)=1
B(n+1) = add C(n,k) * B(k) for k=0 to n

You can find easily information about the Bell (and the related Stirling) numbers

As I said I'm at a lunch break, did not think it through.

4. Re: Combinations Problem (math not excel)

OK. I don't have much time today but I was curious to see how quick these numbers grow.

I just used a simple loop assuming more than 1 member.

The numbers grow really quickly. For 2 members I get 5 dinners (you missed 1), for 3 members 15, for 10 members 678,570 and for 25 members 49,631,246,523,618,756,274 dinners

I used decimals to get all the digits.

Code:
```Sub Dinners()
Dim bN() As Variant, DN As Variant
Dim j As Long, k As Long

Const N As Long = 25
ReDim bN(0 To N)

' calculate the Bell numbers
bN(0) = CDec(1)
bN(1) = CDec(1)

For j = 2 To N
For k = 0 To j - 1
bN(j) = bN(j) + bN(k) * Application.Combin(j - 1, k)
Next k
Next j

' D(n) = C(n,0) * B(n) + C(n,1) * B(n-1) + C(n,2) * B(n-2) ...
' calculate the number of dinners
For k = 0 To N
DN = DN + Application.Combin(N, k) * bN(N - k)
Next k

Debug.Print Format(DN, "#,##0")
End Sub```
In conclusion
It's easy to see if the solution is good. You just gather 25 people in a room, try all the dinner combinations and see if it checks.

5. Re: Combinations Problem (math not excel)

No need for the 2 loops:

Code:
```Sub Dinners2()
Dim bN() As Variant, DN As Variant
Dim j As Long, k As Long

Const N As Long = 25
ReDim bN(0 To N)

bN(0) = CDec(1)
bN(1) = CDec(1)
DN = CDec(1) + N

For j = 2 To N
For k = 0 To j - 1
bN(j) = bN(j) + bN(k) * Application.Combin(j - 1, k)
Next k
DN = DN + Application.Combin(N, j) * bN(j)
Next j

Debug.Print Format(DN, "#,##0")
End Sub```

6. Re: Combinations Problem (math not excel)

Nicely done!

Just as a reference, the OEIS sequence is:

https://oeis.org/A000110

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.

7. Re: Combinations Problem (math not excel)

ABCDEFGHIJKLMNO
1
2N10 1
3DN678,570 12
4   235
5   571015
6   1520273752
7   526787114151203
8   203255322409523674877
9   8771080133516572066258932634140
10   4140501760977432908911155137441700721147
11   211472528730304364014383352922640777782194828115975
12   115975137122162409192713229114272947325869389946467767562595678570
13
[Book1]Sheet1

8. Re: Combinations Problem (math not excel)

oops, forgot the formulas

A formula solution:

Auxiliary table with the Bell numbers:

D2: =1
D3: =LOOKUP(1,-1/D2:Z2,D2:Z2)
Copy down
E3: =IF(D2="","",D3+D2)
Copy down and across

Result in B3:
=SUMPRODUCT(COMBIN(B2,ROW(INDIRECT("1:"&B2+1))-1),D2:INDEX(D:D,B2+2))

9. Re: Combinations Problem (math not excel)

Originally Posted by Eric W
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.
Eric, you are right, there is no upper limit to how many people sit at a table.

I just used Mike's 3 conditions when he describes the problem.

If you want to set a limit to people at a table then this solution does not give you the right result.

10. Re: Combinations Problem (math not excel)

Wow!

I just noticed that my formula:

D(n) = C(n,0) * B(n) + C(n,1) * B(n-1) + C(n,2) * B(n-2) ...

is the same that you use to get the next Bell number.

So the solution to the problem is just DN=B(n+1).

or in the formula solution, read the values to the right of the triangle or the next value in the first column.

Can it be that easy?

User Tag List

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•