Question

I've only played with this a little for the past day or so, and haven't thought about it too hard, so it might be obvious. Obviously it's not fair to ask for a "combinatorial proof" of an inequality involving real numbers, so we'll ask that the vectors be in $\mathbb{N}^n$. More concretely:

Given n boxes subdivided into a "right half" and a "left half" with $a_i$ objects in the right half of box $i$, and $b_i$ in the left half of box i, is there a natural injective function from

Two pairs (ordered, with replacement) of objects, with each pair containing one object from the left half and one object from the right half of a fixed box

to

A pair (ordered, with replacement) from the right half of some box, and a pair (O,WR) from the left half of some (possibly different) box?

(Sorry if this is a double; my wireless is being strange.)

Answer 1

Honestly, not really, there is no interesting combinatorial proof. Think of the most trivial case $a^2 + b^2 \ge 2 a b$. How do you prove that combinatorially? Well, arrange the terms into $(a+b)^2$ as in proving Pythagoras theorem and cut both squares by a diagonal. Now observe that reflection of white triangles will cover the blue rectangles. This proof can be stated in a purely combinatorial language, but why bother - it's a standard "book proof" you can find everywhere. Similarly, you can take: $$\sum_{i=1}^n \sum_{j=1}^n \left(a_i b_j + a_j b_i \right)^2$$ expand all the terms and get a similar flavor "combinatorial proof", more or less the same what you can find in standard books. But again why bother?

P.S. If you want to see the real power of bijective proofs, you can check out my survey of partition bijections. Sorry for the self-promotion, but there is no other such large compendium (although Stanley's "Enumerative Combinatorics" does mention many beautiful bijections, many of which hidden in the solutions to exercises).