# 5 different ways to define the same family of integer sequences

• Let $${n \brace k}$$ be a Stirling number of the second kind.
• Let $$A_n(x)$$ be an Eulerian polynomial. Here $$A_n(x) = \sum_{i=0}^{n}i!{n \brace i}(x-1)^{n-i}.$$
• Let $$a_1(n,p,q)$$ be the family of integer sequences such that $$a_1(n,p,q) = \sum\limits_{i=0}^{n} (p-q)^{n-i}{n \brace i}\prod\limits_{j=0}^{i-1}(qj+1).$$
• Let $$a_2(n,p,q)$$ be the family of integer sequences such that exponential generating functions for it satisfy $$B(x) = \exp\left(\sum\limits_{n=1}^{\infty}p^{n-1}A_{n-1}\left(\frac{q}{p}\right)\frac{x^n}{n!}\right).$$
• Let $$R(n,m,p,q) = R(n-1,m+1,p,q) + p\sum\limits_{j=0}^{m}\binom{m+1}{j}q^{m-j}R(n-1,j,p,q), \\ R(0,m,p,q) = 1.$$
• Let $$a_3(n,p,q)$$ be the family of integer sequences such that $$a_3(n,p,q) = R(n-1, 0, p, q)$$ for $$n>0$$ with $$a_3(0,p,q)=1$$.
• Let $$a_4(n,p,q)$$ be the family of integer sequences such that ordinary generating functions for it are $$\frac{1}{G(0,x)}$$ where $$G(0,x)$$ are continued fractions such that $$G(j,x)=1-\cfrac{(qj+1)x}{1-\cfrac{p(j+1)x}{G(j+1,x)}}.$$ Note that $$G(0,x)=1-\cfrac{x}{1-\cfrac{px}{1-\cfrac{(q+1)x}{1-\cfrac{2px}{1-\cfrac{(2q+1)x}{1-\cfrac{3px}{1-\cfrac{(3q+1)x}{1-\cfrac{4px}{\ddots}}}}}}}}.$$
• Let $$T(n,k,p,q) = (q(k-1)+1)T(n-1,k,p,q) + p(n-k+1)T(n-1,k-1,p,q), \\ T(n,1,p,q) = [n > 0], \\ T(n,0,p,q) = T(0,k,p,q) = 0.$$ Here square bracket denotes Iverson bracket.
• Let $$a_5(n,p,q)$$ be the family of integer sequences such that $$a_5(n,p,q)=\sum\limits_{k=1}^{n}T(n,k,p,q)$$ for $$n>0$$ with $$a_5(0,p,q) = 1$$.

I conjecture that $$a_1(n,p,q) = a_2(n,p,q) = a_3(n,p,q) = a_4(n,p,q) = a_5(n,p,q).$$

Here is the PARI/GP program to check it numerically:

a(n,p,q) = sum(i=0, n, (p-q)^(n-i)*stirling(n, i, 2)*prod(j=0, i-1, (q*j+1)))
b(n,p,q) = p^n*sum(i=0, n, i!*stirling(n, i, 2)*(q/p-1)^(n-i))
G(n,p,q) = my(CF = 1); for(j=0, n, CF = 1 - (q*(n-j)+1)*x/(1 - p*(n-j+1)*x/CF) + x*O(x^n)); CF
F(n,p,q) = my(v1); v1 = Vec(1/G(n,p,q)); log(sum(i=0, n, v1[i+1]*x^i/i!) + x*O(x^n))
upto1(n,p,q) = my(v1); v1 = vector(n, i, a(i, p, q))
upto2(n,p,q) = Vec(1/G(n, p, q) - 1)
upto3(n,p,q) = my(v1); v1 = vector(n, i, 0); v1[1] = 1; v2 = v1; for(i=2, n, v1 = vector(n, j, if(j==1, 1, (q*(j-1)+1)*v1[j] + p*(i-j+1)*v1[j-1])); v2[i] = vecsum(v1)); v2
upto4(n,p,q) = my(v1, v2, v3); v1 = vector(n, i, 1); v2 = v1; v3 = vector(n, i, 0); v3[1] = 1; for(i=1, n-1, for(m=0, n-i-1, v2[m+1] = v1[m+2] + p*sum(j=0, m, binomial(m+1, j)*q^(m-j)*v1[j+1])); v1 = v2; v3[i+1] = v1[1]); v3
upto5(n,p,q) = my(v1); v1 = vector(n, i, b(i-1, p, q))
upto6(n,p,q) = my(v1); v1 = Vec(F(n,p,q)); v1 = vector(n, i, v1[i]*i!)
test1(n,p,q) = my(v1); v1 = upto1(n, p, q); v1 == upto2(n, p, q) && v1 == upto3(n, p, q) && v1 == upto4(n, p, q)
test2(n,p,q) = upto5(n,p,q) == upto6(n,p,q)

Is there a way to prove it?

