The number of sections with a given limit

Question

Consider a set of 13 Danish, 11 Japanese and 8 Polish people. It is well known that the number of different ways of dividing this set of people into groups is number 13 + 11 + 8 = 32: Bell's number (the number of given sections). However, we will be asked to find the number of possible partition sets for a given restriction. The question is this:

The established division is called good if it does not have a group of at least two people, which includes only one citizenship. How many good sections are there for this set? (A group may include only one person.)

The brute force approach requires a transition, although about 10 ^ 26 sections and checking which ones are good. This seems rather impracticable, especially if the groups are larger or introduce other nationalities. Is there any reasonable way?

EDIT: As a note. There is probably no hope for a really good solution. A senior expert on combinatorics answered a question related to him, which, I think, basically says that the problem is related to this and, therefore, this problem is also very difficult to solve accurately.

Answer 1

It uses a solution using dynamic programming.

, .

, , :

• , . (: {a})
• . (: {a, b, c})

. :

[0, 1, 2, 2] -> 3
{a}{b}{c}{mixed} 
   e.g.: 3 partitions that look like: {b}, {c}, {c}, {a,c}, {b,c}

python:

import collections
from operator import mul
from fractions import Fraction

def nCk(n,k):
  return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )

def good_partitions(l):
    n = len(l)
    i = 0
    prev = collections.defaultdict(int)
    while l:
        #any more from this kind?
        if l[0] == 0:
            l.pop(0)
            i += 1
            continue
        l[0] -= 1
        curr = collections.defaultdict(int)

        for solution,total in prev.iteritems():
            for idx,item in enumerate(solution):
                my_solution = list(solution)
                if idx == i:
                    # add element as a new set
                    my_solution[i] += 1
                    curr[tuple(my_solution)] += total
                elif my_solution[idx]:
                    if idx != n:
                        # add to a set consisting of one element
                        # or merge into multiple sets that consist of one element
                        cnt = my_solution[idx]
                        c = cnt
                        while c > 0:
                            my_solution = list(solution)
                            my_solution[n] += 1
                            my_solution[idx] -= c
                            curr[tuple(my_solution)] += total * nCk(cnt, c)
                            c -= 1
                    else:
                        # add to a mixed set
                        cnt = my_solution[idx]
                        curr[tuple(my_solution)] += total * cnt

        if not prev:
            # one set with one element
            lone = [0] * (n+1)
            lone[i] = 1
            curr[tuple(lone)] = 1

        prev = curr
    return sum(prev.values())

print good_partitions([1, 1, 1, 1])      # 15
print good_partitions([1, 1, 1, 1, 1])   # 52
print good_partitions([2, 1])            # 4
print good_partitions([13, 11, 8])       # 29811734589499214658370837

. ( ), .

Answer 2

, + .

, . , , .

, - .

m is the maximum group size we can emit

p is the number of people of each nationality that we have left to split

max_good_partitions_of_maximum_size(m, p) is the number of "good partitions"
we can form from p people, with no group being larger than m

, , , p. , max_good_partitions_of_maximum_size(p, p) p = [13, 11, 8]. , .

, https://en.wikipedia.org/wiki/Memoization . .