The symmetric functions catalog

#The transfer matrix method

The transfer matrix method turns a finite-state enumeration problem into matrix multiplication. It is especially useful when objects are built from left to right and only a bounded amount of boundary data is needed to continue the construction. See [Sec. 4.7, Sta11] for the classical presentation.

Let \(\mathcal{S}\) be a finite set of states, and let \(A=(a_{st})_{s,t\in\mathcal{S}}\) be a matrix with entries in a commutative ring \(R.\) We interpret \(a_{st}\) as the weight of a transition from state \(s\) to state \(t.\)

The method also applies with extra variables in the entries of \(A.\) In that case the matrix records a weighted enumeration, and specializations of the variables recover ordinary counts.

#Binary words with no consecutive ones

Let \(a_n\) be the number of binary words of length \(n\) with no consecutive ones. We use two states, recording whether the last letter is \(0\) or \(1.\) If \[\bvec_n = \begin{pmatrix} b_n^{(0)}\\ b_n^{(1)} \end{pmatrix}\] records the number of valid words ending in \(0\) and \(1,\) then \[\bvec_{n+1} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} \bvec_n .\] Thus \(a_n=b_n^{(0)}+b_n^{(1)},\) and one obtains \[\sum_{n\geq 0} a_n z^n = \frac{1}{1-z-z^2}.\] Equivalently, \(a_n=F_{n+2},\) where \(F_n\) is the Fibonacci sequence.

#Proper colorings of paths and cycles

Let \(B\) be the \(q\times q\) matrix with \(0\) on the diagonal and \(1\) off the diagonal. A product of entries in \(B\) records whether adjacent vertices have distinct colors.

For the path graph on \(n\) vertices, the number of proper \(q\)-colorings is \[\mathbf{1}^\top B^{n-1}\mathbf{1} = q(q-1)^{n-1}.\] For the cycle graph \(C_n,\) the first and last colors must also be adjacent, so the transfer matrix expression is a trace: \[\chi_{C_n}(q) = \operatorname{tr}(B^n) = (q-1)^n + (q-1)(-1)^n .\] This is the usual chromatic polynomial of a cycle.

#Domino tilings of a strip

The number of domino tilings of a \(2\times n\) rectangle can be computed by recording which cells in the next column are already occupied by horizontal dominoes. The possible boundary states are the four subsets of the two cells, which we encode by \(0,1,2,3.\) With rows and columns ordered in this way, the transfer matrix is \[A= \begin{pmatrix} 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{pmatrix}.\] The entry \((A^n)_{0,0}\) counts tilings which start and end with an empty boundary. This gives the Fibonacci recurrence for the number of domino tilings of a \(2\times n\) rectangle.

Weighted versions of the same matrix give bivariate generating functions recording, for example, the number of vertical and horizontal dominoes.

#Weighted tilings by larger tiles

Let \(P_n(t)\) be the generating polynomial for tilings of a \(4\times n\) rectangle using unit squares and \(2\times 2\) squares, where each \(2\times 2\) square contributes a factor of \(t.\) Thus the coefficient of \(t^k\) counts tilings using exactly \(k\) large squares. This is the rectangular big-tile case \(\mu=(2,2)\) in the tiling polynomials studied by J. Ahlberg and P. Alexandersson [AA26].

Process the board column by column. A boundary state records which cells in the next column have already been occupied by \(2\times 2\) squares started in the previous column. For height \(4,\) starting from the empty boundary, only the five states \[\emptyset,\quad 12,\quad 23,\quad 34,\quad 1234\] can occur, where for instance \(23\) means that rows \(2\) and \(3\) are already occupied. Indeed, a \(2\times2\) square crossing the boundary occupies an adjacent pair of rows, and two such squares can cross the same boundary only in the disjoint pairs \(12\) and \(34.\) The shaded cells in the following figure are precisely the rows recorded by the boundary state.

