Многочлен паросочетаний — производящая функция для числа паросочетаний различных размеров в графе.
Известны несколько связанных типов определений:
где m k {\displaystyle m_{k}} обозначает число паросочетаний из k {\displaystyle k} пар графа Γ {\displaystyle \Gamma } .
Каждый тип имеет свои преимущества, и все эквивалентны путем несложных преобразований. Например,
и