Exercise 2 Stanley combinatorics volume 1: Bijective proof of a sum equality

Question

Let $S$ be a finite set of objects and let $\mathscr{P}$ be a finite set of properties that the elements of $S$ may or may not satisfy. Given a subset of properties $X$, I define $f_=(X)$ as the number of elements of $S$ that satisfy exactly the properties $X$ and $f_\geq (X)$ as the number of element of$S$ satisfying at least the properties $X$. I have to give a bijective proof of the following equality

$$\sum_{X\subseteq \mathscr{P}} f_=(X)x^{\# X}= \sum_{X\subseteq \mathscr{P}} f_\geq (X)(x-1)^{\# X} $$

but I’m a bit lost. I’m trying to interpret the monomial $x^{\# X}$ as the number of functions $X\to [x]$. Is this the right idea?

Answer 1

I will give a bijection which proves this equality in the case where $x$ is a positve integer.

The LHS enumerates ordered triples $(X, s, f)$, such that…

• $X$ is a subset of properties

• $s\in S$ is an element which has all of the properties in $X$, and no others.

• $f:X\to \{0,1,\dots,x-1\}$ is a function.

On the other hand, the RHS enumerates enumerates ordered triples $(X',s',f')$ such that…

• $X'$ is a subset of properties.

• $s'\in S$ is an element which has all of the properties in $X' $. (Possibly, $s'$ has some properties which are not in $X'$).

• $f':X'\to \{1,\dots,x-1\}$ is a function.

Given $(X,s,f)$ described by the LHS, here is how you bijectively produce $(X',s',f')$ for the RHS.

Let $s'=s$.
Let $X'=\{p\in X\mid f(p)\neq 0\}$.
Let $f'$ be the restriction of $f$ to $X'$ .

Conversely, here is the inverse mapping which, given $(X',s',f')$, produces $(X,s,f)$.

Let $s=s'$.
Let $X$ be the set of properties satisfied by $s$. Necessarily, $X$ is a superset of $X'$.
Define $f:X\to \{0,1,\dots,x-1\}$ as follows. If $p\in X'$, then $f(p)=f'(p)$. Otherwise, $f(p)=0$.

You just need to prove that these two mappings are valid (in the sense that the outputs have the required properties), and that they are inverses to each other.