Многочлен паросочетаний

Многочлен паросочетаний — производящая функция для числа паросочетаний различных размеров в графе.

Определения

Известны несколько связанных типов определений:

$m_{\mathrm{\Gamma }}(x):=\sum _{k\ge 0}{m}_k{x}^k,$

$M_{\mathrm{\Gamma }}(x):=\sum _{k\ge 0}(-1{)}^k{m}_k{x}^{n-2k},$

${\mu }_{\mathrm{\Gamma }}(x,y):=\sum _{k\ge 0}{m}_k{x}^k{y}^{n-2k},$

где $m_k$ обозначает число паросочетаний из $k$ пар графа $\mathrm{\Gamma }$.

Замечания

Каждый тип имеет свои преимущества, и все эквивалентны путем несложных преобразований. Например,

$M_{\mathrm{\Gamma }}(x)=x^n{m}_{\mathrm{\Gamma }}(-x^{-2})$

и

${\mu }_{\mathrm{\Gamma }}(x,y)=y^n{m}_{\mathrm{\Gamma }}(x/y^2).$

См. также

• Хроматический многочлен