TAOCP 7.1.1 Exercise 121
Let P=[0,m]\times[0,n] with product order, and define the involution
Exercise 121. ▶ [M23] The function $f(x_1, x_2, y_1, y_2)$ is partially symmetric, since it is symmetric in ${x_1, x_2}$ and in ${y_1, y_2, y_3}$, but not in all five variables ${x_1, x_2, y_1, y_2, y_3}$.
a) Exactly how many Boolean functions $f(x_1, \ldots, x_m)$ and $g(y_1, \ldots, y_n)$ are symmetric in $[x_1, \ldots, x_m]$ and $[y_1, \ldots, y_n]$? b) How many of those functions are monotone? c) How many of those functions are self-dual? d) How many of those functions are monotone and self-dual?
Verified: yes
Solve time: 4m03s
Let
$$ P=[0,m]\times[0,n] $$
with product order, and define the involution
$$ \omega(i,j)=(m-i,n-j). $$
For a Boolean function $f$, let
$$ U={(i,j)\in P : f(i,j)=1}. $$
Monotonicity means $U$ is an up-set of $P$.
Self-duality means
$$ (i,j)\in U \iff \omega(i,j)\notin U, $$
so $U\cap \omega(U)=\varnothing$ and $U\cup \omega(U)=P$.
(a)–(c)
These parts are correct as stated in the proposed solution:
- (a) Every symmetric function corresponds to an arbitrary assignment on $(m+1)(n+1)$ pairs $(i,j)$, hence
$$ 2^{(m+1)(n+1)}. $$
- (b) Monotone symmetric functions correspond to order ideals in the grid poset $P$, giving
$$ \binom{m+n+2}{m+1}. $$
- (c) Self-dual (not necessarily monotone) functions correspond to choices on orbits of $\omega$. A fixed point exists iff $m,n$ are both even, in which case no solution exists. Otherwise,
$$ 2^{(m+1)(n+1)/2}. $$
(d) Monotone and self-dual
The previous solution attempted a quotient-poset reduction. That is unnecessary and incorrect. The correct argument is structural and rules out all nontrivial cases.
Step 1: Translate conditions
Let $U\subseteq P$ satisfy:
- $U$ is an up-set (monotonicity),
- $U = P \setminus \omega(U)$ (self-duality).
Equivalently:
- each orbit ${x,\omega(x)}$ contains exactly one element of $U$.
Step 2: Use bottom and top elements
Let
$$ \mathbf{0}=(0,0), \quad \mathbf{1}=(m,n). $$
These form an orbit since $\omega(\mathbf{0})=\mathbf{1}$.
So exactly one of $\mathbf{0},\mathbf{1}$ lies in $U$.
Case 1: $\mathbf{1}\in U$
Since $U$ is an up-set and $\mathbf{1}$ is the maximum element, this implies
$$ U = P. $$
But then self-duality gives $U = P \setminus \omega(U) = \varnothing$, contradiction.
So this case is impossible.
Case 2: $\mathbf{1}\notin U$
Then by the orbit condition,
$$ \mathbf{0}\in U. $$
But $U$ is an up-set and $\mathbf{0}$ is the minimum element of $P$, so every element satisfies $(0,0)\le (i,j)$, hence
$$ U = P. $$
This contradicts $\mathbf{1}\notin U$.
Step 3: Conclusion
Both cases are impossible. Therefore no such function exists.
$$ \boxed{0} $$
for all $m,n\ge 0$.
Final answers
$$ \text{(a)}\quad 2^{(m+1)(n+1)} $$
$$ \text{(b)}\quad \binom{m+n+2}{m+1} $$
$$ \text{(c)}\quad \begin{cases} 2^{(m+1)(n+1)/2}, & \text{if } m \text{ or } n \text{ is odd},\ 0, & \text{if } m,n \text{ are even} \end{cases} $$
$$ \text{(d)}\quad \boxed{0 \text{ for all } m,n} $$
This completes the corrected solution.