10
$\begingroup$

Please give a combinatorial proof of the following:

The number of pairs $(A, B)$ of permutations of the set $\{ 1, 2,\ldots,n \}$ such that they have a total of $n+1$ cycles and their composition $AB$ is the permutation $(123 \ldots n)$, is the $n$th catalan number.

  • 0
    How do you define "combinatorial proof"?2011-10-08
  • 0
    Counting in two different ways or giving a bijection between two sets one of which is counted by the LHS and the other is counted by the RHS.2011-10-08
  • 0
    And what is the second set?2011-10-08
  • 0
    Dear Sanch: I don't understand: isn't the permutation $(123 \ldots n)$ the identity?2011-10-08
  • 0
    The second set maybe the set of all rooted trees with n + 1 vertices. The number of such trees with n + 1 vertices is the nth Catalan number.2011-10-08
  • 0
    @Pierre-Yves Gaillard: http://en.wikipedia.org/wiki/Cycle_notation2011-10-08
  • 0
    Dear @Chris: Thanks! Of course I knew this notation, but I guess what puzzled me is this: I believed the expressions "the **permutation** $(a_1\cdots a_n)$" and "the **n-cycle** $(a_1\cdots a_n)$" had different meanings. IMHO the latter is **much** clearer.2011-10-08
  • 0
    @Pierre: With cycle notation, if the permutation is just an n-cycle then the two expressions' meanings coincide. I've been informed by others before that cycle notation is much more universal than one-line notation.2011-10-08
  • 0
    Could you give an example, perhaps with $n=3$?2011-10-10
  • 0
    I'd probably have to see a non-combinatorial proof first :)2011-10-11
  • 0
    Dear @anaon: Thanks for your comment. You write "With cycle notation, if the permutation is just an $n$-cycle then the two expressions' meanings coincide." But, as I said in my first comment, the **permutation** $(123\cdots n)$ is the identity. It coincides with the $0$-cycle $()$. The **n-cycle** $(123\cdots n)$ is the **permutation** $(23\cdots n(n-1))$. - Beside from that, I agree with everything you said, and I like very much your contributions to this site.2011-10-12
  • 1
    @Pierre: I appreciate the kind words! As for what you said, understand that I say that the permutation $(123\cdots n)$ *in cycle notation* stands for the n-cycle $1\to2,2\to3,\dots,n\to1$ (you are correct that in one-line notation it would be denoted $(23\cdots n 1)$, and that $(123\cdots n)$ understood in one-line notation is the identity). In cycle notation you just write a permutation as disjoint cycles side-by-side, so if the permutation is itself just a single cycle (as here), the notations look exactly the same.2011-10-12
  • 0
    Dear @anon: Thanks! **You** are right: I should have written $(23\cdots n1)$ instead of $(23\cdots n(n-1))$. Sorry for the typo in your name.2011-10-13

3 Answers 3