A binary string $S$ of length $2n$ is said to be non-nesting if there is a perfect matching $M$ between identical bits such that no two edges of $M$ are nesting.

Edges (2, 4) and (1, 6) are nesting (integers represents the location of identical bits inside the string $010110$).

What is the number of non-nesting binary strings?

  • $\begingroup$ Have you tried computing this for several small values of $n$, then seeing if the answer is in OEIS? $\endgroup$ – Mike Earnest Jan 20 at 22:41
  • $\begingroup$ I only ask because I have no other idea how to proceed. $\endgroup$ – Mike Earnest Jan 20 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.