1

enter image description here

Given a square of dimensions x by y pixels, how many permutations of colors of pixels are there in the square? Assume that each square is 1 pixel and that this square is 5x5 pixels. How many unique ways can this square of pixels be permuted? Also assume that the specific colors shown here don't matter.

Martin Erlic
  • 141
  • If I have understood the question, it depends greatly on how many colors there are. – ajotatxe Dec 03 '14 at 20:08
  • Are we just rearranging the pixels in the square? That is, are you looking for permutations of 4 red, 3 orange, 3 green (or 4 A, 3 B, 3 C), etc.? Also, do you care about squares being the same by rotation or reflection? – KSmarts Dec 03 '14 at 20:09
  • Yeah, the colors would matter as I'm dealing with a palette of 255 colors but I wanted to start with a simple example.

    How would I go about doing this with a 5000x5000 pixel square with 255 colors?

     – Martin Erlic Dec 03 '14 at 20:11
  • @santafebound The "simple" case is quite trivial because the answer is just $(x\cdot y)!$. The problem with same colors is more interesting. – AlexR Dec 03 '14 at 20:13
  • If the identity of the colors doesn't matter and neither does the symmetry of the board you esssentially have a set partition of your $n^2$ slots, giving for the total of all such partitions a Bell number. – Marko Riedel Dec 03 '14 at 23:00

2 Answers2

2

Assume we have $k$ distinct colors and the number of each color is $n_1,\ldots,n_k$. Then the answer is $$\frac{(xy)!}{n_1!n_2!\cdots n_k!}$$ by the elementary combinatorial formula for enumerating permutations.

Matt Samuel
  • 58,164
  • I do not think so, because there are for example 4 reds that are the same. Better to use some multinomial. – Phicar Dec 03 '14 at 20:11
  • As denoted by the comments, this answer doesn't provide a correct answer to the real-world problem because multiplicities of colours aren't taken into account. – AlexR Dec 03 '14 at 20:11
  • @Phicar the op explicitly specified that the colors are unimportant. – Matt Samuel Dec 03 '14 at 20:12
  • @MattS i think he mean that the color does not matter but the number of equal squares does matter. – Phicar Dec 03 '14 at 20:15
  • @Phicar my edit deals with that now, thanks. – Matt Samuel Dec 03 '14 at 20:16
  • Thanks a bunch! Is there a way to simply the expression n1!n2!⋯nk! where nk is a large number, such as 255? I would like to actually find an explicit value. – Martin Erlic Dec 03 '14 at 20:16
  • @santafebound one way I can think of is to memoize the factorials you have already computed if the goal is faster computation. As a side note, 255! is an extremely huge number. Normal integer arithmetic on the processor can't handle a number that big. – Matt Samuel Dec 03 '14 at 20:18
  • @santafebound Another way is to notice that you can use the distribution function $$d_c(n) = |{i | n_i \ge n}|$$ Then $\prod_{i=1}^k n_k! = \prod_{j=1}^n j^{d_c(j)}$ see my answer for details. – AlexR Dec 03 '14 at 20:20
1

If we want to make the question more interesting by allowing pixels with the same colour (i.e. indistinguishable pixels), the general solution can be obtained as follows:

Let $n_c$ be the number of colours and $c_i, i=1..n_c$ be the multiplicities of the colours. Then the total number of permutations is given by $$P = \frac{(xy)!}{\prod_{i=1}^{n_c} c_i!}$$ This is because there are $c_i!$ ways to rearrange the $i$-coloured pixels without changing the image. To get the denominator in a different form, we can use $$d(n):=|\{i | c_i \ge n\}|$$ wich counts how many colours $i$ have at least $n$ pixels coloured by $i$. Then the denominator is $$\prod_{i=1}^{n_c} c_i! = 1\cdot2\cdot \ldots c_1 \cdot 1 \cdot \ldots c_2 \ldots c_{n_c} = 1\cdot 1\cdot \ldots 1 \cdot 2 \cdot \ldots = \prod_{j=1}^{xy} j^{d(j)}$$ The upper limit of the RHS product can be replaced by $\max_{i} c_i \le xy$

AlexR
  • 24,905
  • Thanks for everything guys! Going to have to work on figuring out how to explicitly interpret that denominator but it seems like what I've learned here is that there really is a very, very large number of combinations of pixels, even when accounting for a distinguishable set of colors. – Martin Erlic Dec 03 '14 at 20:41