For a fixed integer k, we define a sequence A_k = (a_k(n))_{n ≥ 0} and a corresponding sparse subsequence S_k using the cardinality of the n-th symmetric power of the set {1, 2, ..., k}. For k ∈ {2,...,8}, we find recursive formulas for S_k, and show that the values a_k(0), a_k(1), and a_k(3) are sufficient for constructing A_k.