Let's prove that $$a_3=a_1$$. Note that the recurrence for $$R$$ translates to the following PDE for the generating $$F(x,y):=\sum_{n,m\geq0} R(n,m,p,q) \frac{x^n}{n!}\frac{y^m}{m!}$$: $$\frac{\partial}{\partial x} F(x,y) = \frac{\partial}{\partial y} \bigg(F(x,y) + \frac{p}q(e^{qy} - 1)F(x,y)\bigg)$$ with the boundary condition $$F(0,y) = e^y$$. This PDE is well solvable in CAS like Maple, it can be easily verified that $$F(x,0)=\sum_{n\geq0} R(n,0,p,q) \frac{x^n}{n!}$$ does indeed coincide with the derivative of the e.g.f for $$a_1$$ given in Ira's answer. QED

Equality $$a_1 = a_4 = a_5$$ follows from the Salas and Sokal paper, see Theorem 3.1, formula (3.10) and Proposition 3.3 for $$(w,y,u,v)=(1,p,q,p)$$.

ADDED. Here are the requested details of computation. It turns out that while Maple solves our PDE, it is not so good at simplifying symbolic radicals (or I'm not familiar with the best practice here) in the solution. So, I will use a combination of Maple and Sage for solving the PDE and simplifying the result, respectively:

sage: S = maple('simplify(subs(y=0, rhs( pdsolve( [ diff(F(x,y),x)=diff(F(x,y) + p/q * (exp(q*y)-1)*F(x,y), y), F(0,y) = exp(y) ], F(x,y) ) ) ))').sage()
sage: p,q,x = S.variables()
-1
q + 1                    ---
-----                     q
q   /     q*x      p*x\     x*(p + 1)
(-p + q)     *\- p*e    + q*e   /   *e
-----------------------------------------------
q     p - 2*q
----- + -------
q*x    p - q    p - q   p*x
- p*e    + q               *e

-1
q + 1                    ---
-----                     q
q   /     q*x      p*x\     x*(p + 1)
(-p + q)     *\- p*e    + q*e   /   *e
-----------------------------------------------
q*x      p*x
- p*e    + q*e

Sage just left us with noticing that $$\frac{q}{p-q}+\frac{p-2q}{p-q}=1$$ to conclude equality of the two expressions.

• Thank you for answer! Could you add the details of the calculations performed in Maple? Also thank you for reference. Please see proposition 3.3. Could you add this result to your answer? Commented Aug 2 at 7:51
• @Notamathematician: I've updated my answer as requested. Commented Aug 2 at 13:05
• Thank you very much again! I completely agree that proposition 3.3 gives $a_1=a_4$. Could you point out where it is shown that $a_4=a_5$? Commented Aug 2 at 13:10
• @Notamathematician: Let $T'(n,k):=T(n,k+1)$ so that $T'(n,k) = (qk-1)T'(n-1,k) + p(n-k)T'(n-1,k-1)$, which is a subject to Theorem 3.1 case F1b. Commented Aug 2 at 14:08
• @Notamathematician: Yes, there is a typo - it should be $qk+1$. Commented Aug 3 at 10:15

Here is a proof that $$a_1(n, p, q) = a_2(n,p,q)$$.

The generating function for the Stirling numbers of the second kind is $$\sum_{n=i}^\infty {n\brace i}\frac{x^n}{n!}= \frac{(e^x-1)^i}{i!}.$$ Also $$\prod_{j=0}^{i-1}(qj+1) = q^i i!\,\binom{1/q+i-1}{i}.$$ So \begin{align*} \sum_{n=0}^\infty a_1(n,p,q) \frac{x^n}{n!} &=\sum_{i=0}^\infty \left( q\over p-q\right)^i (e^{x(p-q)} -1)^i\binom{1/q +i-1}{i}\\ &=\left( 1-\displaystyle\frac{q}{p-q} (e^{x(p-q)}-1)\right)^{-1/q}\\ &=\left(\frac{p-q}{p-qe^{x(p-q)}}\right)^{1/q}. \end{align*}

The generating function for the Eulerian polynomials is $$\sum_{n=0}^\infty A_n(t) \frac{x^n}{n!} = \frac{1-t}{e^{(t-1)x-t}}.$$ Integrating with respect to $$x$$ gives \begin{align*} \sum_{n=1}^\infty A_{n-1}(t) \frac{x^n}{n!} &= \frac{1}{t}\left[ \log\left(1-t\over e^{(t-1)x} -t\right) +(t-1)x\right]\\ &=\frac{1}{t}\log\left( 1-t \over 1-te^{(1-t)x}\right). \end{align*} Thus \begin{align*} \log B(x) &= \sum_{n=1}^\infty p^{n-1}A_{n-1}\left(q\over p\right)\frac{x^n}{n!}\\ &=\frac{1}{q}\log\left( 1-q/p\over 1-(q/p) e^{(1-q/p)px} \right)\\ &=\frac{1}{q}\log\left(p-q\over p-q e^{(p-q)x} \right), \end{align*} so $$B(x) = \left(\frac{p-q}{p-qe^{x(p-q)}}\right)^{1/q} =\sum_{n=0}^\infty a_1(n,p,q) \frac{x^n}{n!}.$$