Consider the following problem: Given is a multiset of positive integers, $S$, and an integer $k$. Count submulisets of $S$ of size $k$, $\{s_1,\dotsc,s_k\} \subseteq S$, such that when the $s_i$ are ordered increasingly, $s_i \geq i$.
Can this problem be done in polynomial time (polynomial in size of $S$)?
Background: This is a very special case of counting independent subsets of a graph, (which is hard), but I suspect this special case might be solvable via some clever dynamic programming.