For k=4
and n=6
, we have
1 + 1 + 1 + 3 = 6
1 + 1 + 2 + 2 = 6
which can be obtained from the Triangle of partition numbers.
But for 1 + 1 + 1 + 3
we can have 3
more permutations (4 in total) as follows:
1 + 1 + 1 + 3
1 + 1 + 3 + 1
1 + 3 + 1 + 1
3 + 1 + 1 + 1
and for 1 + 1 + 2 + 2
we can also have 5
more permutations (6 in total) as follows:
1 + 1 + 2 + 2
1 + 2 + 1 + 2
1 + 2 + 2 + 1
2 + 1 + 2 + 1
2 + 1 + 1 + 2
2 + 2 + 1 + 1
which I think in general, binomial(n, n - k)
for every possible partition.
How to find all these partitions in Python or in Julia?
In Julia, my attempt is the following, which is I think correct but not optimal since I am generating all permutations and then applying unique to remove the duplicate ones.
using Combinatorics
n, k = 6, 4
comb = []
for partition in partitions(n, k)
permuted_partition = permutations(partition)
unique_permuted_partition = unique(permuted_partition)
append!(comb, unique_permuted_partition)
end
In Julia, the following answers the question but I think it is not optimal since I am generating all permutations and then applying unique to remove the duplicate ones.
using Combinatorics
n, k = 6, 4
comb = []
for partition in partitions(n, k)
permuted_partition = permutations(partition)
unique_permuted_partition = unique(permuted_partition)
append!(comb, unique_permuted_partition)
end