# Counting the number of maximal chains in a poset

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 necessarely generate a unique maximal chain.

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

• It's easy enough to calculate the number using dynamic programming in something like $n\log\log n$ time, but I don't think that translates to a nice closed formula. – Henning Makholm Nov 14 '16 at 12:58

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

• @JonCC: I think you misread my post. I only count chains ending with $m$. So for $m=12$ we have $\{1,2,4,12\},\{1,2,6,12\}$, and $\{1,3,6,12\}$. But nice answer you gave! :o) – String Nov 14 '16 at 16:25
• @JonCC: The chains correspond to permutations of the prime factors, $2,2,3$, $2,3,2$, and $3,2,2$. – String Nov 14 '16 at 16:27
• My apologies, you're quite right :). – JonCC Nov 14 '16 at 16:59

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$

• Unfortunately, I have discovered an error in my above "proof". Upon correction, the correct result is not as neat as one would hope :(. I will leave the corrected result up in the hope that it may be improved. – JonCC Nov 15 '16 at 3:52
• Oh, for instance $\omega (36) = 1$, but $\{36,12,6,3,1\}$ and $\{36,12,6,2,1\}$ are both bad in $X_{36}$. – Alvin Lepik Nov 15 '16 at 8:09
• Another problem arises when $n$ is prime. for instance the only maximal chain in $X_{11}$ is $\{11,1\}$. So we would have $\{11,1\}$ and only the bad chains in addition to it in $X_{12}$, but $\{12,6,2,1\}$ is also maximal in $X_{12}$ and it isn't a bad chain. – Alvin Lepik Nov 15 '16 at 8:19

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

• Interesting, nonetheless! – String Nov 15 '16 at 13:17
• Note that $Y:=\{y\in\mathbb N:n/2<y\leq n\}$ is the exact set of maximal elements. Thus, thinking inductively, each time $n$ is increased by $1$ we must remove $n/2$ from $Y$ if it is an integer (so when $n$ is even) and add $n$ to $Y$. – String Nov 15 '16 at 13:42