Connected permutation graphs

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