Connected permutation graphs

A permutation graph is a simple graph associated with a permutation. Let c_n be the number of connected permutation graphs on n vertices. Then the sequence {c_n} satisfies an interesting recurrence relation such that it provides partitions of n! as . We also see that, if uniformly chosen at random, asymptotically almost all permutation graphs are connected.