[Math] Counting the number of maximal chains in a poset

combinatoricsextremal-combinatorics

Let $X = \{1,2,\ldots ,n\}$. Consider a poset $(X,|)$, where $|$ is the division relation.

Count the maximal chains of $(X,|)$

A maximal chain is such a chain $C\subset X$ that for every $x\in X\setminus C$, $C\cup\{x\}$ is no longer a chain. For instance, $\{1,p\}, p\in\mathbb{P}$ would be a maximal chain if $p<n$ and $2p>n$.

So, one way to generate maximal chains is to consider $\{p\in\mathbb{P} : p\leq n\} =:P$. Fix $p\in P$ and construct chains as follows:

$$C =\{p^k : p^k\leq n,k\in\mathbb{N}\cup\{0\}\}$$
but this won't obviously exhaust the list of possibilities. It may not even generate a maximum chain.

A more accurate way could be constructing them as follows: For instance, for $\{\{1,2,\ldots , 12\},|\}$ we can have $\{1,2,4,8\}$ or $\{1,3,6,12\}$ or $\{1,2,4,12\}$. The common theme is that each chain contains a maximal element.

Posing a sub-problem that would perhaps help:

Given $X = \{1,2,\ldots ,n\}$ and $m\in X$. What is the maximum length (number of elements) of the chain $\{1,\ldots , m\}$ w.r.t relation $|$?

or equivalently, how many divisors of $m$ are there that are pairwise comparable w.r.t $|$?

But now we need to know all the maximal elements of $X$ , what ever a maximal element exactly even is.

Furthermore, a maximal element doesn't necessarily generate a unique maximal chain.

I need help/hints on how to bring this cacophony to a cohesive harmonious conclusion.

Best Answer

The sub-problem of finding the number of maximal chains with maximal element $m$ is simple: Write $m$ in its unique prime factorization $$ m=\prod_{i=1}^t p_i^{\nu_i} $$ Then a maximal chain consists of adding prime factors one by one. This can be done in exactly $$ \frac{(\nu_1+...+\nu_t)!}{\nu_1!\cdots\nu_t!} $$ ways, since we have shuffle all $\nu_1+...+\nu_t$ prime factors, but no one will notice if we shuffle the $\nu_i$ copies of $p_i$. For $m=12=2^2\cdot 3^1$ we have $$ \frac{(2+1)!}{2!1!}=3 $$ maximal chains for instance, and for $m=2^2\cdot3^3\cdot 5^1=540$ we must have $$ \frac{(2+3+1)!}{2!3!1!}=60 $$ maximal chains.

Here is a suggestion for writing a program that generates $C_n$, the number of maximal chains in $\{1,2,...,n\}$:

  • Let $\mathbb P$ denote the set of primes.
  • Let $k(n,p)$ denote the multiplicity of the prime factor $p\in\mathbb P$ in the prime factorization of $n$, ie. $p^{k(n,p)}$ divides $n$.
  • Let $p_{\min}$ denote the least prime factor of $n$.
  • Let $k_n$ denote the sum of multiplicities of all prime factors of $n$.
  • Finally use the recurrence relations $$C_n=C_{n-1}-C_{n/2}+C_{n/2}\cdot\frac{k_n}{k(n,2)},\quad\text{ when }p_{\min}=2$$ and $$C_n=C_{n-1}+C_{n/p_{\min}}\cdot\frac{k_n}{k(n,p_{\min})},\quad\text{ when }p_{\min}>2$$ together with $$k_n=k_{n/p_{\min}}+1,\quad k(n,p_{\min})=k(n/p_{\min},p_{\min})+1$$

This can be done by storing and re-using data $k_n,k(n,p)$ and $C_n$ inductively, and generating a list of primes less than $n$, $\mathbb P_n$, along the way to use to check for $p_{\min}$. I have tested it, and it works fine.

The idea behind this is based on Alvin Lepik's answer, noting that the set of maximal elements is $Y_n:=\{y\in\mathbb N:n/2<y\leq n\}$ where $Y_n=\{n\}\cup Y_{n-1}$ when $n$ is NOT divisible by $2$ whereas $Y_n=\{n\}\cup Y_{n-1}\setminus\{n/2\}$ when $n$ is divisible by $2$. The cases for even $n$ where we remove $n/2$ from the set of maximal elements is the reason for subtracting $C_{n/2}$ for those cases in the recurrence relations above. A maximal element $y$ survives until we reach $n=2y$, then we remove it and construct the new chains based on this $n$.

Related Question