2
$\begingroup$

A partition of $[n]$ is non-crossing if whenever four distinct elements $1\le a < b < c < d \le n $ are s.t. $a, c$ are both in one block and $b, d$ are both in another one, then the two blocks coincide.

I have showed that the number of non-crossing partitions (by dividing when $k$ and $n+1$ are connected and when they are disjointed) is:

$$ f(n+1) = \sum_{k=1}^{n+1} f(k-1)f(n+1-k) $$

Which is the recurrence formula for the Catalan's numbers as $f(0) = 1 = C_0$.

How to find a recurrence for the number of non-crossing partitions of $[n]$ without singletons? I have not found a good line of reasoning yet.

$\endgroup$
7
  • $\begingroup$ Your definition isn't easy to understand as it is. First of all, the word "block" isn't appropriate (a partition of a set is a set of covering subsets with no common elements, these subsets being often called "equivalence classes"). Moreover, can you give one or two examples... $\endgroup$
    – Jean Marie
    Nov 26, 2021 at 17:56
  • $\begingroup$ @JeanMarie There was a typo in the definition I wrote, so I fixed it, hope it's clear now $\endgroup$ Nov 26, 2021 at 18:02
  • $\begingroup$ No more clear. It must be the same for other colleagues, explaining that you haven't had echoes to your question. Please give an example. For example, how many "blocks" do you have ? As many as you want or only 2 ? $\endgroup$
    – Jean Marie
    Nov 26, 2021 at 18:06
  • $\begingroup$ If $n=7$, can $\{ \{3,5,7\},\{2,4\},\{1,6\} \}$ be called "non-crossing" without "singlets" (single element class= singleton) ? Please answer. $\endgroup$
    – Jean Marie
    Nov 26, 2021 at 18:41
  • $\begingroup$ @JeanMarie yes exactly I meant without singletons, another way to visualize them is illustrated here robertdickau.com/noncrossingpartitions.html, for example. You can think about $[n]$ as the set $\{1, 2, \dots , n \}$ and about the classes as blocks of a partition of that set which satisfy the conditions. $\endgroup$ Nov 26, 2021 at 18:57

1 Answer 1

2
$\begingroup$

Count the number $f(n)$ by cases of how many singletons the partition has. Let's denote by $g(n)$ the number of noncrossing partitions of $[n]$ without singletons. We have

$$f(n) = \sum_{j=0}^n {n \choose j}g(n-j)$$

because we can choose the $j$ singletons out of $n$ numbers and then the rest forms a non-crossing partition of $[n-j]$ without singletons.

We can express this as a matrix equation $f = Ag$ where $A = [{i \choose j}]_{ij}$.

Now (see for example here)

$$A^{-1} = [(-1)^{i+j}{i \choose j}]_{ij}$$

So we have a formula for the vector $g$ (since we know $f(n)=\frac{1}{n+1} { {2n} \choose n}$ are the Catalan numbers):

$$g(n) = \sum_{j=0}^n \frac{(-1)^{n+j}}{j+1} { {n} \choose j} { {2j} \choose j}. $$

EDIT:
These are the Riordan numbers (a more general OEIS-sequence was already linked by Jean Marie)

In the paper: link the following generating function equation is given and used to derive a recursion.

If we put $y = \sum g(n)x^n$, then

$$y = \frac{1}{1+x} + xy^2.$$

Implicit differentiation and arduous algebraic manipulation of the equations leads to

$$1 - x(1+x)(1-3x)y' = (1-3x^2)y.$$

From this the recursion

$$g(n) = \frac{n-1}{n+1}\left(2g(n-1)+3g(n-2)\right)$$

can be read.

$\endgroup$
2
  • $\begingroup$ That's really useful, thank you so much! Do you have any idea how to formulate a recursion for the $g(n)$? $\endgroup$ Nov 27, 2021 at 8:14
  • 1
    $\begingroup$ There's a nice recursion given in OEIS and a multitude of characterizations of the sequence. I put the main steps from one of the references into the solution. But I didn't check the derivation of the linear differential equation. Perhaps it can be verified by solving the generating equation for $y$ in terms of $x$. $\endgroup$
    – ploosu2
    Nov 27, 2021 at 10:37

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.