Matching

Author

Eric W. Weisstein
July 30, 2011

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Matching.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Matching.html.

©2011 Wolfram Research, Inc. except for portions noted otherwise

Classes

Complete (Subscript[K, n])

Φ[k_]:=((n!)/((2k)!!(n-2k)!))

Matching-Generating Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[Φ[k](x^k),{k,0,Floor[n/2]}]]]

Table[p,{n,10}]//Expand

Simplify[Table[(((-1))^n)(2^(n/2))(((-x))^(n/2))HypergeometricU[-n/2,1/2,-(1/(2x))],{n,10}],x>0]

Matching Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}]]]

Table[p,{n,10}]//Expand

Table[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}],{n,10}]

Table[(2^(-n/2))HermiteH[n,(x/(Sqrt[2]))],{n,10}]//Expand

Complete Bipartite (Subscript[K, n,n])

Φ[k_]:=k!((Binomial[n,k])^2)

Matching-Generating Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[Φ[k](x^k),{k,0,Floor[n/2]}]]]

Table[p,{n,10}]//Expand

Table[Sum[Φ[k](x^k),{k,0,Floor[n/2]}],{n,5}]

Table[(x^n)n!LaguerreL[n,-1/x],{n,5}]//Expand

Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingGeneratingPolynomial"][x],{n,5}]

Matching Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}]]]

Table[p,{n,10}]//Expand

Table[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}],{n,10}]

Table[(((-1))^n)n!LaguerreL[n,(x^2)],{n,5}]//Expand

Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingPolynomial"][x],{n,5}]//Expand

Cycle (Subscript[C, n])

Φ[k_]:=(n/(n-k))Binomial[n-k,k]

Matching-Generating Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[Φ[k](x^k),{k,0,Floor[n/2]}]]]

Table[p,{n,10}]//Expand

Table[Sum[Φ[k](x^k),{k,0,Floor[n/2]}],{n,10}]

Table[(x^(n ))LucasL[n,1/x],{n,10}]//Expand

Matching Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}]]]

Table[p,{n,10}]//Expand

Table[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}],{n,10}]

Table[(I^(-n))LucasL[n,I x],{n,10}]//Expand

Table[(I^n)LucasL[n,-I x],{n,10}]//Expand

FullSimplify[FunctionExpand[(I^(-n))LucasL[n,I x]],n∈Integers&&n>0]

Table[(((-2 x+2 I (Sqrt[4-(x^2)])))^(-n)) ((((-4))^n)+(((I x+(Sqrt[4-(x^2)])))^(2 n))),{n,10}]//FullSimplify//Expand

Empty (Subscript[(OverBar[K]), n])

Φ[k_]:=Piecewise[{{1,k==0}},0]

Φ[k_]:=DiscreteDelta[k]

Φ[k]//TraditionalForm

Matching-Generating Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[Φ[k](x^k),{k,0,Floor[n/2]}]]]

...wrong...

Table[p,{n,10}]//Expand

Table[Sum[Φ[k](x^k),{k,0,Floor[n/2]}],{n,10}]

Table[1,{n,10}]

Table[GraphData[{"Empty",n},"MatchingGeneratingPolynomial"][x],{n,10}]

Matching Polynomial

p=Assuming[n>0&&n∈Integers,FullSimplify[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}]]]

...wrong...

Table[p,{n,10}]//Expand

Table[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}],{n,10}]

Table[(x^n),{n,10}]//Expand

Table[GraphData[{"Empty",n},"MatchingPolynomial"][x],{n,10}]

Path (Subscript[P, n])

Matching-Generating Polynomial

Φ[k_]:=Binomial[n-k,k]

Assuming[n>0&&n∈Integers,FullSimplify[Sum[Φ[k](x^k),{k,0,Floor[n/2]}]]]

Matching Polynomial

Assuming[n>0&&n∈Integers,FullSimplify[Sum[(((-1))^k)Φ[k](x^(n-2k)),{k,0,Floor[n/2]}]]]