Approximate counting and sampling via local central limit theorems

We give an FPTAS for computing the number of matchings of size k in a graph G of maximum degree Δ on n vertices, for all k ≤ (1−δ)m*(G), where δ>0 is fixed and m*(G) is the matching number of G, and an FPTAS for the number of independent sets of size k ≤ (1−δ) αc(Δ) n, where αc(Δ) is the NP-hardness threshold for this problem. We also provide quasi-linear time randomized algorithms to approximately sample from the uniform distribution on matchings of size k ≤ (1−δ)m*(G) and independent sets of size k ≤ (1−δ)αc(Δ)n.