can you tell how did you arrive at the formula?
Motivation : The problem can be thought of as dividing the rectangles into “regions”(a region consists of cell(s) sharing having the same number and sharing a common side/boundary). We want to find the expected number of regions , where the cells are filled with numbers uniformly and randomly from [1,k].
Initially, I got a combinatorics formula just for the case m=1. This was based on multinomial theorem. I tried a lot for a similar formula for the case m=2, but couldn’t find a similar formula as there were a lot of cases in the merging of two 1* N rectangles(such as overlapping regions of the two 1* N rectangles) etc which didn’t seem easy to handle.
I started taking many small examples(small values of n,k) for the case m=1. I noticed that the combinatorics formula was giving really large values(of p and q), but always simplified down to a simple small fraction(p/q). I noticed a pattern in the values of p/q to arise on comparing the answers for those small examples(such as keeping n constant, incrementing k by 1 and vice versa), so I this provided some clue to look for a simpler formula.
Logic: Since the numbers are filled randomly, By linearity of expectation, the expected number of regions over the whole rectangle = summation of expectation of increase in number of regions at each step of filling numbers in the cells(we can assume without loss of generality, that it is filled in sequence/order).
For the case m=1, for the first cell, the number of regions will always increase by 1, for any number chosen. The expected increase in number of regions for the first cell is \frac{1*k}{k}
For all the remaining n-1 cells, the number of regions would increase by 1 only if the number filled at that cell is not equal to the number filled at the previous cell. If they are the same, there is no increase in the number of regions. So the expected increase in regions for the remaining cells is \frac{1*(n-1)*(k-1)}{k}.
So the expected number of regions for m=1 is \frac{1*k}{k} + \frac{1*(n-1)*(k-1)}{k}.
the case m=2 is similar to the case of m=1, but here we must take into consideration the filling of both the rows for a given column as well as consider the numbers/conditions of both the cells of the previous column.
This is a bit long so I’ll just write down the formula:
Base case: \frac{2*k*(k-1)+1*k}{k^2}
General case: (n-1)*[2*\left(\frac{k-1}{k}*\frac{k-2}{k}*\frac{k-2}{k}+\frac{k-1}{k}*\frac{1}{k}*\frac{k-1}{k}+\frac{1}{k}*\frac{k-1}{k}*\frac{k-2}{k} \right) + 1*(2*\frac{k-1}{k}*\frac{k-2}{k}*\frac{1}{k}+2*\frac{1}{k}*\frac{k-1}{k}*\frac{1}{k}+\frac{k-1}{k}*\frac{k-2}{k}*\frac{1}{k}+\frac{1}{k}*\frac{k-1}{k}*\frac{1}{k})]
Adding the base and general case and simplifying gives the required formula.
1 Like