The binding energies of n < 100 carbon clusters are calculated using the ab-initio density functional theory code Quantum Espresso. Carbon cluster geometries are determined using several levels of classical techniques and further refined using density functional theory. The resulting energies are used to compute the work of cluster formation and the nucleation rate in a saturated, hydrogen-poor carbon gas. Compared to classical calculations that adopt the capillary approximation, we find that nucleation of carbon clusters is enhanced at low temperatures and depressed at high temperatures. This difference is ascribed to the different behavior of the critical cluster size. We find that the critical cluster size is at n = 27 or n = 8 for a broad range of temperatures and saturations, instead of being a smooth function of such parameters. The results of our calculations can be used to follow carbonaceous cluster/grain formation, stability, and growth in hydrogen poor environments, such as the inner layers of core-collapse supernova and supernova remnants.