0

Let's say I have a lattice like that:

enter image description here

It's a lattice 10x10 (or N*N). So 100 little squares compose the lattice.

Now I have to put 6 green squares (or n green squares) on the lattice.

How do I calculate the number of possible permutations of the 6 green squares on the lattice ?

Rififi
  • 165
  • Are you permuting those particular green squares, or just asking how many ways you can permute those 6 (or more generally, $n$ given) squares in a $10 \times 10$ lattice? If yes, do the permutations have to preserve anything (like adjacent squares getting mapped to adjacent squares, etc)? Or are you asking how many ways there are to place $n$ squares in a $10 \times 10$ lattice? Or something else entirely? – pjs36 Apr 07 '15 at 21:00
  • I think it's "how many ways there are to place n squares in a 10×10 lattice? ". Consider it like this: a square can be white or green. How many lattice are there with 6 green squares ?. The permutations don't have to respect anything. I just want to know the number of possible solutions. – Rififi Apr 07 '15 at 21:09
  • So the shape $10\times 10$ does actually not matter? It could as well be $5\times 20$ or $1\times 100$? – user 59363 Apr 07 '15 at 21:24

2 Answers2

0

You have $100$ squares, and your job is to figure out how many ways there are to mark $n$ of them. So, out of $100$ squares, you need to choose $n$ that get marked...

pjs36
  • 17,979
0

This is an answer to a two year old question, but I wanted to answer it anyway.

If you could fill none to all squares on that lattice (that is any combination (any possible binary number)) the answer would have been some number consisting of 31 digits (in decimal), which would have been a very large number.

Since you are using only two colors (green and white), in this case the colors does not matter. i.e. if you only have one color and another background color: you can define (the color) green as '1', and white (background color) as '0'. In computer terminology we know these are called bits (binary numbers). So by this there is another solution to this problem involving some bruteforcing. I know more programming than math, so bear with me because I can't answer with a very detailed mathematical vocabulary. The answer is very simple if you can bruteforce and check if the hamming weight is equal to n. The only problem using this technique would be the speed of the computer-registers that compute this. We are talking about 100 bits here, and I dont think mainstream cpus have 128-bit registers yet and not even an popcount-instruction to compute the hamming weight. However, the algorithm should work despite all of this.

'Hamming weights' aka 'population count' works this way: It counts the number of on-bits in a binary number representation (Was invented (or atleast named after) by a guy called Richard Hamming). You could make a function that bruteforces all the possible combinations of hamming weight = n (where n is the number of filled (green) squares / or on-bits in computer terminology).

It boils down to this: You have a natural number z that always add +1 when the hamming weight equals n, and so the result (all the sums) of z equals the number of possible permutations.

Pseudocode

Initial condition:

n=6  (number of filled squares).
z=0  (some natural number or integer).

Iterative loop:

For i = 0 to (2^100)-1:
 If (HammingWeight(i) == n) z = z + 1
Next i

z equals the solution after the loop has finished.