×

# Small doubt in nways editorial

 0 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.. :) asked 27 Mar '16, 10:43 4★pallesai 176●8●30 accept rate: 17%

 0 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. answered 27 Mar '16, 21:29 6★likecs 3.7k●23●80 accept rate: 9%
 0 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, 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. answered 30 Mar '16, 18:46 3★ash_code 475●1●14 accept rate: 15%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×884

question asked: 27 Mar '16, 10:43

question was seen: 556 times

last updated: 30 Mar '16, 18:47