On the Generating Functions enumerating walks confined to the Non-Negative H\
alf Line
With step-sets that are subsets of , {-2, -1, 0, 1, 2}
By Shalosh B. Ekhad
It is well known, and not too hard to see, that the generating function
enumerating walks confined to the non-negative half-line with ANY given step\
-set
is always algebraic. This is true for both the total number and for the walk\
s
that end-up at a specific location.
In this article we will state and sketch proofs, of the algebraic equations \
satisfied by generating functions
that enumerate walks where the step-sets are subsets of
{-2, -1, 0, 1, 2}
that have at least one positive and at least one negative step.
-----------------------------------------------------------
Doing the set, {-2, 1}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, 1}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, 1}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
3 3
1 - P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, 1}, with n steps and ending at m, and let f(t,\
x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2 4 3
P[1](t) - t - 2 t P[1](t) + t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t) - P[1](t) x)
f(t, x) = 1 + --------------------------------- + t x f(t, x)
2
x
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x
f(t, x) = -----------------------------
3 2
t + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
3 3
1 - Q[0](t) + t Q[0](t) = 0
2 2 4 3
Q[1](t) - t - 2 t Q[1](t) + t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x
g(t, x) = -----------------------------
3 2
t + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 3 t) R(t) + t (-2 + 3 t) R(t) + t (-1 + 2 t) R(t) = 0
This ends this article that took, 1.681, seconds to produce.
-----------------------------------------------------------
Doing the set, {-2, 0, 1}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, 0, 1}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, 0, 1}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
3 3
1 + (-1 + t) P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, 0, 1}, with n steps and ending at m, and let f\
(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2 2 4 3
-t + (-1 + t) P[1](t) + 2 t (-1 + t) P[1](t) + t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t) - P[1](t) x)
f(t, x) = 1 + --------------------------------- + t f(t, x) + t x f(t, x)
2
x
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x
f(t, x) = -----------------------------
2 3 2
t + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
3 3
1 + (-1 + t) Q[0](t) + t Q[0](t) = 0
2 2 2 4 3
-t + (-1 + t) Q[1](t) + 2 t (-1 + t) Q[1](t) + t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x
g(t, x) = -----------------------------
2 3 2
t + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 4 t) R(t) + t (-2 + 5 t) R(t) + t (-1 + 3 t) R(t) = 0
This ends this article that took, 1.903, seconds to produce.
-----------------------------------------------------------
Doing the set, {-1, 1}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-1, 1}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-1, 1}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2
1 - P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-1, 1}, with n steps and ending at m, and let f(t,\
x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t))
f(t, x) = 1 + --------------------- + t x f(t, x)
x
Equivalently, solving for f(t,x)
-x + t P[0](t)
f(t, x) = --------------
2
t + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
We will go backwards!,
Define Q[0](t) to be the unique formal power series satisfying the algebraic\
equation claimed in the theorem for P[0](t)
2 2
1 - Q[0](t) + t Q[0](t) = 0
and define g(t,x) by
-x + t Q[0](t)
g(t, x) = --------------
2
t + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2
1 + (-1 + 2 t) R(t) + t (-1 + 2 t) R(t) = 0
This ends this article that took, 0.575, seconds to produce.
-----------------------------------------------------------
Doing the set, {-1, 0, 1}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-1, 0, 1}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-1, 0, 1}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2
1 + (-1 + t) P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-1, 0, 1}, with n steps and ending at m, and let f\
(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t))
f(t, x) = 1 + --------------------- + t f(t, x) + t x f(t, x)
x
Equivalently, solving for f(t,x)
-x + t P[0](t)
f(t, x) = ------------------
2
t + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
We will go backwards!,
Define Q[0](t) to be the unique formal power series satisfying the algebraic\
equation claimed in the theorem for P[0](t)
2 2
1 + (-1 + t) Q[0](t) + t Q[0](t) = 0
and define g(t,x) by
-x + t Q[0](t)
g(t, x) = ------------------
2
t + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2
1 + (-1 + 3 t) R(t) + t (-1 + 3 t) R(t) = 0
This ends this article that took, 0.199, seconds to produce.
-----------------------------------------------------------
Doing the set, {-2, -1, 1}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, -1, 1}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, -1, 1}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 3 3
1 - P[0](t) + t P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, -1, 1}, with n steps and ending at m, and let \
f(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2 2 4 3
-t + (1 - 2 t ) P[1](t) - t (2 + t) P[1](t) + t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
f(t, x) =
t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t))
1 + --------------------------------- + --------------------- + t x f(t, x)
2 x
x
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x + t P[0](t) x
f(t, x) = -------------------------------------------
3 2
t + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
2 2 3 3
1 - Q[0](t) + t Q[0](t) + t Q[0](t) = 0
2 2 2 4 3
-t + (1 - 2 t ) Q[1](t) - t (2 + t) Q[1](t) + t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x
g(t, x) = -------------------------------------------
3 2
t + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 3 t) R(t) + 2 t (-1 + 2 t) R(t) + t (-1 + 3 t) R(t) = 0
This ends this article that took, 1.776, seconds to produce.
-----------------------------------------------------------
Doing the set, {-2, -1, 0, 1}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, -1, 0, 1}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, -1, 0, 1}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 3 3
1 + (-1 + t) P[0](t) + t P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, -1, 0, 1}, with n steps and ending at m, and l\
et f(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2 2 4 3
-t + (1 - 2 t - t ) P[1](t) + t (-2 + t) P[1](t) + t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t))
f(t, x) = 1 + --------------------------------- + ---------------------
2 x
x
+ t f(t, x) + t x f(t, x)
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x + t P[0](t) x
f(t, x) = -------------------------------------------
2 3 2
t + t x + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
2 2 3 3
1 + (-1 + t) Q[0](t) + t Q[0](t) + t Q[0](t) = 0
2 2 2 4 3
-t + (1 - 2 t - t ) Q[1](t) + t (-2 + t) Q[1](t) + t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x
g(t, x) = -------------------------------------------
2 3 2
t + t x + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 4 t) R(t) + 2 t (-1 + 3 t) R(t) + t (-1 + 4 t) R(t) = 0
This ends this article that took, 2.260, seconds to produce.
-----------------------------------------------------------
Doing the set, {-1, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-1, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-1, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
3 3
1 - P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-1, 2}, with n steps and ending at m, and let f(t,\
x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t)) 2
f(t, x) = 1 + --------------------- + t x f(t, x)
x
Equivalently, solving for f(t,x)
-x + t P[0](t)
f(t, x) = --------------
3
t + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
We will go backwards!,
Define Q[0](t) to be the unique formal power series satisfying the algebraic\
equation claimed in the theorem for P[0](t)
3 3
1 - Q[0](t) + t Q[0](t) = 0
and define g(t,x) by
-x + t Q[0](t)
g(t, x) = --------------
3
t + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 3 t) R(t) + 3 t (-1 + 2 t) R(t) + t (-1 + 2 t) R(t) = 0
This ends this article that took, 0.841, seconds to produce.
-----------------------------------------------------------
Doing the set, {-1, 0, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-1, 0, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-1, 0, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
3 3
1 + (-1 + t) P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-1, 0, 2}, with n steps and ending at m, and let f\
(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t)) 2
f(t, x) = 1 + --------------------- + t f(t, x) + t x f(t, x)
x
Equivalently, solving for f(t,x)
-x + t P[0](t)
f(t, x) = ------------------
3
t + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
We will go backwards!,
Define Q[0](t) to be the unique formal power series satisfying the algebraic\
equation claimed in the theorem for P[0](t)
3 3
1 + (-1 + t) Q[0](t) + t Q[0](t) = 0
and define g(t,x) by
-x + t Q[0](t)
g(t, x) = ------------------
3
t + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 4 t) R(t) + 3 t (-1 + 3 t) R(t) + t (-1 + 3 t) R(t) = 0
This ends this article that took, 1.323, seconds to produce.
-----------------------------------------------------------
Doing the set, {-2, -1, 2}
-----------------------------------------------------------
Doing the set, {-2, -1, 0, 2}
-----------------------------------------------------------
Doing the set, {-2, 1, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, 1, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, 1, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 2 3 4 4 4 5
1 - P[0](t) - t P[0](t) + t (2 + t) P[0](t) - t P[0](t) - t P[0](t)
6 6
+ t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, 1, 2}, with n steps and ending at m, and let f\
(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2
-t - (-1 + 2 t) (2 t + 1) P[1](t) - t (2 t + 4 t - 1) P[1](t)
3 3 4 4 6 5
+ t (-4 + t) P[1](t) + t (-2 + 3 t) P[1](t) + 3 t P[1](t)
7 6
+ t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t) - P[1](t) x) 2
f(t, x) = 1 + --------------------------------- + t x f(t, x) + t x f(t, x)
2
x
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x
f(t, x) = -----------------------------
3 4 2
t + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
2 2 2 3 4 4 4 5
1 - Q[0](t) - t Q[0](t) + t (2 + t) Q[0](t) - t Q[0](t) - t Q[0](t)
6 6
+ t Q[0](t) = 0
2 2
-t - (-1 + 2 t) (2 t + 1) Q[1](t) - t (2 t + 4 t - 1) Q[1](t)
3 3 4 4 6 5
+ t (-4 + t) Q[1](t) + t (-2 + 3 t) Q[1](t) + 3 t Q[1](t)
7 6
+ t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x
g(t, x) = -----------------------------
3 4 2
t + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 9 t) R(t) + t (-9 + 32 t) R(t) + t (70 t + 2 - 29 t) R(t)
2 4 2 2 5
+ t (-9 + 32 t) (-1 + 3 t) R(t) + t (-1 + 9 t) (-1 + 3 t) R(t)
3 3 6
+ t (-1 + 3 t) R(t) = 0
This ends this article that took, 225.883, seconds to produce.
-----------------------------------------------------------
Doing the set, {-2, 0, 1, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, 0, 1, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, 0, 1, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 2 3 4 4
1 + (-1 + t) P[0](t) - t P[0](t) - t (-2 + t) P[0](t) - t P[0](t)
4 5 6 6
+ t (-1 + t) P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, 0, 1, 2}, with n steps and ending at m, and le\
t f(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2
-t - (t + 1) (-1 + 3 t) P[1](t) - t (4 t + t - 1) P[1](t)
3 3 4 4 6 5
+ t (-4 + 5 t) P[1](t) + t (-2 + 5 t) P[1](t) + 3 t P[1](t)
7 6
+ t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t) - P[1](t) x)
f(t, x) = 1 + --------------------------------- + t f(t, x) + t x f(t, x)
2
x
2
+ t x f(t, x)
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x
f(t, x) = -----------------------------
2 3 4 2
t + t x + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
2 2 2 3 4 4
1 + (-1 + t) Q[0](t) - t Q[0](t) - t (-2 + t) Q[0](t) - t Q[0](t)
4 5 6 6
+ t (-1 + t) Q[0](t) + t Q[0](t) = 0
2 2
-t - (t + 1) (-1 + 3 t) Q[1](t) - t (4 t + t - 1) Q[1](t)
3 3 4 4 6 5
+ t (-4 + 5 t) Q[1](t) + t (-2 + 5 t) Q[1](t) + 3 t Q[1](t)
7 6
+ t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x
g(t, x) = -----------------------------
2 3 4 2
t + t x + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (10 t - 1) R(t) + t (-9 + 41 t) R(t) + t (101 t + 2 - 33 t) R(t)
2 4 2 2 5
+ t (-9 + 41 t) (-1 + 4 t) R(t) + t (10 t - 1) (-1 + 4 t) R(t)
3 3 6
+ t (-1 + 4 t) R(t) = 0
This ends this article that took, 227.023, seconds to produce.
-----------------------------------------------------------
Doing the set, {-1, 1, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-1, 1, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-1, 1, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 3 3
1 - P[0](t) + t P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-1, 1, 2}, with n steps and ending at m, and let f\
(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t)) 2
f(t, x) = 1 + --------------------- + t x f(t, x) + t x f(t, x)
x
Equivalently, solving for f(t,x)
-x + t P[0](t)
f(t, x) = -------------------
2 3
t + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
We will go backwards!,
Define Q[0](t) to be the unique formal power series satisfying the algebraic\
equation claimed in the theorem for P[0](t)
2 2 3 3
1 - Q[0](t) + t Q[0](t) + t Q[0](t) = 0
and define g(t,x) by
-x + t Q[0](t)
g(t, x) = -------------------
2 3
t + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 5 t) R(t) + 4 t (-1 + 3 t) R(t) + t (-1 + 3 t) R(t) = 0
This ends this article that took, 1.060, seconds to produce.
-----------------------------------------------------------
Doing the set, {-1, 0, 1, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-1, 0, 1, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-1, 0, 1, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 3 3
1 + (-1 + t) P[0](t) + t P[0](t) + t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-1, 0, 1, 2}, with n steps and ending at m, and le\
t f(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t)) 2
f(t, x) = 1 + --------------------- + t f(t, x) + t x f(t, x) + t x f(t, x)
x
Equivalently, solving for f(t,x)
-x + t P[0](t)
f(t, x) = -------------------------
2 3
t + t x + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
We will go backwards!,
Define Q[0](t) to be the unique formal power series satisfying the algebraic\
equation claimed in the theorem for P[0](t)
2 2 3 3
1 + (-1 + t) Q[0](t) + t Q[0](t) + t Q[0](t) = 0
and define g(t,x) by
-x + t Q[0](t)
g(t, x) = -------------------------
2 3
t + t x + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 6 t) R(t) + 4 t (-1 + 4 t) R(t) + t (-1 + 4 t) R(t) = 0
This ends this article that took, 1.275, seconds to produce.
-----------------------------------------------------------
Doing the set, {-2, -1, 1, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, -1, 1, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, -1, 1, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 3
1 + (-1 - 2 t) P[0](t) + t (2 + 3 t) P[0](t) - t (2 t + 1) P[0](t)
4 4
+ t P[0](t) = 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, -1, 1, 2}, with n steps and ending at m, and l\
et f(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2 2 3 3
t + (-1 + 4 t + t) P[1](t) + 2 t (1 + 3 t) P[1](t) + t (1 + 4 t) P[1](t)
5 4
+ t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t))
f(t, x) = 1 + --------------------------------- + ---------------------
2 x
x
2
+ t x f(t, x) + t x f(t, x)
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x + t P[0](t) x
f(t, x) = -------------------------------------------
3 4 2
t + t x + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
2 2 3
1 + (-1 - 2 t) Q[0](t) + t (2 + 3 t) Q[0](t) - t (2 t + 1) Q[0](t)
4 4
+ t Q[0](t) = 0
2 2 2 3 3
t + (-1 + 4 t + t) Q[1](t) + 2 t (1 + 3 t) Q[1](t) + t (1 + 4 t) Q[1](t)
5 4
+ t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x
g(t, x) = -------------------------------------------
3 4 2
t + t x + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 4 t) R(t) + 3 t (-1 + 4 t) R(t) + t (-1 + 4 t) R(t)
2 2 4
+ t (-1 + 4 t) R(t) = 0
This ends this article that took, 11.014, seconds to produce.
-----------------------------------------------------------
Doing the set, {-2, -1, 0, 1, 2}
On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\
om the Set, {-2, -1, 0, 1, 2}
By Shalosh B. Ekhad
Theorem: Let a(n) be the number of walks on the non-negative integers starti\
ng at 0, ending at 0, and always
staying in the non-negative integers, where a fundamental step is one of the\
members of set , {-2, -1, 0, 1, 2}
Let P[0](t) be the ordinary generating function of the sequence a(n)
infinity
-----
\ n
P[0](t) = ) a(n) t
/
-----
n = 0
Then P[0](t) satisfies the following algebraic equation
2 2 3 4 4
1 + (-1 - t) P[0](t) + t (2 + t) P[0](t) - t (t + 1) P[0](t) + t P[0](t)
= 0
Sketch of Proof:
We need to consider ALL walks with n steps that stay in the non-negative int\
egers. Let A(n,m) be the number of such walks
still using the step-set, {-2, -1, 0, 1, 2}, with n steps and ending at m, an\
d let f(t,x) be the bivariate generating function
infinity /infinity \
----- | ----- |
\ | \ n m|
f(t, x) = ) | ) A(n, m) t x |
/ | / |
----- | ----- |
m = 0 \ n = 0 /
Note that a(n)=A(n,0).
In order to prove our theorem, we need to establish at the same time the fol\
lowing results
----------------------------------------------------------------------------\
-------------------
Fact Number, 1
Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1)
infinity
-----
\ n
P[1](t) = ) A(n, 1) t
/
-----
n = 0
Then , P[1](t), satisfies the following algebraic equation
2 2 2 3 3
t + (3 t + 2 t - 1) P[1](t) + 2 t (2 t + 1) P[1](t) + t (1 + 3 t) P[1](t)
5 4
+ t P[1](t) = 0
----------------------------------------------------------------------------\
-------------------
----------------------------------------
The bivariate generating functions f(t,x) obviously satisfies the functional\
equation
t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t))
f(t, x) = 1 + --------------------------------- + ---------------------
2 x
x
2
+ t f(t, x) + t x f(t, x) + t x f(t, x)
Equivalently, solving for f(t,x)
2
-x + t P[0](t) + t P[1](t) x + t P[0](t) x
f(t, x) = -------------------------------------------
2 3 4 2
t + t x + t x + t x + t x - x
This functional equation uniquely determines f(t,x) and we have to prove tha\
t P[0](t)=f(t,0) satisfies the algebraic equation
of the theorem,
and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1,
satisfy the algebaric equations in the Facts
We will go backwards!,
Define Q[i](t) for i from 0 to, 1,
to be the unique formal power series satisfying
the algebraic equation of the Theorem and the, 1, facts. In other words
2 2 3 4 4
1 + (-1 - t) Q[0](t) + t (2 + t) Q[0](t) - t (t + 1) Q[0](t) + t Q[0](t)
= 0
2 2 2 3 3
t + (3 t + 2 t - 1) Q[1](t) + 2 t (2 t + 1) Q[1](t) + t (1 + 3 t) Q[1](t)
5 4
+ t Q[1](t) = 0
and define g(t,x) by
2
-x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x
g(t, x) = -------------------------------------------
2 3 4 2
t + t x + t x + t x + t x - x
It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\
by g(t,x)
then it is routine to check that it has a unique formal power series in t wi\
th coefficients that are polynomials in x
it is also routine to check that g(t,0) satisfies the same algebraic equatio\
n as in theorem
it is also routine to check that the coefficient of x^i of g(t,x), satisfies\
the algebraic equations for P[i](t) and Q[i](t)
for i from 1 to, 1
Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\
routine calculation in the Schutzenberger ansatz
hence it suffices to check it for sufficiently many initial terms. But we al\
ready did that!
It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\
QED!
As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0,
we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\
s that never go negative, regardless of destination
satisfies the algebraic equation
2 2 3
1 + (-1 + 5 t) R(t) + 3 t (-1 + 5 t) R(t) + t (-1 + 5 t) R(t)
2 2 4
+ t (-1 + 5 t) R(t) = 0
This ends this article that took, 7.657, seconds to produce.
This ends this webbook that took, 2315.895, to generate
-------------------------------------------------------------