Recently, I was going over an introduction to Holographic Algorithms. I came across some combinatorial objects called Pfaffians. I do not really know much about those at the moment and came across some surprising uses they can be put to.For instance, I came to know that they can be used to efficiently count the number of perfect matchings in planar graphs. Also, they can be used to count the number of possible tilings of a chessboard using 2*1 tiles. The tiling connection seemed very curious to me and I tried searching for more relevant materials on the web but in most places I merely found just one statement or two about the connection and nothing else.I just meant to ask if someone could suggest some reference to relevant literature as that would be really great and I am looking forward to study some related materials.
Regarding Pfaffian Methods in Counting and Combinatorics
reference request;co.combinatorics;counting complexity
(This is an interesting question for me because I'm also reading about the Pfaffian.) I suggest the following references:Chapter 8 of the awesome book Matching Theory by Lovasz and Plummer.The paper Division-Free Algorithms for the Determinant and the Pfaan: Algebraic and Combinatorial Approaches by Rote. This paper relates the Pfaffian with the combinatorial object called alternating closed walk sequence (aka. alternating clow sequence), which gives us a dynamic (division-free) algorithm for computing the Pfaffian.The paper Nonintersecting paths, pfaans, and plane partitions by Stembridge, which shows how to use the Pfaffian to enumerate configurations in combinatorics. The paper also gives combinatorial proofs of basic identities, e.g.,If $A$ is a skew-symmetric matrix, then $\mathsf{pf}(A)^2 = \mathsf{det}(A)$.