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$?

 A: 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$.
