calculating possible combinations with linked sets

Question

i have an object that has 20 elements. each of those 20 elements can be colored with a palette of 5 different colors. but those 5 different colors can be chosen from 31 different colors.

how can i calculate all the different combinations possible?

Answer 1

Over the history of combinatorics and over the course of one's education in the subject, there are a number of particularly useful results that deserve names and deserve to be recognized and deserve their own notation.

You should recognize "$n!$" (read aloud as "n factorial") to be shorthand for $n\cdot (n-1)\cdot (n-2)\cdots 3\cdot 2\cdot 1$ and is the number of ways of arranging $n$ distinct objects in a line. (More rigorously, it represents the number of bijective functions from a set with $n$ elements to itself).

You should further recognize $\binom{n}{r}$ (read aloud as "n choose r") to be shorthand for $\frac{n!}{r!(n-r)!}$ and is the number of ways to select $r$ objects from $n$ distinct objects where order doesn't matter. (More rigorously, it represents the number of $r$-element subsets of an $n$-element set).

There are many several dozens more such symbols and shorthand notations for functions which answer other questions which often do not appear in a first course in combinatorics, but they are still incredibly useful and once you've seen them in use the first time are worth trying to remember for future use. One such would be the Stirling number of the second kind (not to be confused with stirling numbers of the first kind which counts something else).

Stirling numbers of the second kind, denoted $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$ which is shorthand for $\frac{1}{k!}\sum\limits_{j=1}^k(-1)^{k-j}\binom{n}{j}j^n$, happens to be a particularly useful function. It counts the number of ways that a set of $n$ objects can be partitioned into $k$ non-empty unordered subsets. If we want for the sets to be ordered as well, we can just multiply by $k!$ to assign an order to them.

For example $\left\{\begin{smallmatrix}4\\2\end{smallmatrix}\right\} = 7$ since there are seven ways to partition $\{a,b,c,d\}$ into two nonempty subsets. Namely $\{\{a\},\{b,c,d\}\},\{\{b\},\{a,c,d\}\},\{\{c\},\{a,b,d\}\},\{\{d\},\{a,b,c\}\}$

$,\{\{a,b\},\{c,d\}\},\{\{a,c\},\{b,d\}\},\{\{a,d\},\{b,c\}\}$

(note, here $\{\{a,b\},\{c,d\}\}$ is considered the same partition as $\{\{c,d\},\{b,a\}\}$)

---

In the context of your problem, I would imagine that you are trying to count something like "how many sprites using at most five colors exist" where a sprite occupies $20$ pixels and there are $31$ colors available.

To do this, we first break into cases based on the number of colors actually appearing. For example, let us look at the case that a sprite uses exactly five colors.

We first pick what five colors those happen to be in $\binom{31}{5}$ ways. (remember binomial coefficients count the number of subsets of a particular size of a larger set). For example, we may have happened to pick the colors red, blue, green, white, black.

We then decide how to partition the twenty pixels into five non-empty subsets (we require them to be nonempty because otherwise the corresponding color will have not appeared and will not have mattered if it were replaced by another color. If we do not require them to be nonempty we will have overcounted). This step can be done in $\left\{\begin{smallmatrix}20\\5\end{smallmatrix}\right\}$ ways, remembering that this is exactly the scenario that Stirling numbers of the second kind are useful for counting.

We then decide which part in the partition receives which color, and this can be accomplished in $5!$ ways.

Multiplying all of these together as per the rule of product gives us $\binom{31}{5}\left\{\begin{smallmatrix}20\\5\end{smallmatrix}\right\}5!$ ways in which we can color a sprite of 20 pixels using exactly 5 colors from 31 colors available.

Adding this to the amount of ways in which you can color such a sprite with exactly one color, exactly two colors, etc... will give you the final answer.