zbMATH — the first resource for mathematics

Linear recurrences with constant coefficients: The multivariate case. (English) Zbl 0963.05005
Let \(H=\{h_1,\dots,h_k\}\) be a fixed set of vectors with \(d\) integer coordinates. If \(n=(n_1,\dots,n_d)\) is a vector of \(d\) non-negative integers, then write \(\bar{x}^n\) for \(x_1^{n_1}\cdots x_d^{n_d}\). This paper studies multivariate generating functions of the form \(\sum_n a_n \bar{x}^n\) whose coefficients satisfy a linear recurrence relation \(a_n=\sum_{h\in H}c_h a_{n+h}\) in which each \(c_h\) is a constant. The univariate case (\(d=1\)) is well known to give rational generating functions. The multivariate case has richer variety as is shown here by a number of examples including lattice paths, knight’s walks and Young tableaux of bounded height. The main tool employed is a variant of the kernel method. On the theoretical side, an existence and uniqueness result for a solution to the general recurrence is obtained. The key property required is that the convex hull of the set \(H\) should not meet the first orthant.

05A15 Exact enumeration problems, generating functions
Full Text: DOI