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

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}

[Ben Frankel]

What do you mean by "total number of incidences of a kj part"?

[Radu Mihail]

Simply how many times one finds in all possible compositions of N the part kj. for instance part 1 has 5 incidences in all 3 compositions of N=3

Answer 1

[Kaitlyn Keil]

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
            disp(arr);
            count = 1;
        elseif(n > 0)
            count = 0;
            for k = 1:n
                subarr = [arr k];
                count = count + countAllCombinators(subarr, n-k);
            end
        end    
end

Hope that helps!

[Radu Mihail]

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