3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You want to check out this question and answers therein. $\endgroup$ – Leonid Shifrin Mar 7 '14 at 11:50
  • $\begingroup$ Take a look at oeis.org/A008289, fairly sure that's what you're asking for, and there's a Mathematica implementation. $\endgroup$ – ciao Mar 7 '14 at 12:24
  • $\begingroup$ you got so far as finding IntegerPartitions, so what did you try and whats the problem? $\endgroup$ – george2079 Mar 7 '14 at 12:57
5
$\begingroup$

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[#]] &]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.