How to calculate the total number of incidences of a kj part in all compositions of a natural number N

1 view (last 30 days)
A composition of natural number N is a partition in ki summands(parts) of N=k1+k2+k3+k4...+ki , with ki >or =1 and ki<N, where the order of the parts is important. For instance there are 3 compositions of N=3 are: {1,1,1} {1,2} {2,1}

Answers (1)

Kaitlyn Keil
Kaitlyn Keil on 27 Jul 2018
Here is a loop that will print this out for you, though it does include the single case (just the number itself):
function count = countAllCombinators(arr, n)
if n==0
count = 1;
elseif(n > 0)
count = 0;
for k = 1:n
subarr = [arr k];
count = count + countAllCombinators(subarr, n-k);
Hope that helps!
  1 Comment
Radu Mihail
Radu Mihail on 27 Jul 2018
Dear Kaitlyn thank you for your input. However, your loop just calculates the number of compositions of N which is simply calculated by the formula 2^(n-1).
Instead, what I need to calculate is in all compositions of number n how many times each of its summands shows up(summands are the individual terms used in adding up to get n-also called parts ). Ex : in 8 compositions of N=4 [1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2],[1,3],[3,1],[4]
the part(summand) 1 has 12 incidences,
the part(summand) 2 has 5 incidences,
the part(summand) 3 has 2 incidences,
4 does not count in compositions as summand for it is equal to N. Your code for summand 1 and N=3 yields just the number of N compositions
>> arr=[1],n=3 arr = 1 n = 3 >> count = countAllCombinators(arr, n) 1 1 1 1 1 1 2 1 2 1 1 3 count = 4

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by