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.

  • $\begingroup$ What is a multichain? $\endgroup$ – William Elliot May 6 '18 at 7:44
  • $\begingroup$ @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. $\endgroup$ – VHarisop May 6 '18 at 23:11
  • $\begingroup$ There are infinitely many finite multichains in any lattice. $\endgroup$ – William Elliot May 7 '18 at 2:42
  • $\begingroup$ As there are $2^n$ subsets of {1,2,.. n}, $B_k$ has $2^n$ elements. $\endgroup$ – William Elliot May 7 '18 at 2:48
  • $\begingroup$ @WilliamElliot: I added some more info. I am specifically interested in multichains of length $n$. $\endgroup$ – VHarisop May 7 '18 at 3:05

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))$

  • $\begingroup$ Thanks for the answer! Can you clarify a bit on the notation? Is $[k]$ denoting the elements $\{ 1, \dots, k \}$? $\endgroup$ – VHarisop May 8 '18 at 22:18
  • $\begingroup$ Yes sir, $[k]=\{1,2,\cdots , k\}.$ Do you see how to construct the function back? $\endgroup$ – Phicar May 8 '18 at 23:29
  • $\begingroup$ 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. $\endgroup$ – VHarisop May 8 '18 at 23:41
  • $\begingroup$ 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... $\endgroup$ – Phicar May 9 '18 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.