We present an iterative algorithm to count Feynman diagrams via many-body relations. The algorithm allows us to count the number of diagrams of the exact solution for the general fermionic many-body problem at each order in the interaction. Further, we apply it to different parquet-type approximations and consider spin-resolved diagrams in the Hubbard model. Low-order results and asymptotics are explicitly discussed for various vertex functions and different two-particle channels. The algorithm can easily be implemented and generalized to many-body relations of different forms and levels of approximation.