|
|
尝试理解一下AoPS帖子：
This equals the number of pairs of subsets $A, B \subseteq \{1, \dots, n\}$ of the same size $k$, where such a pair is weighted with $(-1)^k$.
We will group most of these pairs with another pair with the opposite weight as follows: given some $(A, B)$, find the largest $s$ not in $A \Delta B$, and pair $(A, B)$ with $(A \Delta \{s\}, B \Delta \{s\})$.
This is a weight-reversing involution on all the pairs $(A, B)$ with $A \Delta B \ne \{1, \dots, n\}$, so to find the desired sum, we can just examine the pairs $(A, B)$ with $A \Delta B = \{1, \dots, n\}$.
If $n$ is odd, then $|A| = |B| = \tfrac{n}{2}$, not possible. Thus the sum is $0$.
If $n$ is even, then $|A| = |B| = \tfrac{n}{2}$. There are $\tbinom{n}{n/2}$ such pairs, and each contributes a weight of $(-1)^n$, for a total of $(-1)^n \tbinom{n}{n/2}$.
To summarize: the answer is
\[ \begin{cases*} 0 & $n$ odd\\ (-1)^n \binom{n}{n/2} & $n$ even. \end{cases*} \]
$A,B$为$U=\{1,2,\dots,n\}$的两个$k$元子集，$A\ne B$，有序对$(A,B)$共有$\binom{\binom{n}{k}}2$个。
这些有序对$(A,B)$可分为3类：
$S_0(n,k)=\#\{(A,B):A\Delta B=U\}$
$S_1(n,k)=\#\{(A,B):A\Delta B\ne U,\max((A\Delta B)^\complement)\in (A\cup B)^\complement\}$
$S_2(n,k)=\#\{(A,B):A\Delta B\ne U,\max((A\Delta B)^\complement)\in A\cap B\}$
那么$S_0(n,k)+S_1(n,k)+S_2(n,k)=\binom{\binom{n}{k}}2$.
显然，$S_0(n,k)=\cases{\binom{n}{k}&if $n=2k$\\0&if $n\ne2k$}$.
问：$S_1(n,k)=?$ |
|
kuing
Post time 2024-3-10 00:30
