Let $\, |U|, \, \sigma(U) \,$ and $\, \pi(U) \,$ denote the number of elements, the sum, and the product, respectively, of a finite set $\, U \,$ of positive integers. (If $\, U \,$ is the empty set, $\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1$.) Let $\, S \,$ be a finite set of positive integers. As usual, let $\, \binom{n}{k} \,$ denote $\, n! \over k! \, (n-k)!$. Prove that \[ \sum_{U \subseteq S} (-1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S) \] for all integers $\, m \geq \sigma(S)$.
Problem
Source: USAMO 1994
Tags: induction, function, algebra unsolved, algebra
calc rulz
28.09.2007 22:43
What does the left side remind you of?
Let $ \{x_1,x_2,...,x_n\}$ denote the elements of $ S$ with $ n = |S|$.
Consider a set $ R$ of $ m$ elements, with $ n$ mutually disjoint subsets $ y_1,y_2,...,y_n$ where $ |y_i| = x_i$.
We wish to count the number of $ n$-element subsets of $ R$ that contain at least one element from all of the $ y_i$'s.
Since the $ y_i$ are mutually disjoint, and there are $ n$ of them, each such subset of $ R$ consists of exactly one element from each $ y_i$, which means the number of such subsets is $ x_1 x_2...x_n = \pi{(S)}$.
As well, we will count the number of such subsets of $ R$ using the Principle of Inclusion-Exclusion. If $ \{x_{i_1},...,x_{i_k}\} = U \subseteq S$, then the number of $ n$-element subsets of $ R$ that do not contain any element of $ y_{i_1},...,y_{i_k}$ is equal to $ \binom{m - \sigma{(U)}}{n}$. By PIE, the number of $ n$-element subsets of $ R$ that contain at least one element from every $ y_i$ is
\[ \sum_{U \subseteq S} ( - 1)^{|U|} \binom{m - \sigma(U)}{n}
\]
and we are done.
Aryth
18.04.2009 08:25
{Lemma 1:} We first prove, by induction:
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{m - \sigma(U) - 1}{|S| - 1} = 0 \forall m$ where variables and functions are described in the problem statement.
For our base case, we set $ |S| = 1$. Then, suppose $ S = \{ a \}$. Then the left hand side is equal to:
$ (-1)^0 \dbinom{m - 1}{1 - 1} + (-1)^1 \dbinom{m - a - 1}{1 - 1}$
$ = 1 - 1 = 0$
This completes the base case.
Now, suppose that for some $ |S| = k$, the statement is true; we wish to show it is true for $ |S| = k+1$ as well.
Notice that the subsets of a $ k+1$-element set can be generated from one of its $ k$-element subsets by taking all subsets of the $ k$-element subset, in addition to the union of each subset of the $ k$-element subset with the other element of the $ k+1$ element subset.
Suppose a set $ S^\prime$ has $ k+1$ elements, including the $ k$ elements of the set $ S$. The other element of $ S^\prime$ is $ y$.
Then we can say:
$ \displaystyle\sum_{U \subseteq S^\prime} (-1)^{|U|} \dbinom{m - \sigma(U) - 1}{|S^\prime| - 1} = \left( \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{m - \sigma(U) - 1}{|S^\prime| - 1} \right) + \left( \displaystyle\sum_{U \subseteq S} (-1)^{|U| + 1} \dbinom{m - \sigma(U) - 1 - y}{|S^\prime| - 1} \right)$
$ = \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \left( \dbinom{m - \sigma(U) - 1}{|S^\prime| - 1} - \dbinom{m - \sigma(U) - 1 - y}{|S^\prime| - 1} \right)$
Now we double-count as follows: Suppose there are $ m - \sigma(U) - 1$ people divided into two groups, one containing $ y$ people and the other containing the rest. Then the quantity
$ \left( \dbinom{m - \sigma(U) - 1}{|S^\prime| - 1} - \dbinom{m - \sigma(U) - 1 - y}{|S^\prime| - 1} \right)$
is the number of ways we can choose $ |S^\prime| - 1$ people such that at least one of the people is from the group containing $ y$ people.
We can alternatively do this by choosing one person from the group containing $ y$ people and then choosing the $ |S^\prime| - 2$ other people from the remaining $ m - \sigma(U) - 2$ people. Thus,
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \left( \dbinom{m - \sigma(U) - 1}{|S^\prime| - 1} - \dbinom{m - \sigma(U) - 1 - y}{|S^\prime| - 1} \right)$
$ = \displaystyle\sum_{U \subseteq S} (-1)^{|U|} y \dbinom{(m-1) - \sigma(U) - 1}{|S^\prime|-2}$
But we can simply plug $ m-1$ into $ m$ in our inductive hypothesis (since the statement is true for all applicable $ m$) and find that
$ y \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{(m-1) - \sigma(U) - 1}{|S^\prime|-2} = 0$
so we have completed the inductive step.
$ \Box$
{Lemma 2:} Now we use the previous result:
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{m - \sigma(U) - 1}{|S| - 1} = 0$
By Pascal's Identity, this can be written as:
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \left( \dbinom{m - \sigma(U)}{|S|} - \dbinom{m - \sigma(U) - 1}{|S|} \right) = 0$
$ \displaystyle\sum_{U \subseteq S} x (-1)^{|U|} \left( \dbinom{m - \sigma(U)}{|S|} - \dbinom{m - \sigma(U) - 1}{|S|} \right) = 0$
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} x \dbinom{m - \sigma(U) - 1}{|S|} = \displaystyle\sum_{U \subseteq S} x (-1)^{|U|} \dbinom{m - \sigma(U)}{|S|}$
We use the same double-counting scenario as above to reach:
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \left( \dbinom{m - \sigma(U)}{|S| + 1} - \dbinom{m - \sigma(U) - x}{|S| + 1} \right) = \displaystyle\sum_{U \subseteq S} x (-1)^{|U|} \dbinom{m - \sigma(U) -1}{|S|}$
$ \Box$
Now we will prove the main statement of the problem, by induction.
For our base case, we set $ |S| = 1$. Then, suppose $ S = \{ a \}$. The left hand side equals:
$ (-1)^0 \dbinom{m}{1} + (-1)^1 \dbinom{m-a}{1} = m - (m-a) = a$
Then the base case holds.
Suppose that for some $ |S| = j$, the statement holds true; we wish to prove it holds true for $ |S| = j+1$. This implies:
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{m - \sigma(U)}{|S|} = \pi(S) \forall m$
We can generate subsets of a set $ S^\prime$ with $ j+1$ elements exactly as we did before. Suppose that $ S^\prime$ has the same elements as $ S$ does, except $ S^\prime$ also includes the element $ x$. Then,
$ \displaystyle\sum_{U \subseteq S^\prime} (-1)^{|U|} \dbinom{m - \sigma(U)}{|S^\prime|} = \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{m - \sigma(U)}{|S^\prime|} + \displaystyle\sum_{U \subseteq S} (-1)^{|U| + 1} \dbinom{m - \sigma(U) - x}{|S^\prime|}$
$ = \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \left( \dbinom{m - \sigma(U)}{|S| + 1} - \dbinom{m - \sigma(U) - x}{|S| + 1} \right)$
But by our second lemma, this is equal to:
$ = \displaystyle\sum_{U \subseteq S} (-1)^{|U|} x \dbinom{m - \sigma(U) - 1}{|S|}$
$ = x \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{(m-1) - \sigma(U)}{|S|}$
By our inductive hypothesis, this is equal to:
$ = x \pi(S)$
Since $ x$ is the element of $ S^\prime$ that is not an element of $ S$, the product of $ x$ with the product of the elements of $ S$ is equal to the product of the elements of $ S^\prime$. Thus,
$ \displaystyle\sum_{U \subseteq S^\prime} (-1)^{|U|} \dbinom{m - \sigma(U)}{|S^\prime|} = \pi(S^\prime)$
given that
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{m - \sigma(U)}{|S|} = \pi(S)$
This concludes our inductive step.
By induction, we have proved:
$ \displaystyle\sum_{U \subseteq S} (-1)^{|U|} \dbinom{m - \sigma(U)}{|S|} = \pi(S)$
as desired.
math154
30.03.2011 00:59
Note that \begin{align*} \sum_{U\subseteq S}(-1)^{|U|}\binom{m-\sigma(U)}{|S|} = [x^0]\sum_{U\subseteq S}(-1)^{|U|}\frac{(1+x)^{m-\sigma(U)}}{x^{|S|}} &= [x^{|S|}] (1+x)^m \sum_{U\subseteq S}(-1)^{|U|}(1+x)^{-\sigma(U)} \\ &= [x^{|S|}] (1+x)^m \sum_{U\subseteq S}\prod_{t\in U}\frac{-1}{(1+x)^t} \\ &= [x^{|S|}] (1+x)^m \prod_{t\in S}\left(1-\frac{1}{(1+x)^t}\right) \\ &= [x^{|S|}] (1+x)^{m-\sigma(S)} \prod_{t\in S}((1+x)^t-1) \\ &= [x^{|S|}] (1+x)^{m-\sigma(S)} \prod_{t\in S}\sum_{k=1}^{t}\binom{t}{k}x^k \\ &= [x^0] (1+x)^{m-\sigma(S)} \prod_{t\in S}\sum_{j=0}^{t-1}\binom{t}{j+1}x^j \\ &= \prod_{t\in S}\binom{t}{1} = \pi(S), \end{align*}as desired.
WolfusA
02.01.2019 19:40
Can somebody explain what's going on above? Especially what is $[x^0]$?
Tintarn
02.01.2019 20:43
WolfusA wrote: Can somebody explain what's going on above? Especially what is $[x^0]$? For a polynomial $P(x)$ and a natural number $n$, the number $[x^n]P(x)$ is the coefficient of $x^n$ in $P(x)$.