3
$\begingroup$

This question is related to one I asked previously.

Consider in sorted order all ${n + k - 1\choose k}$ ways of choosing $k$ integers from $\{0,n-1\}$ with repetitions. For example, if $n=5$ and $k=3$ we have:

(0, 0, 0),
(0, 0, 1),
(0, 0, 2),
(0, 0, 3),
(0, 0, 4),
(0, 1, 1),
[...]

Let us now regard each combination as a multi-subset of integers.

Looking at this list from top to bottom, I would like to group consecutive multi-subsets together in a greedy way so that the size of the intersection of all the multi-subsets in a grouping is at least $k-1$.

For $n = 5, k = 3$, the groupings would look as follows:

(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)
(0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)
(0, 2, 2), (0, 2, 3), (0, 2, 4)
(0, 3, 3), (0, 3, 4)
(0, 4, 4)
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4)]
(1, 2, 2), (1, 2, 3), (1, 2, 4)]
(1, 3, 3), (1, 3, 4)
(1, 4, 4)
(2, 2, 2), (2, 2, 3), (2, 2, 4)
(2, 3, 3), (2, 3, 4)
(2, 4, 4)
(3, 3, 3), (3, 3, 4)
(3, 4, 4), (4, 4, 4)

I am interested in the number of groupings you get by this greedy algorithm. We can see that for $n = 5, k = 3$ the number is $14$.

For $n = 4, k = 4$ I believe you get the following $17$ groupings.

(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)
(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)
(0, 0, 2, 2), (0, 0, 2, 3)
(0, 0, 3, 3)
(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)
(0, 1, 2, 2), (0, 1, 2, 3)
(0, 1, 3, 3)
(0, 2, 2, 2), (0, 2, 2, 3)
(0, 2, 3, 3), (0, 3, 3, 3)
(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)
(1, 1, 2, 2), (1, 1, 2, 3)
(1, 1, 3, 3)
(1, 2, 2, 2), (1, 2, 2, 3)
(1, 2, 3, 3), (1, 3, 3, 3)
(2, 2, 2, 2), (2, 2, 2, 3)
(2, 2, 3, 3), (2, 3, 3, 3)
(3, 3, 3, 3)

Is it possible to give an exact formula for this count for arbitrary positive integers $n> k$?


For $n = 2, 3, 4, 5$ I computed the answer for $k = 1,\dots 20$.

  • $n = 2$ gives 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11.

This is a simple sequence.

  • $n = 3$ gives 1, 3, 5, 8, 11, 15, 19, 24, 29, 35, 41, 48, 55, 63, 71, 80, 89, 99, 109, 120

This is this OEIS sequence. The interesting fact is that the differences between consecutive numbers is exactly the sequence for $n = 2$.

  • $n = 4$ gives $1, 4, 9, 17, 28, 43, 62, 86, 115, 150, 191, 239, 294, 357, 428, 508, 597, 696, 805, 925$. This is OEIS A005744.

Again the differences between consecutive numbers is exactly the sequence for $n = 3$.

  • $n = 5$ gives $1, 5, 14, 31, 59, 102, 164, 250, 365, 515, 706, 945, 1239, 1596, 2024, 2532, 3129, 3825, 4630, 5555$.

This is not in the OEIS but again the differences between consecutive numbers is exactly the sequence for $n = 4$.

$\endgroup$
1
+50
$\begingroup$

As with the previous question, the differences pattern that you've noted follows from the observation that the greedy algorithm's will never put $(0,n-1,n-1,\dots,n-1)$ and $(1,1,1,\dots,1)$ in the same group for $n>2$. As a result, we can separately figure out what the greedy algorithm does to the multi-subsets that start with $0$, and what it does to the multi-subsets that start with $1, 2, \dots, n$.

Let $m(n,k)$ be the number of multi-subset groupings the greedy algorithm gives us. Then for $n>2$ and $k>1$, we have:

  1. The multi-subsets starting with $0$ all agree on that first element. So if we ignore the leading $0$, we are dividing multi-subsets of size $k-1$ into groupings by the greedy algorithm, and we will get $m(n,k-1)$ groupings there.
  2. The rest of the multi-subsets do not include $0$ at all. So they only use the $n-1$ values from $\{1,2,\dots,n-1\}$, and we will get $m(n-1,k)$ groupings there.

