How to count number of matchings?

Question

Suppose we have a bipartite graph $G$ with bipartition $(A,B)$ such that $A=\{a_{1},...a_{n}\}$ and $B=\{b_{1},...,b_{n},b_{n+1} \}$ and the vertex $a_{k}$ is adjacent to $b_{1}, b_{2} , .... , b_{k+1}$ for $k=1,2,..n$

Then it can be shown that there exist exactly $2^{n}$ matching's in G that cover A. Why?

I tried to do it by induction, also I know about Halls thereom but I am not sure I will need it.

The base case is clear because we have exactly two matching, each consists of a single edge.

Next I suppose that it is true for $n-1$ and want to show this implies it is true for n. But that is where I am stuck.

I know that going from $n-1$ to n will cause the addition of two new vertices, one in A and one in B.

I thought maybe we could partition the matching's for n as $M1,M2,...M(2^{k-1})$

but then I am not sure how to proceed.

Maybe induction isn't even the correct way? If not maybe I could use thereoms for bipartite graphs such as the fact that the maximum matching number is equal to the minimum vertex number?

Any help please

Answer 1

I don't think induction on the number of nodes in the graph is the clearest way to go. Instead, induct on the nodes like this (although, in the end, it's exactly the same thing): A matching that covers $A$ must specifically cover $a_1$. How many choices of edges do you have to do that? Once you've made that choice, how many choices do you have to pick an edge that covers $a_2$? Now keep going, and you'll get your answer.

Answer 2

you want the bijections of $\{1,2,3,\dots, n\}$ such that $f(k)\leq k+1$ for all $k$.

as you guessed we can count them by indution.

If we have $f(n)=n$ then there are clearly $2^{n-1}$ such function by the iduction hypothesis.. If we do not have $f(n)=n$ then we must clearly have $f(n-1)=n$ and every "good" bijection of $\{1,2,\dots, n\}$ gives us a good function $f$ such that $f(n)\neq n$ by letting $f(k)=g(k)$ for $k<n$ , letting $f(n-1)=g(n)$ and letting $f(n)=g(n-1)$. this assignment is bijective.

So there are $2^{n-1}+2^{n-1}$ such functions.