Using column vectors, with rows indexed by the next state and columns indexed by the current state in the order above, the transfer matrix is \[A(t)= \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ t & 0 & 0 & t & 0 \\ t & 0 & 0 & 0 & 0 \\ t & t & 0 & 0 & 0 \\ t^2 & 0 & 0 & 0 & 0 \end{pmatrix}.\] For example, from the empty state one may start no large square, one large square in rows \(12,\) \(23,\) or \(34,\) or two large squares in rows \(12\) and \(34.\) This explains the first column of \(A(t).\)

For \(n=2,\) the coefficient \(P_2(t)=1+3t+t^2\) has the following direct interpretation. There is one tiling using no \(2\times2\) square, three tilings using one \(2\times2\) square, and one tiling using two \(2\times2\) squares.

The desired polynomial is the empty-to-empty entry \[P_n(t)=\bigl(A(t)^n\bigr)_{\emptyset,\emptyset}.\] Consequently, \[\sum_{n\geq 0} P_n(t) z^n = \frac{1-tz} {1-(1+t)z-(2t+t^2)z^2+(t^2+t^3)z^3}.\] The first few polynomials are \[\begin{array}{c|l} n & P_n(t) \\ \hline 0 & 1\\ 1 & 1\\ 2 & 1+3t+t^2\\ 3 & 1+6t+4t^2\\ 4 & 1+9t+16t^2+8t^3+t^4\\ 5 & 1+12t+37t^2+34t^3+9t^4 . \end{array}\]

#Limiting zero sets

Transfer matrices also give an asymptotic tool for locating complex zeros. After diagonalization, a sequence often has the form \[f_n(z)=\sum_{k=1}^m \alpha_k(z)\lambda_k(z)^n,\] where the \(\lambda_k\) are transfer-matrix eigenvalues.

Thus isolated limiting zeros arise from vanishing amplitudes, while curves of limiting zeros usually arise where dominant eigenvalues have equal modulus. This theorem concerns asymptotic complex root location; it does not by itself imply real-rootedness of any fixed \(f_n.\)

Bibliography

1. [AA26]John Ahlberg and Per Alexandersson. Polynomials from tilings of rectangles. arXiv:2605.03473, 2026.
   .bib

   Copy Download

   @article{AhlbergAlexandersson2026,
     author = {John Ahlberg and Per Alexandersson},
     title = {Polynomials from tilings of rectangles},
     year = {2026},
     eprint = {2605.03473},
     archivePrefix = {arXiv},
     primaryClass = {math.CO}
   }
   

2. [BKW75]S. Beraha, J. Kahane and N. J. Weiss. Limits of zeroes of recursively defined polynomials. Proceedings of the National Academy of Sciences, 72(11):4209–4209, 1975.
   .bib

   Copy Download

   @article{Beraha75limits,
     author = {S. Beraha and J. Kahane and N. J. Weiss},
     title = {Limits of zeroes of recursively defined polynomials},
     journal = {Proceedings of the National Academy of Sciences},
     year = {1975},
     volume = {72},
     number = {11},
     pages = {4209--4209},
     doi = {10.1073/pnas.72.11.4209},
     url = {https://doi.org/10.1073/pnas.72.11.4209}
   }
   

3. [Sok04]Alan D. Sokal. Chromatic roots are dense in the whole complex plane. Combinatorics, Probability and Computing, 13(2):221–261, 2004.
   .bib

   Copy Download

   @article{Sokal2004ChromaticRoots,
     author = {Alan D. Sokal},
     title = {Chromatic roots are dense in the whole complex plane},
     year = {2004},
     journal = {Combinatorics, Probability and Computing},
     volume = {13},
     number = {2},
     pages = {221--261},
     doi = {10.1017/S0963548303006023},
     url = {https://doi.org/10.1017/S0963548303006023},
     eprint = {cond-mat/0012369}
   }
   

4. [Sta11]Richard P. Stanley. Enumerative Combinatorics: Volume 1. Cambridge University Press, Second, 2011.
   .bib

   Copy Download

   @book{StanleyEC1,
    author = {Richard P. Stanley},
    title = {Enumerative {C}ombinatorics: {V}olume 1},
    year = {2011},
    isbn = {9781107602625},
    edition = {Second},
    doi = {10.1017/CBO9781139058520},
    publisher = {Cambridge University Press}
   }