You have n colors and you make nonempty sets from them. A set of these color sets is color balanced if each color is in the same number of the color sets.
Ex. For n=3, using Red Green Blue (RGB) as the colors, the set { {RG}, {RB}, {GB} } would be color balanced as each color is in two color sets. As would:
{ {R}, {G}, {B} }
{ {B}, {G}, {RB}, {RG} }
{ {RGB}, {R}, {BG}}
{ }
{ {RGB}, {RG}, {RB}, {GB}, {R}, {G}, {B}}
The sets { {R}, {G} } and { {RGB}, {R}, {G} } would not be color balanced for n=3, as Blue (B) fails to appear in as many color sets as Red (R) and Green (G).
How many color balanced sets can you create with n colors? The obvious brute force method is to a. enumerate all the color sets b. enumerate all sets of color sets and check each one for color balance. With this I found:
3 colors: 20 color balanced sets
4 colors: 880
5 colors: 5,280,908
(code) But this requires $2^{2^n}$ color balance checks, which is obviously intractable for larger n.
Question: Is there a more tractable algorithm or combinatoric trick for finding the number of color balanced sets you can make with n colors? How many color balanced sets are there using 7 colors?
We've broached this subject before, though not with this particular question. Dan Uznanski came up with a list of primitive canonical groups for n=5, where all non-primitive color balanced sets are combinations of these primitive groups. That seems like a promising direction, but it's not clear to me how you'd actually form and count the non-canonical sets from these primitive bases, or if you can actually find the primitives without brute forcing (as I think Dan did).
The motivation for this question was the same: Magic the Gathering expansions are almost always divided into "factions" that have colors associated with them (the color sets). One of the most popular expansions, for instance, is divided by all the 2-color pairs (Green-Blue, Green-Red, Green-White, Green-Black, Blue-Red etc). The factions have always been color balanced within the expansion, and I was curious exactly how many configurations there were.
