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$?
5
-
$\begingroup$ "Intuitively, the distance is the number of elements we would need to move..." - I don't see how this is the case. Did you mean to say $d (a, b) = \sum_{i=1}^N (1-\delta_{a_i b_i}) $? $\endgroup$– MyridiumCommented Mar 3, 2015 at 19:29
-
$\begingroup$ Thanks for taking the time to read my question/comment. I am not sure that I fully understood your comment :-) What do you mean by $\delta_{a_ib_i}$? $\endgroup$– JeremiahCommented Mar 4, 2015 at 21:47
-
$\begingroup$ Sorry, $\delta_{a_i b_i}$ equals $1$ if $ a_i = b_i $, and equals $0$ otherwise. In other words, did you mean to say that the distance function was the number of entries in the two tuples that did not match? I don't understand the sentence: "...the distance is the number of elements we would need to move to change..." $\endgroup$– MyridiumCommented Mar 4, 2015 at 22:48
-
$\begingroup$ I am viewing a partition as a sequence of stacks of single blocks arranged in descending order. For example, if $\vec{f} = (10,5,5,0,...0) \in Partitions(20)$ then we would have a stack of 10 blocks next to two stacks of 5 blocks and a bunch of empty stacks. To create the partition $\vec{f}' = (9,5,4,2,0,...,0) \in Partitions(20)$ we would need to move two blocks (from the stacks of 10 and 5) to an empty stack. We have $dist\left(\vec{f},\vec{f}' \right) = \frac{\left|10-9\right| + \left|5-4\right| + \left|0-2\right|}{2} = 2 \ .$ $\endgroup$– JeremiahCommented Mar 5, 2015 at 16:25
-
$\begingroup$ Thanks for your comment. I edited the question to clarify this point. $\endgroup$– JeremiahCommented Mar 5, 2015 at 16:29
Add a comment
|