I want to find a general solution for a problem. I explain the problem with an example.
$\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of size $M \times K$ from $A$, where $K<M<N$. Then, for a given $K, M$ and $N$, the total number of possible sub-matrices that can be chosen from $A$ is $\binom{N}{K}$. The question is: out of the total number of sub-matrices how many sub matrices have one common column? How many sub-matrices have two common columns, three common columns and so on to $K-1$ common columns? Let us say $m=0,1,2,\cdots,K-1$ as number of common columns.
$\underline{Example}:$ Consider a matrix $A$ of size $3 \times 6$. Thus, $N=6, M=3$ and let $K=3$. That is, we take $3 \times 3$ sub matrices from $A$. The total number of sub matrices is $\binom{6}{3}=20$. Here, $m=0,1,2$.
$\underline{Case: m=0}.$ No overlapping columns. There are only $\lfloor{\frac{N}{K}}\rfloor=\lfloor{\frac{6}{3}}\rfloor=2$ possibilities. Two examples of (column) indices of the possible sub matrices are $(1,2,3)$ and $(4,5 ,6)$, $(1,3,5)$ and $(2,4,6)$ .
$\underline{Case: m=2}.$ Two overlapping columns. The (column) indices of the possible sub matrices with two overlapping columns are $(1,2,3),(1,2,4), (1,2,5),(1,2,6)$ (with 1 and 2 as the common columns) .$(1,3,4),(1,3,5),(1,3,6)$ (with 1 and 3 as common columns). $(1,4,5), (1,4,6)$(with 1 and 4 as common columns).$(1,5,6),(2,5,6),(3,5,6),(4,5,6)$ (with columns 5 and 6 as common), $(2,3,4),(2,3,5),2,3,6)$ (with 2 and 3 as common), $(2,4,5),(2,4,6)$ (with 2 and 4 as common) and finally $(3,4,5), (3,4,6)$ (with 3 and 4 as common). So there are totally 20 possible sub matrices.
(end of example)
For a general $N,M$ and $K$, how to compute the number of columns that are common?