# Generating function for number of distinct coordinates in integer lattice.

I'm looking for the value of the generating function $$f_{k, n}(x) = \sum_{y \in [n]^k}{x^{\# \text{distinct coordinates of y}}} = \sum_i{a^{(k, n)}_ix^i}$$

For example, for $$k = 1$$, we have $$f_{1, n}(x) = nx,$$ and for $$k = 2$$, we have $$f_{2, n}(x) = n(n-1)x^2 + nx$$. I know that $$a_i^{(k+1, n)} = ia_i^{(k, n)} + (n - i + 1)a_{i - 1}^{(k, n)}.$$

Are there any closed formulas for the coefficients $$a_i^{(k, n)}$$, or any tight bounds on them in terms of n? I'm interested primarily in the case where n grows large and k is constant.

Thanks!

It appears that $$a_i^{(k,n)}=S(k,i)(n)_i$$, where $$S(k,i)$$ are the Stirling numbers of the second kind and $$(n)_i=n(n-1)\cdots(n-i+1)$$ is the falling factorial. I'm sure this would be a relatively easy induction exercise.
• I believe it's $a_i^{(k,n)} = S(k,i)(n)_i$ (not $(n)_k$). – mfjones Apr 30 at 22:10