Многочлен паросочетаний — производящая функция для числа паросочетаний различных размеров в графе.
Определения
Известны несколько связанных типов определений:
![{\displaystyle m_{\Gamma }(x):=\sum _{k\geq 0}m_{k}x^{k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a01c7a06284a2152b2e3fa860d869a318ec26d53)
![{\displaystyle M_{\Gamma }(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b12d81d6aae0612f1a306788fc42225f6ea8ce8)
![{\displaystyle \mu _{\Gamma }(x,y):=\sum _{k\geq 0}m_{k}x^{k}y^{n-2k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8557376801bb156d9aa7f3fbeb92c56749fe724c)
где
обозначает число паросочетаний из
пар графа
.
Замечания
Каждый тип имеет свои преимущества, и все эквивалентны путем несложных преобразований. Например,
![{\displaystyle M_{\Gamma }(x)=x^{n}m_{\Gamma }(-x^{-2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd8bb4748eeef73051e029e7edf6df27901413d5)
и
![{\displaystyle \mu _{\Gamma }(x,y)=y^{n}m_{\Gamma }(x/y^{2}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdddf1aabdf8f1c54de27484f1af954b3a3c737c)
См. также
Эта страница в последний раз была отредактирована 16 января 2019 в 04:30.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.