Using IntegerPartitions for distinct integers

Question

What I would like to do is to find a way to test how many ways m distinct integers from the set {1,..., n} where n ≥ m can sum to a given integer K?

Answer 1

When you say "how many ways", I interpret this to mean you want to count the number of partitions, and do not necessarily need to find the partitions themselves. Also, summing to the given integer $k$ only requires the set from 1 to $k$, rather than 1 to $n$. So assume $n\le k$.

In this case, you can usePartitionsQ[k]to find the number of partitions of integer $k$ into distinct parts, which is Sloane's A000009. https://oeis.org/A000009

PartitionsQ[Range[10]]
(* {1, 1, 2, 2, 3, 4, 5, 6, 8, 10} *)

However, you also state you want to use only a specified number $m$ of integers from the set 1 to $k$.PartitionsQ[k]gives you the total count for all possible $m$. The count for specific $m$ may be obtained by using generating functions.

The generating function corresponding toPartitionsQhas the following form.

Series[Product[1 + z^i, {i,1,k}], {z,0,k}]

The coefficient of $z^k$ in this series gives the number of ways of partitioning $k$ into distinct parts.

Coefficient[Series[Product[1 + z^i, {i,1,k}], {z,0,k}], z, k]

For example, to find the number of partitions into distinct parts of $k=7$ you would use

Block[{z,k=7}, Coefficient[Series[Product[1 + z^i, {i,1,k}], {z,0,k}], z, k]]

The 5 partitions of $k=7$ into distinct integers are {7}, {6, 1}, {5, 2}, {4, 3}, and {4, 2, 1}. To count how many partitions use $m$ distinct integers use the following generating function.

Coefficient[Series[Product[1 + t*z^i, {i,1,k}], {z,0,k}], z, k]]

For the example $k=7$, the coefficient of $z^7$ in the resulting series is $t + 3 t^2 + t^3$. Now look at the coefficients of powers of $t$, which are 1, 3, and 1. This means, from left to right, that there is one partition of 7 into 1 distinct part, 3 partitions of 7 into 2 distinct parts, and 1 partition of 7 into 3 distinct parts.

Consider another example for $k=9$ and $m=3$. The generating function is

Block[{k=9,m=3}, Series[Product[1 + t*z^i, {i,1,k}], {z,0,k}]]

The coefficient of $z^{k=9}$ is $t + 4 t^2 + 3 t^3$. Hence, $k=9$ may be formed by one set of 1 distinct integer from 1 to 9, that is, {9}. Moreover, $k=9$ may be formed by four sets of 2 distinct integers from 1 to 9, that is, {8, 1}, {7, 2}, {6, 3}, {5, 4}. Finally, $k=9$ may be formed by three sets of 3 distinct integers from 1 to 9, that is, {6, 2, 1}, {5, 3, 1}, {4, 3, 2}.

These partitions may be found by using IntegerPartitions as follows.

Select[IntegerPartitions[9, {1}], Length[#] == Length[Union[#]] &]
Select[IntegerPartitions[9, {2}], Length[#] == Length[Union[#]] &]
Select[IntegerPartitions[9, {3}], Length[#] == Length[Union[#]] &]

For $n<k$, use the generating function

Series[Product[1 + t*z^i, {i, 1, n}], {z, 0, k}]

or, for example,

Select[IntegerPartitions[9, {2}, Range[n]], Length[#] == Length[Union[#]] &]