Solving recurrent relation

Question

I have the following recurrent relation and I want to find a close form of it if it exists at all.

$$ P_n = (1-p)^{n-1}P_{n-1} + \sum\limits_{k=2}^{n} \binom{n-1}{k-1} p^{\binom{k}{2}} (1-p)^{k(n-k)} P_{n-k} $$

Here $p$ is a constant in $[0;1]$, $P_0 =1$. It can be done with a little effort that $P_1 = 1$, $P_2 = p + 1 - p = 1$, $P_3 = 1 - 3p^2(1-p)$ and so on (it's getting messier after this step). I tried to write several first member and what I get is that $P_n = p^{\binom{n}{2}} + (1-p)^{\binom{n}{2}} + F(p)$ where $F(p)$ is a non-negative polynomial on $[0;1]$ with max power $\binom{n}{2}$.

So my questions are: 1) is it the linear recurrent relation for such that we usually build the characteristic polynomial and do the math like at school?

2) any known problems which involve such type of recursions (different size of sum for different $n$)?

3) any methodology how to approach it?

4) Maybe someone can solve it?

Thank you for your attention.

[edit]

After substituion $t = n - k$ the recursion takes form $$ P_n = \sum\limits_{t=0}^{n-1} \binom{n-1}{t} p^{\binom{n-t}{2}} (1-p)^{t(n-t)} P_t $$,

which is similar to Bell number recurrence.

[edit 2]

Special case for $p=1/2$ as suggested by Pietro Majer takes the form $$ P_n(\frac{1}{2}) = 2^{-\binom{n}{2}}\sum_{t=0}^{n-1} \binom{n-1}{t} 2^{\binom{t}{2}} P_t(\frac{1}{2}) $$ and leads to Bell number.

Answer 1

Here is a generating function approach. Note that the RHS is almost a convolution $\sum_{k=0}^n a_{k}b_{n-k}$, which suggests the use of generating functions, after some bricolage on the the recursion aimed to get a convolution form (whence a Cauchy product of power series).

To start with, note that the first term on the RHS may be naturally included in the sum for $k=1$. The binomial has already a suitable form; and then note the exponent of $(1-p)$: it can be written $k(n-k)= {n \choose 2}-{ n-k\choose 2} -{k\choose2} $, which suggests to multiply the relation by $ (1-p)^{-{n\choose 2}}{x^{n-1}\over(n-1)!}$ : $$(1-p)^{-{n\choose 2}}P_{n}{x^{n-1}\over (n-1)!}= p^{k\choose 2 }(1-p)^{-{k\choose2}}{x^{k-1}\over(k-1)!}\cdot (1-p)^{-{n-k\choose 2}} P_{n-k}{x^{n-k}\over (n-k)!} $$

If we introduce the generating functions

$$g(x)=g(x,p):=\sum_{n=1}^\infty \Big({p\over 1-p}\Big)^{n \choose 2 }{x^{n}\over n!}$$ $$f(x)=f(x,p):=\sum_{n=0}^\infty (1-p)^{-{n\choose2}}P_{n}{x^{n}\over n!} $$ the recurrence relations write $f'=g'f$, whence $$f(x)=\exp\Big( \sum_{n=1}^\infty \Big({p\over 1-p}\Big)^{n \choose 2 }{x^{n}\over n!}\Big).$$

Incidentally, for $p=1/2$ one has $g(x)=e^x-1$, and we obtain the special values $$P_n(1/2)=2^{-{n\choose 2}}B_n$$ where $B_n$ are the Bell numbers.

Given that in the above formula for $f(x)$ the variable $p$ only enters in the term ${p\over 1-p}$, we may express the polynomials $P_n$ as $$P_n(p )=(1-p)^{n\choose 2}Q_n\big({p\over1-p}\big)$$ where the sequence $Q_n(q)$ is defined correspondingly by the somehow simpler generating series $$F(x)=F(x,q)=\sum_{n=0}^\infty Q_{n}{x^{n}\over n!} := \exp G(x,q)$$ where $$G(x)=G(x,q)=g\Big(x,{q\over q+1}\Big) := \sum_{n=1}^\infty q^{n \choose 2 }{x^{n}\over n!} $$ is the power series solution to the linear delay differential equation $$G(0)=0$$ $$G'(x)=1+G(qx).$$ The first polynomials $Q_n$ are curiously similar to binomial expansions: $$Q_0=1 $$ $$Q_1=1 $$ $$Q_2=q + 1 $$ $$Q_3 = q^3+3q+1 $$ $$Q_4=q^6+4q^3+3q^2+6q+1 $$ $$Q_5=q^{10}+5q^6+10q^4+10q^3+15q^2+10q+1 $$ $$Q_6=q^{15}+6q^{10}+15q^7+25q^6+60q^4+35q^3+45q^2+15q+1 $$ $$Q_7=q^{21}+7q^{15}+21q^{11}+21q^{10}+35q^9+105q^7+105q^6+105q^5+210q^4+140q^3+105q^2+21q+1 $$