Thanks to t.ravnushkin for helping in writing contents of this blog. Thanks to Alexdat2000 for proof-reading and to bashkort for announcing the month of blog posts. Even though I have started writing this blog before the announcement it would have probably been left in a trash bin due to my laziness.
Introduction
Matching is a beloved topic throughout competitive programming community due to its simple nature and fun applications. Matchings are not only useful in graph theory, but are also essential in topics such as game theory, partially ordered sets and combinatorics. In this blog we are gonna talk about less known applications of the subject. The main goal of the blog is explaining the intuition behind being able to associate the number of some combinatorial species to the amount of perfect matchings and understanding when it is possible to efficiently compute their counts. The blog mainly consists of two parts: one covering more general approach and the other one covering more combinatorial technique called graphical condensation which is applicable to some of the matching problems.
Prerequisites: basic linear algebra knowledge, gaussian elimination algorithm. Basically being able to compute determinant in $$$O(n^3)$$$ or having trust in possibility of doing so is enough