For a natural number $n{},$ determine the number of ordered pairs $(S,T)$ of subsets of $\{1,2,\ldots,n\}$ for which $s>|T|$ for any element $s\in S$ and $t>|S|$ for any element $t\in T.$
Problem
Source: Russian TST 2014, Day 10 P4 (Groups A & B)
Tags: combinatorics, counting
RM1729
08.01.2024 21:53
Solved with Pranav1056 The idea is that if $S$ has size $a$ and $T$ has size $b$ there are ${{n-b}\choose a} \cdot {{n-a}\choose b}$ ways Let $a+ b = s$, so we can rewrite the sum as \[\sum_{s=0}^{n} \sum_{a=0}^{s} \binom{n-a}{s-a}\binom{n-s+a}{a} = \sum_{s=0}^{n} \sum_{a=0}^{s} \binom{n-a}{n-s}\binom{n-s+a}{n-s}\]Note that\[\sum_{a=0}^{s} \binom{n-a}{n-s}\binom{n-s+a}{n-s} = \sum_{a=s-n}^{n}\binom{n-a}{n-s}\binom{n-s+a}{n-s} \]Using the fact that $\binom{i}{j} = 0, \forall i < j$. Now, we can think of this summation combinatorially. It is of the form $$\sum_{k = -Y}^{X} \binom{X-k}{C} \binom{Y+k}{C}$$Think above as follows - suppose we have $X+Y+1$ objects labelled from $-Y$ onwards till $X$, and we have to select $2C+1$ objects from it. We select object $k$ from it, and then we select $C$ objects from left of it which are $Y+k$ objects, and remaining $C$ from right of it which are $X-a$ objects. Hence, we can write :- $$\sum_{k = -Y}^{X} \binom{X-k}{C} \binom{Y+k}{C} = \binom{X + Y + 1}{2C + 1}$$Now, comparing it with our original summation, we have $Y = n-s, x = n, C = n-s$ \[\implies \sum_{a = s-n}^{n} \binom{n-a}{n-s}\binom{n-s+a}{n-s} = \binom{2n-s + 1}{2n-2s + 1} = \binom{2n+1 -s}{s}\]Therefore, the answer is\[\sum_{s=0}^{n} \binom{2n+1-s}{s} = \boxed{F_{2n+2}}\]Where $F_n$ is the $n$th fibonacci number.
starchan
08.01.2024 22:13
hopefully no messup
Let $s, t$ denote the sizes of sets $S ,T$. The problem reduces to finding the following sum: \[\sum_{0 \leq s, t \leq n} \binom{n-s}{t} \binom{n-t}{s}\]
Switching over to the variable $n-x-y$ we obtain the equivalent sum \[\sum \limits_{t = 0}^{n} \sum \limits_{a+b= n+t} \binom{a}{t} \binom{b}{t}\]Let the above sum denote $f(n)$. Use Snake Oil (or whatever you want to call it really) we get \[\sum \limits_{n \geq 0} f(n)x^n = \sum \limits_{t =0}^{\infty} \sum \limits_{a =0}^{\infty} \sum \limits_{b =0}^{\infty} \binom{a}{t} \binom{b}{t} x^{a+b-t}\]The above simplifies to: \[\sum \limits_{t =0}^{\infty} x^{-t} \left(\sum \limits_{a =0}^{\infty} \binom{a}{t} x^{a} \right)^2\]Using the closed expression for the term being squared, this becomes: \[\sum \limits_{t = 0}^{\infty} \frac{x^t}{(1-x)^{2t+2}}\]This is a GP with ratio $\frac{x}{(1-x)^2}$. Thus it evaluates to \[\frac{1}{(1-x)^2} \cdot \frac{1}{1- \frac{x}{(1-x)^2}}\]or \[\frac{1}{(1-x)^2-x} = \frac{1}{1-3x+x^2}\]Let $u, v = \frac{3 \pm \sqrt{5}}{2}$ be the roots of the previous equation so that we have \[\sum \limits_{n \geq 0} f(n)x^n = \frac{1}{(x-a)(x-b)} \]It's well known that the above has the expansion: \[\sum \limits_{n \geq 0} \frac{a^{n+1}-b^{n+1}}{a^{n+1}b^{n+1}(a-b)} x^n\]Since $ab = 1$, the above simplifies and yields that \[f(n) = \frac{a^{n+1}-b^{n+1}}{a-b} = \frac{1}{\sqrt{5}} \cdot \left(\left(\frac{3+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{5}}{2}\right)^{n+1}\right)\]Note that $\frac{3 \pm \sqrt{5}}{2} = \left(\frac{1 \pm \sqrt{5}}{2}\right)^2$ and thus the above expression is actually the $2n+2$th Fibonacci number.
Therefore, the number of such ordered pairs of subsets is exactly $F_{2n+2}$. $\square$
IAmTheHazard
08.01.2024 23:48
Putnam 1990/A6 It’s a shame that so many Russia TST problems seem to be straight out of old contests (not just this year - it’s a pattern I’ve noticed for a while), especially since (original) Russian problems are generally quite high-quality.