4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Nov 14 '16 at 12:58
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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) $\endgroup$ – String Nov 14 '16 at 16:25
  • $\begingroup$ @JonCC: The chains correspond to permutations of the prime factors, $2,2,3$, $2,3,2$, and $3,2,2$. $\endgroup$ – String Nov 14 '16 at 16:27
  • $\begingroup$ My apologies, you're quite right :). $\endgroup$ – JonCC Nov 14 '16 at 16:59
3
$\begingroup$

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 $

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JonCC Nov 15 '16 at 3:52
  • $\begingroup$ Oh, for instance $\omega (36) = 1$, but $\{36,12,6,3,1\}$ and $\{36,12,6,2,1\}$ are both bad in $X_{36}$. $\endgroup$ – Alvin Lepik Nov 15 '16 at 8:09
  • $\begingroup$ 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. $\endgroup$ – Alvin Lepik Nov 15 '16 at 8:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Interesting, nonetheless! $\endgroup$ – String Nov 15 '16 at 13:17
  • $\begingroup$ 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$. $\endgroup$ – String Nov 15 '16 at 13:42

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.