Linear recurrences with constant coefficients: The multivariate case
From MaRDI portal
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.
Recommendations
- Multivariable recurrences with constant coefficients
- Multivariate linear recurrences and power series division
- Recurrence relations for the sections of the generating series of the solution to the multidimensional difference equation
- Systems of simultaneous linear recurrence relations with constant coefficients
- Analytic combinatorics in d variables: an overview
Cited in
(88)- The site-perimeter of bargraphs
- Basic analytic combinatorics of directed lattice paths
- Asymptotics of multivariate sequences. I: Smooth points of the singular variety
- Encoding algebraic power series
- Efficient counting of degree sequences
- On correctness of Cauchy problem for a polynomial difference operator with constant coefficients
- Multivariate linear recurrences and power series division
- Exchange relations, Dyck paths and copolymer adsorption
- From object grammars to ECO systems
- Walks confined in a quadrant are not always D-finite
- Solving the Cauchy problem for a two-dimensional difference equation at a point using computer algebra methods
- Counting walks with large steps in an orthant
- Generating function of the solution of a difference equation and the Newton polyhedron of the characteristic polynomial
- Evaluating the rational generating function for the solution of the Cauchy problem for a two-dimensional difference equation with constant coefficients
- Computational problems of multivariate hypergeometric theory
- Counting colored planar maps: algebraicity results
- Solvability of the Cauchy problem for a polynomial difference operator and monomial bases for the quotients of a polynomial ring
- Well-posedness of the Cauchy problem for multidimensional difference equations in rational cones
- Partially directed paths in a wedge
- Linear functional equations with a catalytic variable and area limit laws for lattice paths and polygons
- Longest alternating subsequences of \(k\)-ary words
- Kernel method and linear recurrence system
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- Explicit bounds for multidimensional linear recurrences with restricted coefficients
- Kernel method and system of functional equations
- Why Delannoy numbers?
- Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
- Algebraic diagonals and walks: algorithms, bounds, complexity
- Enumerative combinatorics of prographs
- Sections of the generating series of a solution to a difference equation in a simplicial cone
- The research and progress of the enumeration of lattice paths
- Systems of simultaneous linear recurrence relations with constant coefficients
- On the hierarchy of generating functions for solutions of multidimensional difference equations
- A human proof of Gessel's lattice path conjecture
- Combinatorics meets potential theory
- Multivariable recurrences with constant coefficients
- Constant coefficient linear difference equations on the rational cones of the integer lattice
- scientific article; zbMATH DE number 5837696 (Why is no real title available?)
- Proof of Ira Gessel's lattice path conjecture
- The Euler-Maclaurin formula for rational parallelotope
- On the importance sampling of self-avoiding walks
- An elementary solution of Gessel's walks in the quadrant
- Gröbner bases and their application to the Cauchy problem on finitely generated affine monoids
- Exactly solved models
- Formal Laurent series in several variables
- scientific article; zbMATH DE number 36110 (Why is no real title available?)
- scientific article; zbMATH DE number 7324712 (Why is no real title available?)
- scientific article; zbMATH DE number 7324738 (Why is no real title available?)
- scientific article; zbMATH DE number 7324815 (Why is no real title available?)
- Cauchy problem for multidimensional difference equations in lattice cones
- Multitime action recurrences on a monoid
- Recurrence relations for the sections of the generating series of the solution to the multidimensional difference equation
- scientific article; zbMATH DE number 7598168 (Why is no real title available?)
- Counting quadrant walks via Tutte's invariant method
- On 3-dimensional lattice walks confined to the positive octant
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Analytic solvability of the Hörmander problem and the Borel transformation of multiple Laurent series
- Asymptotics of lattice walks via analytic combinatorics in several variables
- Automaticity and invariant measures of linear cellular automata
- Generating functions for vector partition functions and a basic recurrence relation
- Higher dimensional lattice walks: connecting combinatorial and analytic behavior
- COMPLEXITY OF VILLAMAYOR'S ALGORITHM IN THE NON-EXCEPTIONAL MONOMIAL CASE
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- Walks in the quarter plane: Kreweras' algebraic model
- Solvability of the Cauchy Problem with a Polynomial Difference Operator
- scientific article; zbMATH DE number 7325218 (Why is no real title available?)
- Correctness of a Two-dimensional Cauchy Problem for a Polynomial Difference Operator with Constant Coefficients
- Difference Equations and Generating Functions for some Lattice Path Problems
- The Cauchy Problem for Multidimensional Difference Equations in Lattice Cones
- Counting lattice paths taking steps in infinitely many directions under special access restrictions
- Solving the Cauchy problem for a three-dimensional difference equation in a parallelepiped
- Fast Algorithms for Discrete Differential Equations
- Harmonic functions for singular quadrant walks
- Discrete generating functions
- Counting lattice paths by using difference equations with non-constant coefficients
- Riordan arrays and difference equations of subdiagonal lattice paths
- Weakly directed self-avoiding walks
- Walks avoiding a quadrant and the reflection principle
- Graceful bases in solution spaces of differential and difference equations
- Stability of the Cauchy problem for a multidimensional difference operator and the amoeba of the characteristic set
- Computer algebra in the service of enumerative combinatorics
- Height of walks with resets, the Moran model, and the discrete Gumbel distribution
- Pascal-like determinants are recursive
- On the summability of formal solutions of linear partial differential equations
- On directed lattice paths with vertical steps
- Families of prudent self-avoiding walks
- A history and a survey of lattice path enumeration
- Counting elements and geodesics in Thompson's group \(F\).
This page was built for publication: Linear recurrences with constant coefficients: The multivariate case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1591138)
