# Integer partitions with subset sums “not divisible” by p

I have the following questions: Let $N \in \mathbb{N}$ and $$\sum_{i=1}^k n_i = N,$$ with $n_i \in \mathbb{N}$ for $1 \le i \le k$ and some $k \in \mathbb{N}$, be an integer partition of $N$, such that $n_i \le p$ and for all non-empty subsets $I \subset \{1,\ldots,k\}$ we either have $$\sum_{i \in I} n_i \notin p \mathbb{N}$$ or $$n_i = p, \;\;\;\;\;\;\;\; \forall i \in I.$$ (I.e., in words, any subset sum is not a multiple of $p$ except it consists of the number $p$ only). How can I generate these partitions efficiently? Is there a closed expression for the number of such partitions?

For example, for $N=16$ and $p = 5$ I count the following 5 partitions: $$\begin{split} 5+5+5+1 &= 16, \\ 5+5+4+2 &= 16, \\ 5+5+3+3 &= 16, \\ 5+4+4+3 &= 16, \\ 4+4+4+4 &= 16. \\ \end{split}$$

• By the pigeonhole principle, there are at most $k-1$ non-$k$ numbers in the partition. This may make the generation of the partitions easier when $k$ is small. – LeechLattice Jul 18 '18 at 15:10
• What does OEIS say? – Per Alexandersson Jul 18 '18 at 21:01
• Als the sum over the empty subset (which is zero) is allowed to be divisible by k – Jan-Willem van Ittersum Jul 19 '18 at 8:53
• I get a bit confused. Is the number $k$ denoting the number of parts equal to the divisor $k$? In your example the first is 4 and the latter 5. Moreover, shouldn't 7 + 5 + 2 + 2 = 16 be another example? – Jan-Willem van Ittersum Jul 19 '18 at 9:08
• For computational purposes, it might be better to do the complementary problem (partition kp-N into at most k pieces each of size less than p) and use some technique like the one I mentioned to prune partitions. This is a much smaller problem if N/kp is close to 1. Gerhard "More Ways To Trim Problem" Paseman, 2018.07.19. – Gerhard Paseman Jul 19 '18 at 17:36