Short of A Matching
The Marriage Theorem is fundamental to matching theory. It provides for a necessary and sufficient condition for finding a perfect matching in a bipartite graph. A bipartite graph can be thought of as the realization of a relation 
. A matching 
in 
is a collection of mutually disjoint pairs 
from . Specifically, for any 
and 
, 
and 
. A perfect matching in has 
pairs. Notice that for any subset 
, 
must be at least 
for to even admit the possibility of a perfect matching. The Marriage Theorem states that the seemingly obvious necessary condition alone is also sufficient — that is to say, if the condition is true, then indeed admits a perfect matching!
The theorem is witnessed by an ample number of proofs. Just as fascinating is the number and nature of contexts in which it has been applied. Here we sketch the proof of a somewhat general version of the marriage theorem, and we use the marriage theorem in this proof.
Permutations with Cycles
This is a digital sketch inspired by the equality: C(n,k) = C(n-1,k-1) + C(n-1,k) (n-1), where C(n,k) denotes the number of permutations of, say, [n] with k cycles. The equality is nearly self-explanatory — you simply knock off one of the elements (let’s do away with n) and stare at permutations of [n-1]. Click here ...
Hello world!
Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!