Quantum random walk on the integer lattice: examples and phenomena (2009)
Bressler, Andrew, Greenwood, Torin, Pemantle, Robin, Petkovsek, Marko
We apply results from Baryshnikov, Brady, Bressler and Pemantle (2008) to compute limiting probability profiles for various quantum random walks in one and two dimensions. Using analytic machinery we...
On a conjecture of Ira Gessel (2008)
Petkovsek, Marko, Wilf, Herbert S.
Let F(m; n1, n2) denote the number of lattice walks from (0,0) to (n1,n2), always staying in the first quadrant {(n_1,n_2); n1 >= 0, n2 >= 0} and having exactly m steps, each of which belongs to the...
Counting One-Vertex Maps (2008)
Orbanic, Alen, Petkovsek, Marko, Pisanski, Tomaz, Potocnik, Primoz
The number of distinct maps (pre-maps) with a single vertex and valence $d$ is computed for any value of $d$. The types of maps (pre-maps) that we consider depend on whether the underlaying graph...
Symbolic Computation with P-finite Sequences (2007)
[summary by Bruno Salvy] The talk consists in two parts. The first part is devoted to computer algebra algorithms for the manipulation of P-finite (holonomic in one variable) sequences and the second...
A Comparison of Degree Polynomials (Note) (2007)
Marko Petkovsek, Christian Weixlbaumer
All known algorithms for finding polynomial solutions of linear difference equations with polynomial coefficients start out by computing a degree bound
A Generalization of Gosper's Algorithm (2007)
We present a derivation of Gosper's algorithm which permits generalization to higher-order recurrences with constant least and most significant coefficients. Like Gosper's algorithm, the...
q-Hypergeometric Solutions of q-Difference Equations (2007)
Sergei A. Abramov, Peter Paule, Marko Petkovsek
We present algorithm qHyper for finding all solutions y(x) of a linear homogeneous q-difference equation, such that y(qx) = r(x)y(x) where r(x) is a rational function of x. Applications include...
Given a word w of length n over a finite alphabet and a set of ordered pairs of letters which define adjacencies, we construct an n- vertex graph which we call the letter graph of w. The lettericity...
q-Hypergeometric Solutions of q-Difference Equations (2007)
Sergei A. Abramov, Peter Paule, Marko Petkovsek
We present algorithm qHyper for finding all solutions y(x) of a linear homogeneous q-difference equation such that y(qx) = r(x)y(x) where r(x) is a rational function of x. Applications include...
Multibasic and Mixed Hypergeometric Gosper-Type Algorithms (2007)
Introduction and notation Let F be a field of characteristic zero and ht n i 1 n=0 a sequence of elements from F which is eventually non-zero. Call t n : 1. hypergeometric, if there are polynomials p...
Polynomial Solutions of Linear Operator Equations (2007)
The algorithm described here extends the algorithm to find all polynomial solutions of differential and difference equations that was given in [1, 2] to more general operators. It also takes a more...
While in the univariate case solutions of linear recurrences with constant coefficients have rational generating functions, in the multivariate case the situation is much more interesting: even...
While in the univariate case solutions of linear recurrences with constant coefficients have rational generating functions, in the multivariate case the situation is much more interesting: even...
The Zarankiewicz problem via Chow forms (2007)
Marko Petkovsek, James Pommersheim, Irena Swanson
The well-known Zarankiewicz problem [Za] is to determine the least positive integer Z(m; n; r; s) such that each m \Theta n 0-1 matrix containing Z(m; n; r; s) ones has an r \Theta s submatrix...
On subgraphs of Cartesian product graphs (2007)
Sandi Klavzar, Alenka Lipovec, Marko Petkovsek
Graphs which can be represented as nontrivial subgraphs of Cartesian product graphs are characterized. As a corollary it is shown that any bipartite, K 2;3-free graph of radius 2 has such a...
Letter Graphs and Well-Quasi-Order by Induced Subgraphs (2007)
Given a word w over a finite alphabet and a set of ordered pairs of letters which define adjacencies, we construct a graph which we call the letter graph of w. The lettericity of a graph G is the...
The Zarankiewicz problem via Chow forms (2007)
Marko Petkovsek, James Pommersheim, Irena Swanson
The well-known Zarankiewicz problem [Za] asks to determine the least positive integer Z(m; n; r; s) such that each m \Theta n zero-one matrix containing Z(m; n; r; s) ones has an r \Theta s submatrix...
Multibasic and mixed Gosper’s algorithm (2007)
Gosper's summation algorithm finds a hypergeometric closed form of an indefinite sum of hypergeometric terms, if such a closed form exists. We generalize his algorithm to the case when the terms...
Combinatorial Interpretation of Unsigned Stirling and Lah Numbers (2007)
Marko Petkovsek, Tomaz Pisanski
The combinatorial role of unsigned Stirling and Lah numbers is reexamined in connection with ordinary powers, rising factorial powers, and falling factorial powers. Several bijective proofs are given.
Walks confined in a quadrant are not always D-finite (2007)
Mireille Bousquet-Melou, Marko Petkovsek, Marko Petkov Sek
We consider planar lattice walks that start from a prescribed position, take their steps in a given nite subset of Z , and always stay in the quadrant x 0; y 0. We rst give a criterion which...
Walks confined in a quadrant are not always D-finite (2002)
Bousquet-Melou, Mireille, Petkovsek, Marko
We consider planar lattice walks that start from a prescribed position, take their steps in a given finite subset of Z^2, and always stay in the quadrant x >= 0, y >= 0. We first give a criterion...
Linear Recurrences With Constant Coefficients: The Multivariate Case (2000)
Mireille Bousquet-Melou, Marko Petkovsek
While in the univariate case solutions of linear recurrences with constant coeOEcients have rational generating functions, we show that the multivariate case is much richer: even though initial...
Solving Discrete Initial- and Boundary-Value Problems (1999)
Multivariate linear recurrences appear in such diverse fields of mathematics as combinatorics, probability theory, and numerical resolution of partial differential equations. Whereas in the...
Solving Discrete Initial- and Boundary-Value Problems (1999)
Multivariate linear recurrences appear in such diverse fields of mathematics as combinatorics, probability theory, and numerical resolution of partial differential equations. Whereas in the...
Solving Discrete Initial- and Boundary-Value Problems (1999)
Multivariate linear recurrences appear in such diverse fields of mathematics as combinatorics, probability theory, and numerical resolution of partial differential equations. Whereas in the...
Multibasic and Mixed Hypergeometric Gosper-Type Algorithms (1999)
Gosper's summation algorithm finds a hypergeometric closed form of an indefinite sum of hypergeometric terms, if such a closed form exists. We extend his algorithm to the case when the terms are...
Hypergeometric Solutions of Linear Recurrences with Polynomial Coefficients (1998)
this paper we present algorithm Hyper which can be used to find all hypergeometric solutions of (1.3). To give some motivation, we describe first an application of algorithm Hyper to definite...
New Universal Aspects of Diffusion in Strongly Chaotic Systems (1997)
Robnik, Marko, Dobnikar, Jure, Rapisarda, Andrea, Prosen, Tomaz, Petkovsek, Marko
We study some new universal aspects of diffusion in chaotic systems, especially such having very large Lyapunov coefficients on the chaotic (indecomposable, topologically transitive) component. We do...
How to do MONTHLY problems with your computer (1997)
Istvan Nemes, Marko Petkovsek, Herbert S. Wilf, Doron Zeilberger
this article (PWZ) have just written a book [8] that describes the theoretical foundations of the solution of this problem, and also gives the software by means of which everyone can perform these...
Marko Petkovsek, Donald E. Knuth, Doron Zeilberger, Herbert Wilf
Contents Foreword vii AQuickStart... ix I Background 1 1 Proof Machines 3 1.1 Evolutionoftheprovinceofhumanthought .............. 3 1.2 Canonicalandnormalforms....................... 7 1.3...
How to do MONTHLY problems with your computer (1997)
István Nemes, Marko Petkovsek, Herbert S. Wilf, Doron Zeilberger
this article (PWZ) have just written a book [8] that describes the theoretical foundations of the solution of this problem, and also gives the software by means of which everyone can perform these...
When Can the Sum of (1/p)th of the Binomial Coefficients Have Closed Form? (1996)
We find all nonnegative integer $r, s, p$ for which the sum $\sum^{sn}_{k=rn}{pn \choose k}$ has closed form.
Special Formal Series Solutions of Linear Operator Equations (1996)
Sergei A. Abramov, Marko Petkovsek, Anna Ryabenko
The transformation which assigns to a linear operator L the recurrence satisfied by coefficient sequences of the polynomial series in its kernel, is shown to be an isomorphism of the corresponding...
An Introduction to Pseudo-Linear Algebra (1996)
Manuel Bronstein, Marko Petkovsek
Pseudo-linear algebra is the study of common properties of linear differential and difference operators. We introduce in this paper its basic objects (pseudo-derivations, skew polynomials, and...
Special Power Series Solutions of Linear Differential Equations (Extended Abstract) (1996)
Sergei A. Abramov, Marko Petkovsek
) Sergei A. Abramov Computer Center of the Russian Academy of Science, Vavilova 40, Moscow 117967, Russia. abramov@ccas.ru Marko Petkovsek y Department of Mathematics, University of Ljubljana,...
A High-Tech Proof of the Mills-Robbins-Rumsey Determinant Formula (1995)
Marko Petkovsek, Herbert S. Wilf
this paper. Hence any reader who wishes to do so can cut-and-paste it from there and verify that it does indeed certify the recurrence. It can also be computed by using the Paule-Schorn...
A High-Tech Proof of the Mills-Robbins-Rumsey Determinant Formula (1995)
Marko Petkovsek, Herbert S. Wilf
this paper. Hence any reader who wishes to do so can cut-and-paste it from there and verify that it does indeed certify the recurrence. It can also be computed by using the Paule-Schorn...
On Polynomial Solutions of Linear Operator Equations (1995)
Sergei A. Abramov, Manuel Bronstein, Marko Petkovsek
Introduction Let K be a field of characteristic 0 and L : K[x] ! K[x] an endomorphism of the K-linear space of univariate polynomials over K. We consider the following computational tasks concerning...
D'Alembertian Solutions of Linear Differential and Difference Equations (1994)
Sergei A. Abramov, Marko Petkovsek
D'Alembertian solutions of differential (resp. difference) equations are those expressible as nested indefinite integrals (resp. sums) of hyperexponential functions. They are a subclass of...
Finding All Hypergeometric Solutions of Linear Differential Equations (1993)
Marko Petkovsek, Sek Bruno Salvy, Bruno Salvy, Marko Petkovsek, Marko Petkovsek
Hypergeometric sequences are such that the quotient of two successive terms is a fixed rational function of the index. We give a generalization of M. Petkovsek's algorithm to find all...