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 [Sta11, Sec. 4.7] 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.\)

Polynomial sequences with rational generating functions may also satisfy shorter recurrences involving derivatives. The recurrence-space criterion determines when such a representation exists.

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.

#Choosing the states

To discover auxiliary states, we reverse the last construction step. If every remainder belongs to the original family, we can write a recurrence using that family alone. Otherwise, we record the extra information needed to continue, such as whether a required color has appeared or whether the last color agrees with the first. We then check closure: every construction step must lead to a state already on the list.

For tilings of a fixed-height strip, we record the cells occupied by tiles that started to the left of a moving vertical boundary. This is a profile. The maximum horizontal reach of the tiles determines how many columns ahead we must remember.

#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+z}{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.

#Straight triominoes and squares

Let \(t_n\) count tilings of a \(3\times n\) rectangle by \(2\times2\) squares and straight triominoes, placed horizontally or vertically. A horizontal triomino can protrude two columns beyond the boundary, so our profiles record the next two columns. Up to horizontal reflection, there are nine reachable classes \(A,\dotsc,I.\) The classes \(A,B,C\) each contain one profile, while \(D,\dotsc,I\) each contain two, giving \(15\) concrete profiles.

In the table, rows give current profiles and columns give successors. Dark blue cells are already occupied; orange stripes mark new triominoes and pink crosshatching marks new squares. Each transition shows three columns: remove the completed leftmost column to obtain the successor profile. An empty entry means no transition. The \(\times2\) at \((A,D)\) counts the two reflected placements; one is drawn.

Current / next $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$ $I$ A    × 2           B                 C                 D                 E               F                 G               H                 I                

We find all transitions by covering the lowest unoccupied cell of the current column until it is full, then advancing the boundary. The table lists every legal completion, so the state set is closed. All classes are reachable from \(A,\) using \(A\to C\to B,\) \(A\to D\to E\to F\to G\to I,\) and \(E\to H.\)

Let \(\mathbf v_n\) count partial tilings in the classes \(A,B,\dotsc,I,\) adding counts from reflected profiles. With columns indexed by the current class and rows by the successor class, the table has the nonzero pattern of \(M^{\mathsf T}.\) We obtain \[\mathbf v_{n+1}=M\mathbf v_n, \qquad \mathbf v_0=(1,0,0,0,0,0,0,0,0)^{\mathsf T},\] where \[M= \begin{pmatrix} 1&1&0&0&0&0&0&0&0\\ 0&0&1&0&0&0&1&0&0\\ 1&0&0&0&0&0&0&0&0\\ 2&0&0&0&0&0&0&1&0\\ 0&0&0&1&0&0&0&0&0\\ 0&0&0&0&1&0&0&0&1\\ 0&0&0&0&0&1&0&0&0\\ 0&0&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&1&0&0 \end{pmatrix}.\] A complete tiling ends in the empty profile \(A,\) so \(t_n=(M^n)_{A,A}.\) For \(n=0,1,\dotsc,9,\) the counts (A219968) are \[1,\ 1,\ 1,\ 2,\ 3,\ 4,\ 8,\ 13,\ 19,\ 35.\] For example, \(t_3=2\): three vertical triominoes or three horizontal ones. The characteristic polynomial is \[\chi_M(r)=r^9-r^8-3r^6+2r^5+r^3-r^2-1.\] For \(n\geq0,\) the counts satisfy \[t_{n+9}=t_{n+8}+3t_{n+6}-2t_{n+5}-t_{n+3}+t_{n+2}+t_n.\]

#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.

For a worked example and the connection with derivative recurrences, see Beraha–Kahane–Weiss and limiting zeros on the polynomial-recurrence page.

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}
   }