So for $n>2$ and $k>1$, we have $m(n,k) = m(n,k-1) + m(n-1,k)$.

When $k=1$, we can put all the one-element multi-subsets into one grouping, so $m(n,1) = 1$.

When $n=2$, our multi-subsets are $\{00\dots00, 00\dots01, 00\dots11,\dots, 01\dots11, 11\dots11\}$. Each shares $k-1$ elements with the multi-subset following it in the lexicographic ordering, but only $k-2$ with the one after that, so all our groupings will be of size $2$, except possibly for the last multi-subset. There are $k+1$ multi-subsets, so $m(2, k) = \left\lceil\frac{k+1}{2}\right\rceil$.


So far, we've confirmed that the patterns in your calculations continue. The obstacle to finding a closed form for $m(n,k)$ is that the base case $\left\lceil\frac{k+1}{2}\right\rceil$ is very annoying to deal with.

We can find a formula for fixed $n$ that's nearly-polynomial in $k$ by observing that $\delta(n,k) = \frac{(-1)^k}{2^n}$ also satisfies the recurrence relation $$\delta(n,k) = \delta(n-1,k) + \delta(n,k-1)$$ and therefore $m(n,k) - \delta(n,k)$ does, too. We have $m(2,k) - \delta(2,k) = \frac{k}{2} + \frac34$, which is exactly linear in $k$, and from the formula $$m(n,k) - \delta(n,k) = m(n,1) -\delta(n,1) + \sum_{j=2}^k \bigl(m(n-1,j) - \delta(n-1,j)\bigr)$$ we can get a quadratic formula for $m(3,k) -\delta(3,k)$, a cubic formula for $m(4,k)-\delta(4,k)$, and so on.

We can find all of $m(n,k)$ in the OEIS by looking it up as the triangular table $$ \begin{matrix} 1 \\ 1 & 2 \\ 1 & 3 & 2 \\ 1 & 4 & 5 & 3 \\ 1 & 5 & 9 & 8 & 3 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix} $$ where the $j^{\text{th}}$ diagonal from the top is the sequence $m(j+1,k)$. (This is a useful trick when you have a sequence with two parameters.) Read by rows, this triangle is sequence A181971 in the OEIS, but there is no closed formula there either.

We can also find inequalities bounding $m(n,k)$ that let us at least derive the asymptotics.

  • If we define $m_-(n,k) = \frac12\binom{n+k-2}{k-1}$, then $m_-(n,1) = \frac12 \le m(n,1)$ and $m_-(2,k) = \frac k2 \le m(2,k)$. Also, $m_-(n,k) = m_-(n-1,k) + m_-(n,k-1)$, so we can inductively prove that $m_-(n,k) \le m(n,k)$ for all $k$.
  • If we define $m_+(n,k) =\binom{n+k-2}{k-1}$, then $m_+(n,1) = 1 \ge m(n,1)$ and $m_+(2,k) = k \ge m(2,k)$. Also, $m_+(n,k) = m_+(n-1,k) + m_+(n,k-1)$, so we can inductively prove that $m_+(n,k) \ge m(n,k)$ for all $k$.

Therefore we have $$\frac12 \binom{n+k-2}{k-1} \le m(n,k) \le \binom{n+k-2}{k-1}$$ for all $n \ge 2$ and $k \ge 1$, which lets us estimate $m(n,k)$ to within a factor of $2$.

$\endgroup$
  • $\begingroup$ Thank you. It's a shame it doesn't have such a pretty answer as last time. Are there nice asymptotics as you were able to show previously? $\endgroup$ – felipa Apr 21 '17 at 10:45
  • $\begingroup$ How about for fixed $k$ as $n \to \infty$? $\endgroup$ – felipa Apr 21 '17 at 18:00
  • 1
    $\begingroup$ Actually, I thought of a much better approach to approximate $m(n,k)$, which I've added to the answer. $\endgroup$ – Misha Lavrov Apr 21 '17 at 18:11
  • $\begingroup$ That's awesome! $\endgroup$ – felipa Apr 21 '17 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.