I worked for a while trying to solve the general case of N total plates where one side couldn't have m or more plates than the other. I got really close, I think, but I couldn't figure out one little point.
My method was to count the number of ways to fail at this (i.e., get to m more plates on one side than the other), and then subtract this from the total number of ways to put the plates on. Let R and L refer to adding plates on the right and left. We'll focus on failing on the right. I organized my counting by the number of R's required to fail.
Situation 1: We fail if we put m R plates in a row, with no L's:
To count the number of ways this can happen, there's only one way to put on the m R plates, and then we have to count the number of ways to order the remaining N-m plates, in which N/2 of them are Ls.
Number of ways = (N-m) choose (N/2)
Situation 2: m+1 R plates and 1 L plate:
Naively, we could just count how to order these m+2 plates, combined with ordering the remaining plates. But this would overcount the orderings from the previous situation: where we have m R's in a row at the beginning. So here, we want to focus only on orderings of the m+1 R's and 1 L such that the 1 L is placed in the first m slots. This way, we're only counting new orderings that fail. So our ordering will be:
- In the first m slots, 1 L and the rest R's. Number of ways = m
- In the next two slots, the remaining 2 R's (since we're focusing here on m+1 R's).
- In the remaining N-(m+2) slots, the remaining plates, which include (N/2)-1 L's.
Total number of ways = m * [(N-(m+2)) choose (N/2 - 1)]
Situation 3: We do m+2 R's and 2 L's, using the same method. But it gets trickier here. When we count how many ways to place the 2 L's among these first m+4 slots, we need to make sure not to overcount the situations above. We could think of it this way. We need the 2 L's in the first m+2 slots (which will prevent us from overcounting situation 2), AND at least 1 L in the first m slots (to prevent overcounting situation 1). And this is where I got hung up. I figured out a way to count this, but I couldn't turn it into something that was easily expressible for any N and m.
My method was the following. The first L could go in any of the first m slots, and the next L could go anywhere after this, up to m+2. To count this, let x1 be the position of the first L, and x2 be the position of the second L:
sum from x1 = 1 to m of (sum from x2 = x1+1 to m+2 of 1)
Notice that we're just counting 1, over and over, each time placing the L's in different places.
And then, to finish situation 3, we finish like we did with situation 2, by placing the remaining N-(m+4) plates, which include (N/2)-2 L's, counted as [N-(m+4) choose (N/2)-2].
This works for the subsequent situations too, but I can't write it succinctly. For example, situation 4 (with m+3 R's and 3 L's) would have the nested summation of:
sum from x1 = 1 to m of (sum from x2 = x1+1 to m+2 of (sum from x3 = x2+1 to m+4 of 1))
I worked for a while trying to solve the general case of N total plates where one side couldn't have m or more plates than the other. I got really close, I think, but I couldn't figure out one little point.
My method was to count the number of ways to fail at this (i.e., get to m more plates on one side than the other), and then subtract this from the total number of ways to put the plates on. Let R and L refer to adding plates on the right and left. We'll focus on failing on the right. I organized my counting by the number of R's required to fail.
Situation 1: We fail if we put m R plates in a row, with no L's:
To count the number of ways this can happen, there's only one way to put on the m R plates, and then we have to count the number of ways to order the remaining N-m plates, in which N/2 of them are Ls.
Number of ways = (N-m) choose (N/2)
Situation 2: m+1 R plates and 1 L plate:
Naively, we could just count how to order these m+2 plates, combined with ordering the remaining plates. But this would overcount the orderings from the previous situation: where we have m R's in a row at the beginning. So here, we want to focus only on orderings of the m+1 R's and 1 L such that the 1 L is placed in the first m slots. This way, we're only counting new orderings that fail. So our ordering will be:
- In the first m slots, 1 L and the rest R's. Number of ways = m
- In the next two slots, the remaining 2 R's (since we're focusing here on m+1 R's).
- In the remaining N-(m+2) slots, the remaining plates, which include (N/2)-1 L's.
Total number of ways = m * [(N-(m+2)) choose (N/2 - 1)]
Situation 3: We do m+2 R's and 2 L's, using the same method. But it gets trickier here. When we count how many ways to place the 2 L's among these first m+4 slots, we need to make sure not to overcount the situations above. We could think of it this way. We need the 2 L's in the first m+2 slots (which will prevent us from overcounting situation 2), AND at least 1 L in the first m slots (to prevent overcounting situation 1). And this is where I got hung up. I figured out a way to count this, but I couldn't turn it into something that was easily expressible for any N and m.
My method was the following. The first L could go in any of the first m slots, and the next L could go anywhere after this, up to m+2. To count this, let x1 be the position of the first L, and x2 be the position of the second L:
sum from x1 = 1 to m of (sum from x2 = x1+1 to m+2 of 1)
Notice that we're just counting 1, over and over, each time placing the L's in different places.
And then, to finish situation 3, we finish like we did with situation 2, by placing the remaining N-(m+4) plates, which include (N/2)-2 L's, counted as [N-(m+4) choose (N/2)-2].
This works for the subsequent situations too, but I can't write it succinctly. For example, situation 4 (with m+3 R's and 3 L's) would have the nested summation of:
sum from x1 = 1 to m of (sum from x2 = x1+1 to m+2 of (sum from x3 = x2+1 to m+4 of 1))
And then finish with [N-(m+6) choose (N/2)-3].