Let $a, \ b \in \mathbb{Z_{+}}$. Denote $f(a, b)$ the number sequences $s_1, \ s_2, \ ..., \ s_a$, $s_i \in \mathbb{Z}$ such that $|s_1|+|s_2|+...+|s_a| \le b$. Show that $f(a, b)=f(b, a)$.
Problem
Source: Polish Mathematical Olympiad 2016 P3- Final Round
Tags: combinatorics, counting
sabbasi
08.04.2016 23:29
For any sequence of integers $s_1,...,s_a$ satisfying $|s_1|+|s_2|+...+|s_a|\le b$ we construct the sequence of integers $t_1,...,t_b$ as follows. Let $p_i$ be the $i$-th partial sum $|s_1|+...+|s_i|$ for all $1\le i\le a$. First, we set $|t_j|$ to be the number of partial sums equal to $j$ for all $1\le j\le b$. Immediately, this implies $|t_1|+...+|t_b| \le a$. Furthermore, using the sequence $|t_1|,...,|t_b|$, we can recover some aspects of the original sequence. We know the number of leading zeroes in the sequence $s_1,...,s_a$ is $a - |t_1|-...-|t_b|$. Hence we know all the partial sums $p_i$. Furthermore, consider some $1\le j \le n$ such that $|t_j|>0$. Let $n_j$ be minimal such that $|s_1|+...+|s_{n_j}|=j$. Then we know that $|s_{n_j}|>0$, and that there are $|t_j|-1$ zeroes following $s_{n_j}$, since the partial sum stays constant $|t_j|$ times. Therefore, the only thing left to "encode" is the sign of $s_{n_j}$, which we do with the sign of $t_j$. So this process gives a bijection between the sequences in $f(a,b)$ and $f(b,a)$ since given $t_1,...,t_b$ we can recover $s_1,...,s_a$. The explanation is probably a bit hard to follow I can explain more upon request. Here's an example to make it clearer: Let $a=4, b=3$ Suppose $s_1 = 0, s_2 = -2, s_3 = 0, s_4 = -1$. Hence $|s_1| = 0$, $|s_1|+|s_2| = 2$, $|s_1|+|s_2|+|s_3| = 2$ and $|s_1|+|s_2|+|s_3|+|s_4|=3$. So we set $t_1 = 0, t_2 = -2, t_3 = -1$. Then if we're given $t_1 = 0, t_2 = -2, t_3=-1$, we know the sequence of partial sums is $0,2,2,3$, and so we know the sequence $|s_1|,|s_2|,|s_3|,|s_4|$ is $0,2,0,1$, and based on the signs we know the original sequence is $0,-2,0,-1$.
shinichiman
09.04.2016 00:11
It was an old problem.
Note a well-known result: The number of lists $(b_1,b_2, \cdots , b_{m+1})$ of positive integers such that $b_1+b_2+ \cdots + b_{m+1}=n+1$ is $\tbinom{n}{m}$.
If there are $a-i \; (0 \le i \le a)$ number $0$ among $s_i \; (1 \le i \le a)$ then we have $|s_{c_1}|+ \cdots +|s_{c_{i}}| \le b$. Using the result above we find the number of lists $(|s_{c_1}|, \cdots , |s_{c_i}|)$ of positive integers is $$\binom{b-1}{i-1}+ \binom{b-2}{i-1}+ \cdots+ \binom{i-1}{i-1}= \binom{b}{i}.$$There are $2^{i}$ ways to pick the sign ($+$ or $-$) for $s_{c_1}, \cdots, s_{c_i}$ and $\tbinom{a}{a-i}=\tbinom{a}{i}$ ways to pick $a-i$ numbers $0$ among $s_1,s_2, \cdots , s_a$. Hence, there are $\binom bi \binom ai 2^i$ number of lists of $s_1,s_2, \cdots , s_a$ such that there are exactly $a-i$ numbers $0$ among them. Thus,
$$f(a,b)=\sum_{k=0}^a \binom bk \binom ak 2^k= \sum_{k=0}^{\infty} \binom bk \binom ak 2^k= \sum_{k=0}^{b} \binom ak \binom bk2^k=f(b,a).$$We are done.
Pinionrzek
09.04.2016 00:42
I managed to come up with another solution.
By induction it is sufficient to show: $f(a, b)=f(a, b-1)+f(a-1, b-1)+f(a-1, b)$. It implies that we need to prove that number of sequences which sum of modules of terms is excatly $b$ is $f(a-1, b-1)+f(a-1, b)$. Divide the set $S$ of all sequnces summing to $b$ into $S_1, \ S_2$. Sequences in $S_1$ satisfy the following condition: for first $a-1$ terms the sum of their modules is less than $b$. Other sequences belong to $S_2$. Notice that for each sequence from $S_1$ we can choose unambiguously wtr sign the last term, so we need to count them twice. Sequences from $S_2$ should be counted only one time, as the last term must be $0$. It is apparent that $f(a-1, b-1)+f(a-1, b)$ satisfies these conditions.
va2010
09.04.2016 00:51
This is 2005 Putnam B4 .
MarkBcc168
19.09.2020 17:21
Very easy if you know generating function. See that $f(a,b)$ is the coefficient of $x^ay^b$ in $$F(x,y)=\sum_{a=0}^{\infty} x^a(1+y+y^2+\hdots)(1+2y+2y^2+2y^3+\hdots)^a.$$We want to show that this is symmetric in $x,y$, but this is easy: \begin{align*} F(x,y) &= \sum_{a=0}^\infty x^a\cdot \frac 1{1-y} \cdot \left(\frac{1}{1-y}-1\right)^a \\ &= \sum_{a=0}^\infty x^a\cdot \frac 1{1-y} \cdot \left(\frac{1+y}{1-y}\right)^a \\ &= \frac{1}{1-y}\sum_{a=0}^\infty \left(\frac{x(1+y)}{1-y}\right)^a \\ &= \frac{1}{1-y} \cdot \frac{1}{1- \left(\frac{x+xy}{1-y}\right)} \\ &= \frac{1}{1-x-y-xy}. \end{align*}
EthanWYX2009
04.09.2024 15:55
Define $f(0,b)=f(a,0)=1.$ \begin{align*}F(X,Y):&=\sum_{m,n=0}^{+\infty}f(m,n)X^mY^n=\sum_{m,n=0}^{+\infty}\sum_{|x_1|+|x_2|+...+|x_n| \le m}X^mY^n\\&=\sum_{n=0}^{+\infty}Y^n\sum_{x_1,x_2,\ldots ,x_n}\frac{X^{|x_1|+|x_2|+...+|x_n|}}{1-X}\\&=\sum_{n=0}^{+\infty}\frac{Y^n}{1-X}\left(\sum_{x\in\mathbb Z}x^{|k|}\right)^n=\frac{1}{1-X-Y-XY}\\&=F(Y,X).\Box\end{align*}