How many combinations of coloured dots (with restrictions)?

Question

My friend is designing a logo. The logo can essentially be reduced to 24 coloured dots arranged in a circle, and they can be either red or white. We want to produce a individual variation of this logo for each employee. That, if I have worked it out right, (since this appears analogous to a 24-bit binary string), means we could have an individual logo for 2^24 employees, obviously way more than we need.

But of course, we don't really want logos that don't have a lot of white dots as they may look too sparse. So we stipulate that there must always be at least half + 1 = 13 in the logo. How many combinations does that restrict us to?

My initial thought is 12 (half) + 1 + 2^11, but I'm not good enough to prove it.

Also, how can we generalise this formula for $x$ dots, $y$ individual colours and at least $n$ colours of a single type? If that's too general, what about just the case $y = 2$ as we have above?

Answer 1

There are $\binom{24}{12}$ $12$-element subsets of the $24$ positions; those correspond to the designs that have $12$ dots of each color. Half of the remaining $2^{24}-\binom{24}{12}$ subsets have at least $13$ elements. Thus, the answer to the main question is

$$\frac12\left(2^{24}-\binom{24}{12}\right)=2^{23}-\frac12\binom{24}{12}=16,777,216-1,352,078=15,425,138$$

logos. The general problem is significantly harder: for this one we can take advantage of the fact that we’re looking at exactly half of an easily computed number. However, for two colors and a majority of white dots it’s not bad. If there are $2n$ dots, the same reasoning leads to the result

$$\frac12\left(2^{2n}-\binom{2n}n\right)=2^{2n-1}-\frac12\binom{2n}n\;.$$

If there are $2n+1$ dots, exactly half of the $2^{2n+1}$, or $2^{2n}$ designs, have a majority of white dots.

Added: Note that I am assuming, as you implicitly did in saying that there are $2^{24}$ unrestricted patterns, that identical patterns in different orientations are counted as different patterns (e.g., that the $24$ patterns with a single red dot count as $24$ patterns, not as one). The problem becomes much more complicated if patterns that can be rotated into one another are considered identical.

Answer 2

To get a general answer to your question, consider the number of possible patterns with exactly $k$ red dots, for $k \le 24$. It is $\binom{24}{k}$, since the problem boils down to "choosing" $k$ out of the 24 positions.

The number of patterns with at least 13 red dots is then

$$\sum_{k=13}^{24} \binom{24}{k}$$

And similarly for other values instead of $24$ and $13$ (but still for just two colors).

But there's an extra detail to consider: Do your circular logos have a fixed orientation? Unless there is a natural "up" side, you need to account for rotational symmetries. You can't just divide the above number by 24, since some patterns are self-symmetric. (E.g., there's only one pattern with 24 red dots, and rotating it doesn't change that).

Answer 3

If rotations of the circle are allowed, you need to apply Pólya's coloring theorem. The relevant group for just rotations of 24 elements is $C_{24}$, whose cycle index is: $$ \zeta_{C_{24}}(x_1, \ldots x_{24}) = \frac{1}{24} \sum_{d \mid 24} \phi(d)x_d^{24 / d} = \frac{1}{24} \left( x_1^{24} + x_2^{12} + 2 x_3^{8} + 2 x_4^{6} + 3 x_6^4 + 4 x_8^3 + 6 x_{12}^2 + 8 x_{24} \right) $$ For 13 red and 11 white ones (use $r$ and $w$ for them) you want the coefficient of $r^{13} w^{11}$ in $\zeta_{C_{24}}(r + w, r^2 + w^2, \ldots, r^{24} + z^{24})$. The only term that can provide exponents 13 and 11 is the first one: $$ [r^{13} w^{11}] \zeta_{C_{24}}(r + w, r^2 + w^2, \ldots, r^{24} + z^{24}) = [r^{13} w^{11}] \frac{1}{24} (r + w)^{24} = \frac{1}{24} \binom{24}{13} $$ Flipping over is left as an excercise ;-)

(I'm sure that as soon as I post this, somebody will post a simple reason why this is so by considering that 24 is even, and 13 and 11 odd...).

Answer 4

Another try: Consider the 11 positions of the white dots around the circle. There is no possibility of arranging them so that a rotation repeats the pattern, because 11 is a prime (any shuffling of dots must exchange pairs, or rotate groups of 3, or...). So for each linear order of the dots (there are $\binom{24}{13}$ of those) can be rotated into 24 positions, giving again $\frac{1}{24} \binom{24}{13}$. There are two ways of flipping the logo over: Through two dots, or through the lines connecting adyacent dots. But the last one will have an odd number of white dots at one side and an even one at the other, can't give the same. By exchanging left and right through vertically oposite dots, by the same reasoning one has to be red and the other white. This leaves 6 red and 5 white dots to be arranged the same way at each side, and with the selection of red or white dot at the top this then gives $2 \binom{11}{6}$ configurations that can't be distinguised by flipping over. So, allowing flipover the total number of logos is (half of the original have to be subtracted as they result from flipping over, but the ones which are the same flipped over have to be added back in): $$ \frac{1}{2} \cdot \cfrac{1}{24} \cdot \binom{24}{13} + 2 \binom{11}{6} $$