I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.



Number of bases of a matroid
With the problem as stated, the answer is $n-k+1$. Take the uniform matroid of rank $1$ on $n-k+1$ elements and direct sum with $k-1$ co-loops. (Geometrically, take the standard basis $e\_1$, $e\_2$, ..., $e\_k$ of $\mathbb{R}^k$ and duplicate the first basis element $n-k+1$ times.)


To see that this is optimal, suppose for the sake of contradiction that we could achieve $n-k$ bases: $B\_1$, $B\_2$, ..., $B\_{n-k}$. Consider the exchange graph, where $B\_i$ and $B\_j$ are connected by an edge if $\#(B\_i \setminus B\_j)= \#(B\_j \setminus B\_i) = 1$. It is known to be connected. Reorder the $B\_i$ such that the induced subgraph on $B\_1$, $B\_2$, ..., $B\_r$ is connected. Then, for $2 \leq r \leq n-k$, there is at most one element of $B\_r$ not in $\bigcup\_{1 \leq i<r} B\_i$. We deduce that $\# \bigcup\_{1 \leq i \leq n-k} B\_i \leq \# B\_1 + (n-k-1) = n-1$. So there is some element not in $\bigcup B\_i$, and this element is not independent.


As I commented above, I think it would be more natural to impose that $M$ has neither loops nor co-loops. The best I can find for that problem $k(n-k)$, by using $U(k-1,k) \oplus U(1, n-k)$, where $U(r,m)$ is the uniform matroid of rank $r$ on $m$ elements. If you ask for the matroid to be connected, I can achieve $k(n-k)+1$ by starting with $U(k,k+1)$ and replacing one element with $n-k$ parallel copies. I would guess these are optimal. 


