Counting the number of partitions that are a distance d away from a fixed partition.

94 Views Asked by At

Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N f_i = N$, $f_i \in \mathbb{Z}^{\geq 0}$ for $1 \leq i \leq N$ and $f_i \geq f_{i+1}$ for all $1\leq i \leq N-1$. Given two partitions $\vec{f} \in Partitions(N)$ and $\vec{f}' \in Paritions(N)$ we define the distance between two partitions to be $$dist\left(\vec{f},\vec{f'} \right) = \sum_{i=1}^{N} \frac{1}{2} \left|f_i-f_i' \right| \ . $$ Intuitively, if we view each $f_i$ as a stack of $f_i$ individual blocks then the distance is the number of blocks we would need to move to change partition $\vec{f}$ into $\vec{f}'$. Given a positive integer $d \in \mathbb{Z}^{\geq 0}$ and a partition $\vec{f} \in Partitions(N)$ we let $$\mathcal{S}_{\vec{f}}\left(d\right) = \left\{\vec{f}' \in Partitions(N)~:~dist\left(\vec{f},\vec{f'}\right)=d \right\} \ .$$ I am particularly interested in understanding how $\left|\mathcal{S}_{\vec{f}}\left(d\right) \right|$ grows with $d$. I have seen a few asymptotic upper bounds on $\left|Partitions(N) \right|$. Are there any known asymptotic upper bounds for $\left|\mathcal{S}_{\vec{f}}\left(d\right) \right|$? Are there any known algorithms for computing $\left|\mathcal{S}_{\vec{f}}\left(d\right) \right|$ that run in polynomial time in $N$ and $d$?