Small doubt in nways editorial

combinatorics

#1

I am trying to solve NWAYS problem.I read the Editorial but I am not able to understand how they got the relation

S = 2\sum_{i=1}^{n}\sum_{j=i}^{n} \binom{j-i+k}{k}-n

It would be a great help if any one explain me with this… :slight_smile:


#2

First consider the case when y-coordinate is less than x-coordinate. In that case |j-i| = i-j.

Next, Consider the case when y-coordinate is more than y-coordinate. In that case |j-i| = j-i.

Finally, consider the case when y-coordinate is equal to x-coordinate. In that case |j-i| = 0.

The first 2 cases are equivalent. Hence the factor of 2 comes. For the last case Combination part i.e. nCr (with n = k and r = k) gave 1, which summed upto n. Since 2 was multiplied, so they subtracted ‘n’ (Similar to n = 2n - n).

Hope it is clear.


#3

Here is the expression you are talking about.

S = \sum_{i=1}^n \sum_{j=1}^n {|j-i|+k \choose k}

Now, from the definition of absolute value,

alt text

Now, as the mod function is symmetric, the expression can be modified as shown below.

S = \sum_{i=1}^n \sum_{j=1}^n {|j-i|+k \choose k} \\= 2\sum_{i=1}^n \sum_{j=i+1}^n {j-i+k \choose k} + \sum_{i=1}^n {k \choose k} \\= 2\sum_{i=1}^n \sum_{j=i+1}^n {j-i+k \choose k} + n \\= 2\sum_{i=1}^n \sum_{j=i}^n {j-i+k \choose k} - n

Hope this helps.