<p>If $S = \{2,2\}$ and $k=1$, the answer is $2$, the following dynamic program works.</p>

<p>Let $S = \{a_1,a_2,...,a_{|S|}\}$ where $a_i \leq a_{i+1}$. Consider the function $DP(i,n)$ as the number of satisfying subsets ending with element $i$ of length $n$. A satisfying set is a set $T = \{s_1,s_2,...,s_{k'}\}$ with the property $i \leq s_i \leq s_{i+1}$.</p>

<p>Hence, $DP(i,n) = 0$ if $a_i \leq n$, $1$ if $n = 1$. Otherwise, $DP(i,n) = \sum_{j=1}^{i-1} DP(j,n-1)$. The answer will then be $\sum_{j=1}^{|S|} DP(j,k)$.</p>

<p>If indeed for the case  $S = \{2,2\}$ and $k=1$, the answer is $1$. A small modification to the above recurrence is possible. Consider a representation of a multiset $S$ in the form $\{(a_1,b_1),(a_2,b_2),...,(a_n, b_n)\}$ where $a_i &lt; a_{i+1}$ and $b_i$ is the number of copies of $a_i$ in $S$.</p>

CC BY-SA 3.0
2017-03-01T03:31:56.863Z
That is very nice! Indeed, your example should have two solutions (take the first, or the second 2).
Per Alexandersson
CC BY-SA 3.0
2017-03-01T03:07:53.247Z
2017-03-01T03:07:53.247Z
S. Pek
<p>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$.</p>

<p>Can this problem be done in polynomial time (polynomial in size of $S$)?</p>

<p>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.</p>

CC BY-SA 3.0
2017-03-01T00:25:27.963Z
Just to clarify one more time. If $S = \{2,2\}$ and $k = 1$, should the answer be $1$ or $2$?
Mikhail Rudoy
<co.combinatorics><counting-complexity>
Counting subsets of given set with certain properties
Per Alexandersson
# Counting subsets of given set with certain properties

(Asked by: username_0 on 2017-02-28)

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.

**Tags:** co.combinatorics, counting-complexity
> **Comments:**
> **username_1**: Just to clarify one more time. If $S = \{2,2\}$ and $k = 1$, should the answer be $1$ or $2$?  

---

## 1 answers

### Answer by username_2 on 2017-03-01. Score: 3 | Accepted answer

If $S = \{2,2\}$ and $k=1$, the answer is $2$, the following dynamic program works.

Let $S = \{a\_1,a\_2,...,a\_{|S|}\}$ where $a\_i \leq a\_{i+1}$. Consider the function $DP(i,n)$ as the number of satisfying subsets ending with element $i$ of length $n$. A satisfying set is a set $T = \{s\_1,s\_2,...,s\_{k'}\}$ with the property $i \leq s\_i \leq s\_{i+1}$.

Hence, $DP(i,n) = 0$ if $a\_i \leq n$, $1$ if $n = 1$. Otherwise, $DP(i,n) = \sum\_{j=1}^{i-1} DP(j,n-1)$. The answer will then be $\sum\_{j=1}^{|S|} DP(j,k)$.

If indeed for the case $S = \{2,2\}$ and $k=1$, the answer is $1$. A small modification to the above recurrence is possible. Consider a representation of a multiset $S$ in the form $\{(a\_1,b\_1),(a\_2,b\_2),...,(a\_n, b\_n)\}$ where $a\_i < a\_{i+1}$ and $b\_i$ is the number of copies of $a\_i$ in $S$.

> **Comments:**
> **username_0**: That is very nice! Indeed, your example should have two solutions (take the first, or the second 2).  

---

