关于(0,1)矩阵

hbghlyj

我在oeis网站上看到如下的
a(n) = 2^n * Sum_{i = 0...C(n, 2)} C(C(n, 2), i)*3^i.  The summation conditions on i, 0 <= i <= C(n, 2), the number of 1's above the main diagonal in the matrix representations of the relations on {1, 2, ..., n}. - Geoffrey Critzer, Feb 18 2011
也就是$$2^{n^2-n}=\sum_{i = 0}^{\binom n 2}\binom{\binom n2}i\cdot 3^i$$证明是显然的：$$2^{n^2-n}=(3+1)^{\binom n2}=\sum_{i = 0}^{\binom n 2}\binom{\binom n2}i\cdot 3^i$$但是，如何理解Geoffrey Critzer所述的“去掉主对角线的$n\times n$的(0,1)矩阵,可以看作{1, 2, ..., n}上的二元关系,这里的i是主对角线上方的1的个数”(标红色字不理解 )

tommywong

應該係講緊主對角線上方的1的個數$i$可以係$0,1,2,\dots,\binom{n}{2}$
例如$4\times 4$的(0,1)矩陣
$\begin{pmatrix}
1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}$
主對角線上方有$\binom{4}{2}=6$個位

至於$\displaystyle \sum_{i=0}^{\binom{n}{2}}\binom{\binom{n}{2}}{i}3^i$計緊乜我就唔知喇