Partitions of combinations?

85 Views Asked by At

Given a number of trials $n>1$, which conditions must the integers $a,b,c,d\in\mathbb{N}^+$ satisfy in such a way that it holds the following relation?

$$ \binom{a+n-1}{n}+\binom{b+n-1}{n}=\binom{c+n-1}{n}+\binom{d+n-1}{n} $$

The problem is inspired by the fact that, with $n=2$, $a+b>c$, and $$d=\frac{-3+\sqrt{4(a+b-c)+1}}{2},$$ the relation is satisfied by all the Pythagorean triplets $a,b,c$.

EDIT: The problem is clearly interesting only in case of non-trivial solutions (e.g. the relation certainly holds in case $a=b$ and $c=d$). See also Summing combinations with repetition and Triangular Inequality involving binomial coefficients.

Since I am not an expert, I apologize in case this is an obvious problem.

1

There are 1 best solutions below

10
On BEST ANSWER

Let's look at $n=2$. We have $${r\choose2}+{s\choose2}={t\choose2}+{u\choose2}$$ Multiply both sides by 8 and add 2 to get $$(2r-1)^2+(2s-1)^2=(2t-1)^2+(2u-1)^2$$ So we're asking for numbers expressible in more than one way as a sum of two odd squares. For example, $130=11^2+3^2=9^2+7^2$ gives $r=6$, $s=2$, $t=5$, $u=4$.

Now, it's well-known that a number can be expressed as a sum of two squares if and only if primes of the form $4k+3$ appear with even exponents in its factorization. For the squares to be odd, the number must be a multiple of 2, but not of 4. To have more than one expression, there must be more than one prime divisor (counting multiplicity) of the form $4k+1$.

EDIT: There are infinitely many nontrivial solutions to $${r\choose3}+{s\choose3}={t\choose3}+{u\choose3}$$ In fact, there are infinitely many solutions to this equation with $t=u$. The following construction is due to W Sierpinski, Trois nombres tetraedraux en progression arithmetique, Elem Math 18 (1963) 54-55, MR 26 #4957, MR0147441.

Let $a_1=2$, $b_1=1$, $a_{n+1}=73a_n+148b_n$, $b_{n+1}=36a_n+73b_n$, $u_n=3b_n-a_n$, $v_n=4b_n$, $w_n=3b_n+a_n$. Then $${u_n+1\choose3}+{w_n+1\choose3}=2{v_n+1\choose3}$$ When $n=2$, this gives $${142\choose3}+{730\choose3}=2{581\choose3}$$ This gives infinitely many solutions, but by no means all solutions.

I've had a look at John Leech, Some solutions of Diophantine equations, Math Proc Camb Phil Soc 53 (1957) 778-780. For $n=3$, he found 985 solutions in integers smaller than 500. For $n=4$, he found 80 solutions in integers smaller than 500. For $n=5$, he found $${r\choose5}+{s\choose5}={t\choose5}+{u\choose5}$$ for $(r,s,t,u)=(118,117,133,78)$ and $(197,160,209,53)$ (as well as the trivial $(9,9,10,4)$), again going up to $500$. He found nothing nontrivial for $n\ge6$, although I don't know how far up he went for $n$ nor for $r,s,t,u$.

Computers have come along way since 1957. No doubt someone could push the calculations farther (or already has).