2
$\begingroup$

With IntegerPartitions[7], I have partitions of 7 into integers that are smaller than 6 as follows.

{5, 2}, 
{5, 1, 1}, 
{4, 3}, 
{4, 2, 1}, 
{4, 1, 1, 1}, 
{3, 3, 1}, 
{3, 2, 2}, 
{3, 2, 1, 1}, 
{3, 1, 1, 1, 1}, 
{2, 2, 2, 1}, 
{2, 2, 1, 1, 1}, 
{2, 1, 1, 1, 1, 1}, 
{1, 1, 1, 1, 1, 1, 1}

Furthermore, I want to include the permutation of each partition. For the first partition, for example, I also want to include {2, 5}.

Question

How to calculate the whole permutation of the partition of 7 given above? I don't need the list for sure, but just the length of the list.

$\endgroup$
2
  • $\begingroup$ Related: Find all permutations with a condition $\endgroup$
    – Carl Woll
    Dec 29, 2017 at 18:42
  • $\begingroup$ Is this some of one-shot problem, or are you after a generalized solution? If the latter, this can be done much more efficiently than the answers here... $\endgroup$
    – ciao
    Dec 30, 2017 at 0:28

2 Answers 2

4
$\begingroup$

You could just apply Permutations to the partitions:

Length @ Catenate @ Map[Permutations] @ IntegerPartitions[7, 7, Range[5]]

61

update

And, a faster version that avoids computing all the permutations:

permCount[list_] := Multinomial @@ Tally[list][[All,2]]

Total @ Map[permCount] @ IntegerPartitions[7, 7, Range[5]]

61

$\endgroup$
8
$\begingroup$

Perhaps a slightly more efficient method:

 ClearAll["Global`*"]

 num[int_,max_]:=SeriesCoefficient[(1-x)/(1-2x+x^(max+1)),{x,0,int}];

Arguments are target number and maximum allowed element in partitions.

For large cases, the following (same arguments as above) can net additional speed, depending on relative magnitudes of the target and maximum:

num2=ParallelSum[(-1)^r Binomial[#1-#2*r-1, n-1] Binomial[n, r],{n,#1},{r,0,(#1 - n)/#2}]&;

Some timing comparisons:

enter image description here

Warning: Don't even think about trying test cases of this size with extant answers, you'll probably crash the kernel or lockup your machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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