# Number of subsets of combinations using a greedy algorithm

This question is related to one I asked previously.

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

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


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

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

So starting from the top I collect $\{(0, 1, 2), (0, 1, 3),(0, 1, 4)\}$ together as their intersection has size $k - 1 = 2$. I then need to start a new grouping and collect $\{(0, 2, 3),(0, 2, 4)\}$, then afterwards $\{(0,3,4)\}$ on its own in a grouping and so on. In this case I end up with $5$ groupings.

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

• Just to clarify & so I understand the question ... let $A_{1}, \cdots ,A_{\binom{n}{k}}$ be the list of subset of subset of ${0,\cdots ,(n-1)}$ of cardinality $k$. Now you want to partition this set into $m$ parts of differing sizes. $\{\{A_{a_{1,1}}, \cdots , A_{a_{1,s_1}}\},\{A_{a_{2,1}}, \cdots , A_{a_{2,s_2}}\}, \cdots ,\{A_{a_{m,1}}, \cdots , A_{a_{m,s_m}}\}\}$ so that $\mid \cap_{j=1}^{s_i} A_{a_{i,j}} \mid =k-1$ for $i=1, \cdots , m$ ... is this right ? – Donald Splutterwit Apr 8 '17 at 10:34
• @DonaldSplutterwit Yes except that it has to be $\geq k-1$ as a subset on its own will have size $k$ . In this question we are just applying the greedy algorithm to do this partitioning to the subsets in sorted order. – felipa Apr 8 '17 at 10:56

If $n>k+1$, then the last combination containing $0$ is not going to have overlap $k-1$ with the first combination not containing $0$. (In your example, $(0,3,4)$ and $(1,2,3)$ do not have overlap $k-1$.)

So we will greedily choose a partition of the combinations containing $0$, and then greedily choose a partition of the combinations not containing $0$, and these two steps will not interact in any way.

When $n=k+1$, and $k>1$, we will start by choosing a group of combinations containing $(1,2,\dots,k-1)$. All of them will be part of that group except the last element, so we get two groups.

Let $g(n,k)$ be the size of the partition we get. We have $g(n,n-1)=2$; also, $g(n,1) = 1$ because in that case, we can put everything into one partition. The recursive argument above tells us that when $n>k>0$, $g(n,k) = g(n-1,k-1) + g(n-1,k)$, as:

• When working with combinations containing $0$, the element $0$ is going to be in all of them, so we are really looking for overlap $k-2$ in their last $k-1$ elements.
• With the other combinations, it's as though $0$ was never an element to begin with.

These imply some sort of binomial solution; in fact, any linear combination of binomial coefficients will satisfy the recurrence, so we just have to find one that satisfies the base cases. I claim that $$g(n,k) = \binom{n-2}{k-1} + \binom{n-3}{k-2}$$ works: we can check that $g(n,1) = \binom{n-2}{0} = 1$ and $g(n,n-1) = \binom{n-2}{n-2} + \binom{n-3}{n-3} = 2$ for all $n$.

• As a side note, I originally misunderstood the problem to mean that in any group, any two sets must share $k-1$ elements, but the whole group doesn't need to (so $\{(1,2), (1,3), (2,3)\}$ is valid). In that case, $g(n,k) = \binom{n-2}{k-1}$ is the solution. – Misha Lavrov Apr 8 '17 at 17:35
• This is great, thank you. We know that this answer has to be bigger than $t(k,k-1) \binom{n}{k-1}$ in your answer to math.stackexchange.com/questions/2222441/…. Is it obvious why this should be the case? – felipa Apr 9 '17 at 9:04
• Only asymptotically, and asymptotically $g(n,k) \sim \binom{n}{k-1}$ as $n\to\infty$. – Misha Lavrov Apr 9 '17 at 14:33
• Thank you again. Is it simple to show that $\binom{n-2}{k-1} + \binom{n-3}{k-2} \sim {n \choose k-1}$ as $n \to \infty$? – felipa Apr 9 '17 at 14:54
• We can ignore the lower-order term $\binom{n-3}{k-2}$, and $\binom{n-2}{k-1} \sim \binom{n}{k-1}$ because they are both degree $k-1$ polynomials in $n$ with leading term $\frac1{(k-1)!}$. – Misha Lavrov Apr 9 '17 at 14:57