Counting the number of maximal chains in a poset

Question

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.

Answer 1

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

Answer 2

Let $X_{n}=\{1,2,…,n\} $. Let $C_{n}$ denote the total number of distinct maximal chains in $( X_{n},|)$, so trivially $C_{1}=1$. Let $\tilde{\omega} (n) $ denote the number of distinct odd prime factors of $n$.

Claim: For all $n\geq 1$: $$C_{n+1} \geq C_{n} \hspace{1mm} + \tilde\omega (n+1)$$

Proof: The case $n=1$ is clearly true $(C_{2}=1)$, so take $n\geq 2$.

Observe that the maximal chains in $X_{n}$ either remain maximal in $X_{n+1}$ or extend to a maximal chain in $X_{n+1}$ by adding the element $n+1$ to the chain. Thus, we obtain a partial surjective map from the set of maximal chains of $X_{n+1}$ to the set of maximal chains of $X_{n}$ given by: $$A\mapsto A\setminus \{n+1\}$$ The reason this map is partial is because there may be maximal chains of $X_{n+1}$ which could be mapped to non-maximal chains. Call these maximal chains "bad" chains. For example, $\{1,2,6\}$ is a maximal chain in $X_{6}$ but $\{1,2\}$ is not a maximal chain in $X_{5}$.

Suppose $B$ is a "bad" maximal chain in $X_{n+1}$. Let $ b $ be the largest element of $ B $ other than $ n+1 $. Since bad chains must contain $ n+1 $, we see that $ n+1\in B $, whence $ n+1 = bq $ for some positive integer $ q $.

If $ q $ is not prime, then we could take a prime factor $ p $ of $ q $ and extend $ B $ to a larger chain by adding $ bp $. As $ B $ is maximal, this can't happen.

If $ q=2 $, then $ n+1=2b $ and so $ B\setminus \{n+1\} $ is maximal in $ X_{n} $. This contradicts $ B $ being bad.

Finally, we see that whenever $ q $ is an odd prime, $ B $ is indeed a bad chain since $ B\setminus \{n+1\} $ can be extend to a larger chain by adding $ 2b $.

So we see that there are at least $ \tilde\omega (n+1) $ bad maximal chains, and that the set of non-bad maximal chains of $ X_{n+1} $ bijects (under the map previously defined) with the maximal chains of $ X_{n} $. Thus, we obtain the desired formula. $ \square $

Answer 3

Inspired by String 's answer, I think the safest course of action is to consider a so called maximal element in $X$. Can't think of a precise definition (maximum element of a maximal chain?) at the moment, but what I mean is the following:

Let $n=12$, for instance. Then a maximal element is $M>6$. $6$ itself cannot be maximal, since a chain ending with $6$ is extendable by $12$.

If $n=11$, then maximal element would be $M\geq \lceil\frac{n}{2}\rceil$. Again, a chain ending with $5$ is extendable by $10$.

We consider $f:\mathbb{N}\to\mathbb{N}$ defined by $$f(m:=p_1^{k_1}\ldots p_s^{k_s}) = \frac{(k_1+\ldots +k_s)!}{k_1!k_2!\ldots k_s!}\quad\mbox{and}\quad f(1):=1$$i.e it counts all maximal chains ending with $m$

Then, considering $Y$ as the set of all maximal elements of $n$, the total number of maximal chains is: $$\sum_{y\in Y}f(y) $$

The problem is, though, it isn't very practical. Suppose $n=100!$