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

##### MSC:
 05A15 Exact enumeration problems, generating functions
Full Text: