# Zeta polynomial of the Boolean Lattice

The task at hand is to compute the zeta polynomial $Z(B_k, n)$ of the Boolean Lattice in $k$ elements, which is the lattice formed by the subsets of $\left\{1, \dots, k\right\}$ under inclusion. The zeta polynomial $Z(B_k, n)$ counts the number of multichains $t_1 \leq \dots \leq t_n = \{1, \dots, k\}$ of length $n$ in the lattice $B_k$. A multichain is simply a chain with element repetitions allowed.

A direct combinatorial approach outlined in Example 3.12.2 from [Enumerative Combinatorics] shows that $Z(B_k, n) = n^k$. Is there a bijective approach towards that result?

P.S: This is homework so please do not post full answers.

• What is a multichain? – William Elliot May 6 '18 at 7:44
• @WilliamElliot A multichain is a chain that is allowed (but not required) to have repeated elements. For example, in $B_3$, $(\emptyset, \{ 1 \}, \{1, 2\})$ is a chain, and $(\emptyset, \{ 1 \}, \{ 1 \}, \{1, 2 \})$ is a multichain. – VHarisop May 6 '18 at 23:11
• There are infinitely many finite multichains in any lattice. – William Elliot May 7 '18 at 2:42
• As there are $2^n$ subsets of {1,2,.. n}, $B_k$ has $2^n$ elements. – William Elliot May 7 '18 at 2:48
• @WilliamElliot: I added some more info. I am specifically interested in multichains of length $n$. – VHarisop May 7 '18 at 3:05

## 1 Answer

This has a problem, take $n = 1,$ then there should be $1^k=1$ but is clear that for a set of length $k$ there are $2^k$ so i think you should add the constraint in the multichain that $t_n = [k].$

Hint: $$[n]^{[k]}=\{f:[k]\longrightarrow [n]\},$$ what if you take $f\in [n]^{[k]}$ and construct $(f^{-1}(1),f^{-1}(1)\cup f^{-1}(2),\cdots f^{-1}(1)\cup \cdots \cup f^{-1}(n))$

• Thanks for the answer! Can you clarify a bit on the notation? Is $[k]$ denoting the elements $\{ 1, \dots, k \}$? – VHarisop May 8 '18 at 22:18
• Yes sir, $[k]=\{1,2,\cdots , k\}.$ Do you see how to construct the function back? – Phicar May 8 '18 at 23:29
• Not yet, but I'm working on it. I think that $f^{-1} = [k]$, since we can choose any of the $k$ elements to form a length $1$ chain. For $f^{-1}(2)$ we should have all pairs, etc. If I'm wrong, I probably haven't understood the bijection you are hinting towards yet. – VHarisop May 8 '18 at 23:41
• Not quite, what if you take a chain $t_1\subseteq t_2\subseteq \cdots \subseteq t_n=[k]$ and you say that $f(t_1)=1,f(t_2\setminus t_1)=2$ etc... – Phicar May 9 '18 at 3:51