Designing a kernel function for generating functions

138 Views Asked by At

I was thinking about a question from project Euler the other day, and one of the lines of thought I had seemed mathematically interesting, but I wasn't entirely sure how to make my potential technique work, and I was curious if anybody had seen anything similar, or if they knew a decent way of making it work. Again, the question is about the technique, not the project Euler question.

Roughly speaking, my question is, given functions $f_{ab}(t)$ for all $(a,b)\in \mathbb N^2$, how can we design an integral transform $T$ such that $T(x^ay^b)=f_{ab}(t)$? For context, below is a problem where I would like to use the idea.

Setup: Let $\alpha_1,\ldots, \alpha_n \in \mathbb N$, define a partial ordering on $\mathbb N^n$ by $(a_1,\ldots, a_n)\leq (b_1,\ldots b_n)$ iff $a_i \leq b_i$ for all $i$. We wish to calculate the number of sequences of vectors $v_i\in \mathbb N^n$ such that $0=v_0<v_1<\cdots <c_k = (\alpha_1,\ldots, \alpha_n)$. Call such a sequence a valid sequence of length $k$, and let $A_k(\alpha_1,\ldots, \alpha_n)$ be the number of such sequences.

Approach: If we wish to approach the problem by induction on $n$, we have a small difficulty that at each point in a valid sequence, we can have an increase in some of the first $n$ coordinates, or we can have an increase in the $(n+1)$st coordinate, or both. This gives rise to a somewhat involved recurrence relation.

We can package this information using generating functions. Let $f_{(\alpha_1,\ldots,\alpha_n)}(t)=\sum A_k(\alpha_1,\ldots,\alpha_n) t^k$. Then $$f_{(\alpha_1,\ldots,\alpha_n,\alpha_{n+1})}(t)=T(f_{(\alpha_1,\ldots,\alpha_n)}(x)f_{(\alpha_{n+1})}(y))$$

where $T$ is the $\mathbb R$-linear function such that $T(x^ay^b)=f_{ab}(t)=\sum f(a,b,c)t^{a+b-c}$ where $f(a,b,c)=\frac{a+b-c}{(a-c)!(b-c)!c!}$ if $0\leq c \leq \min(a,b)$ and $0$ otherwise.

Hope: If the map $T$ can be given in a form that can be computed without knowing the Taylor expansion of the input function, then we have a simple, inductive method to compute our generating functions, and hence to count valid sequences. The only idea I have for such a computable transformation is integrating against an as yet unknown kernel function, e.g.,

$$T(f(x,y))(t)=\iint f(x,y)K(x,y,t)dxdy.$$

Questions: How would one find such a kernel function? Are there other types of explicit transforms that might work better? Has this idea been used before? Is there a reference for it?