# A Problem of Combinatorics

In how many ways can three distinct numbers be chosen from the set {1,2,3,4....2n} such that the numbers are in increasing arithmetic progression?

-
What have you tried? –  rah4927 Apr 20 '14 at 11:38
The common difference for the selected numbers can lie between 1 to 2n/3. so it seems I need to work for every common difference from 1 to 2n/3. Is this fine? –  Kush Shukla Apr 20 '14 at 11:46
How many extra APs do you get when you add $2n+1$ to the set, and now many more when you then add $2n+2$? –  Mark Bennet Apr 20 '14 at 11:49
@Shukla,remember that combi questions often require you to divide into cases.You could try by dividing the arithmetic progressions according to their first term too.Here,your idea about working with common differences does work,but you still have to sort the APs using the first term.I am sure I saw a similar question a while ago,but cannot find it.Another approach,as mentioned by Mark Bennet,is to try recursion. –  rah4927 Apr 20 '14 at 11:50
@Mark Adding 2n+1 to the set can get me [2n+1/3] A.Ps, maximum 1 more AP. And 2n+2 to the set can get me [2n+2/3] A.Ps, maximum 2 more AP. –  Kush Shukla Apr 20 '14 at 11:56

The number of progressions $\{a_1,a_2,a_3\}$ such that $a_2=k$ is:

• $k-1$ if $2\leq k\leq n$
• $2n-k$ if $n+1\leq k\leq 2n-1$

so the total number is $$S=\sum_{k=2}^n (k-1)+\sum_{k=n+1}^{2n-1} (2n-k)$$

The first sum is $1+2+\ldots+(n-1)=\frac{n^2-n}2$, and the second sum is the same, but in the reverse order. This gives $$S=n^2-n$$

Another solution:

We can count how many AP's with difference $d$ there are. If the first term is $1$, the last is $1+2d$, so there are $2n-(1+2d)+1=2n-2d$ of such AP's. But $d$ can be any integer from $1$ to $n-1$, so $$S=\sum_{d=1}^{n-1}(2n-2d)=\sum_{k=1}^{n-1} 2k=n^2-n$$

-
Thanks that put the things into perspective. –  Kush Shukla Apr 20 '14 at 12:32

Solution: The second term of the AP is determined entirely by the other two terms.But the first term $a$ and third term $a+2d$ have the same parity(adding the even number $2d$ does not change their parity).

If they are both odd,then they can be selected in $\dbinom{n}{2}$ ways.

If they are both even,they can be selected in $\dbinom{n}{2}$ ways.

Adding them up,we get $n(n-1)$.

Credits: Thanks to Mark Bennet for helping me with this solution.

-

This is an extended hint.

If you add $2n+1$ to the set, you get some extra APs, but note that the extra APs you get all include $2n+1$ - for example $[2n-1, 2n, 2n+1]$ is added, with difference $1$ and $[2n-3, 2n-1, 2n+1]$ with difference $2$. $[1, n+1, 2n+1]$ also gets added, with difference $n$.

You can count these, and also the ones you get when you additionally add $2n+2$ to the set.

Also check with small values what gets added to ensure your calculations are right. With a bit of testing you should see what is happening.

-
If I am not wrong,your answer is trying to get a recursive formula,isn't it? –  rah4927 Apr 20 '14 at 12:07
@rah4927 Well, it is trying to indicate an easier way of counting, by seeing what you add by going from $2n$ to $2n+2$ which avoids having to think about fractions. Then you have to work out where you start and add up all the pieces. Actually counting the APs of difference $1$, then of difference $2$ etc also works - you have a sum to add which initially looks different, but turned out to be the same. The final answer is surprisingly simple. Recursion or induction can be used to do the sum. –  Mark Bennet Apr 20 '14 at 12:13
Thanks.Just another brainwave that I got:The second term of the AP is completely dependent on the other two terms.Now,in how many ways can we select two integers from the given set?Then we have to eliminate a few cases.Does this method work? –  rah4927 Apr 20 '14 at 12:18
@Mark On adding an element to the set, the element get into counting of all APs formed. Got it. By inspecting the smaller values of n, I found that the number of APs are n*(n-1) and if we consider the reverse APs also then it should be 2*n*(n-1). Are my observations OK? –  Kush Shukla Apr 20 '14 at 12:28
@rah4927 Since the terms of the $AP$ are $a, a+d, a+2d$ you are OK for the middle number if yout initial numbers were both even or both odd. That's neat, so why not post it as an answer? –  Mark Bennet Apr 20 '14 at 12:31