A permutation pi of [n] = {1, 2, ..., n} is irreducible if pi([m]) = [m] for no m in [n], m<n, and it is connected if for no subinterval I of [n], 2 <= |I| <= n-1, the image pi(I) is an interval. We review enumeration of irreducible permutations and their appearances in mathematics. Then we enumerate connected permutations. Asymptotically, there are n!/e2 of them, and exactly (for n>2) their number equals 2.(-1)n+1 minus the coefficient of xn in the compositional inverse of 1!x + 2!x^2 + ... . We show that their numbers are not P-recursive, are congruent modulo high powers of 2 to 2.(-1)n+1, and are congruent modulo 3 to -Cn-1 + (-1)n where Cn is the Catalan number.