Return to Question

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Update:

Let $P_n^m$ be the number of three-connected planar graphs on $n$-vertices with $m$ edges. In particular, $P_n^{3n-6}$ are the triangulations. I think we have, in fact, $C_{n-3} \leq P_n^{3n-6}$ for $n\geq 4$.

Is there a nice injection from $C_{n-3}$ into $P_n^{3n-6}$?

Here is an alternative refinement:

Let $C_n^m$ be the number of Dyck paths of semilength $n$ with $m$ returns, i.e., https://www.findstat.org/StatisticsDatabase/St000011.

Then, it seems that $C_{n-3}^{m - 2n + 3} \leq P_n^m$ for $n\geq 4$ and all $m$, or, if you prefer, $C_n^m \leq P_{n+3}^{2n+3+m}$ for $n\geq 1$.

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Update:

Let $P_n^m$ be the number of three-connected planar graphs on $n$-vertices with $m$ edges. In particular, $P_n^{3n-6}$ are the triangulations.

Let $C_n^m$ be the number of Dyck paths of semilength $n$ with $m$ returns, i.e., https://www.findstat.org/StatisticsDatabase/St000011.

Then, it seems that $C_{n-3}^{m - 2n + 3} \leq P_n^m$ for $n\geq 4$ and all $m$, or, if you prefer, $C_n^m \leq P_{n+3}^{2n+3+m}$ for $n\geq 1$.

Variation:

We also have, I think, $C_{n-4} \leq P_n^{3n-6}$ for $n\geq 4$. (I had an off-by-one error in a previous version of the question.)

Is there a nice injection from $C_{n-4}$ into $P_n^{3n-6}$?

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Update:

Let $P_n^m$ be the number of three-connected planar graphs on $n$-vertices with $m$ vertices. In particular, $P_n^{3n-6}$ are the triangulations. I think we have, in fact, $C_{n-3} \leq P_n^{3n-6}$ for $n\geq 4$.

Is there a nice injection from $C_{n-3}$ into $P_n^{3n-6}$?

Here is an alternative refinement:

Let $C_n^m$ be the number of Dyck paths of semilength $n$ with $m$ returns, i.e., https://www.findstat.org/StatisticsDatabase/St000011.

Then, it seems that $C_{n-3}^{m - 2n + 3} \leq P_n^m$ for $n\geq 4$ and all $m$, or, if you prefer, $C_n^m \leq P_{n+3}^{2n+3+m}$ for $n\geq 1$.

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Update:

Let $P_n^m$ be the number of three-connected planar graphs on $n$-vertices with $m$ edges. In particular, $P_n^{3n-6}$ are the triangulations. I think we have, in fact, $C_{n-3} \leq P_n^{3n-6}$ for $n\geq 4$.

Is there a nice injection from $C_{n-3}$ into $P_n^{3n-6}$?

Here is an alternative refinement:

Let $C_n^m$ be the number of Dyck paths of semilength $n$ with $m$ returns, i.e., https://www.findstat.org/StatisticsDatabase/St000011.

Then, it seems that $C_{n-3}^{m - 2n + 3} \leq P_n^m$ for $n\geq 4$ and all $m$, or, if you prefer, $C_n^m \leq P_{n+3}^{2n+3+m}$ for $n\geq 1$.

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Update:

Here is a possibly easier refinement:

Let $C_n^m$ be the number of Dyck paths of semilength $n$ with $m$ returns, i.e., https://www.findstat.org/StatisticsDatabase/St000011.

Let $P_n^m$ be the number of three-connected planar graphs on $n$-vertices with $m$ vertices.

Then, it seems that $C_{n-3}^{m - 2n + 3} \leq P_n^m$ for $n\geq 4$ and all $m$, or, if you prefer, $C_n^m \leq P_{n+3}^{2n+3+m}$ for $n\geq 1$.

For example, there is a single Dyck path of semilength $n-3$ with $n-3$ returns, and there are several three-connected planar graphs on $n$ vertices with $3n-6$ edges (the triangulations).

Variation:

Is there a nice injection from $C_{n-3}$ into $P_n^{3n-6}$?

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Update:

Let $P_n^m$ be the number of three-connected planar graphs on $n$-vertices with $m$ vertices. In particular, $P_n^{3n-6}$ are the triangulations. I think we have, in fact, $C_{n-3} \leq P_n^{3n-6}$ for $n\geq 4$.

Is there a nice injection from $C_{n-3}$ into $P_n^{3n-6}$?

Here is an alternative refinement:

Let $C_n^m$ be the number of Dyck paths of semilength $n$ with $m$ returns, i.e., https://www.findstat.org/StatisticsDatabase/St000011.

Then, it seems that $C_{n-3}^{m - 2n + 3} \leq P_n^m$ for $n\geq 4$ and all $m$, or, if you prefer, $C_n^m \leq P_{n+3}^{2n+3+m}$ for $n\geq 1$.