Combinations Problem (math not excel)

Thanks Thanks:  0
Likes Likes:  0
Page 1 of 2 12 LastLast
Results 1 to 10 of 14

Thread: Combinations Problem (math not excel)

  1. #1
    MrExcel MVP mikerickson's Avatar
    Join Date
    Jan 2007
    Location
    Davis CA
    Posts
    21,302
    Post Thanks / Like
    Mentioned
    4 Post(s)
    Tagged
    0 Thread(s)

    Default 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. #2
    MrExcel MVP Eric W's Avatar
    Join Date
    Aug 2015
    Location
    Bountiful, UT
    Posts
    5,368
    Post Thanks / Like
    Mentioned
    15 Post(s)
    Tagged
    0 Thread(s)

    Default 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.
    Cheers,
    Eric

    When you eliminate the impossible, whatever remains, however improbable, must be the truth.

    -Posting guidelines, forum rules, terms of use, FAQs, BB codes, See how to search the forum
    -Post a screen shot with the HTML Maker

  3. #3
    MrExcel MVP
    Join Date
    Apr 2006
    Posts
    18,955
    Post Thanks / Like
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default 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) ...

    which means adding

    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.
    Last edited by pgc01; Mar 20th, 2017 at 12:20 PM.
    Kind regards
    PGC

    To understand recursion, you must understand recursion.

  4. #4
    MrExcel MVP
    Join Date
    Apr 2006
    Posts
    18,955
    Post Thanks / Like
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default 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.
    Last edited by pgc01; Mar 20th, 2017 at 06:29 PM.
    Kind regards
    PGC

    To understand recursion, you must understand recursion.

  5. #5
    MrExcel MVP
    Join Date
    Apr 2006
    Posts
    18,955
    Post Thanks / Like
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default 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
    Kind regards
    PGC

    To understand recursion, you must understand recursion.

  6. #6
    MrExcel MVP Eric W's Avatar
    Join Date
    Aug 2015
    Location
    Bountiful, UT
    Posts
    5,368
    Post Thanks / Like
    Mentioned
    15 Post(s)
    Tagged
    0 Thread(s)

    Default Re: Combinations Problem (math not excel)

    Nicely done!

    Just as a reference, the OEIS sequence is:

    https://oeis.org/A000110

    which seems to jibe with your answers.

    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.
    Cheers,
    Eric

    When you eliminate the impossible, whatever remains, however improbable, must be the truth.

    -Posting guidelines, forum rules, terms of use, FAQs, BB codes, See how to search the forum
    -Post a screen shot with the HTML Maker

  7. #7
    MrExcel MVP
    Join Date
    Apr 2006
    Posts
    18,955
    Post Thanks / Like
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default 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
    Kind regards
    PGC

    To understand recursion, you must understand recursion.

  8. #8
    MrExcel MVP
    Join Date
    Apr 2006
    Posts
    18,955
    Post Thanks / Like
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default 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))
    Last edited by pgc01; Mar 20th, 2017 at 07:38 PM.
    Kind regards
    PGC

    To understand recursion, you must understand recursion.

  9. #9
    MrExcel MVP
    Join Date
    Apr 2006
    Posts
    18,955
    Post Thanks / Like
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default Re: Combinations Problem (math not excel)

    Quote Originally Posted by Eric W View Post
    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.
    Kind regards
    PGC

    To understand recursion, you must understand recursion.

  10. #10
    MrExcel MVP
    Join Date
    Apr 2006
    Posts
    18,955
    Post Thanks / Like
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    Default 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?
    Kind regards
    PGC

    To understand recursion, you must understand recursion.

User Tag List

Like this thread? Share it with others

Like this thread? Share it with others

Posting Permissions

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

 

 
DMCA.com