Efficient counting of degree sequences

We present formulas to count the set D₀(n) of degree sequences of simple graphs of order n, the set D(n) of degree sequences of those graphs with no isolated vertices, and the set D_{k_con}(n) of degree sequences of those graphs that are k-connected for fixed k. The formulas all use a function of Barnes and Savage and the associated dynamic programming algorithms all run in time polynomial in n and are asymptotically faster than previous known algorithms for these problems. We also show that |D(n)| and |D_{1_con}(n)| are asymptotically equivalent but |D(n)| and |D₀(n)| as well as |D(n)| and |D_{k_con}(n)| with fixed k≥2 are asymptotically inequivalent. Finally, we explain why we are unable to obtain the absolute asymptotic orders of these functions from their formulas.