Write function for complicated recurrence relation.

Hi all!

I'm trying to learn myself how to write some code in Matlab to solve some involved recurrence relations. But I'm not a great programmer and I have a very hard time to go from the simple examples (of calculating a factorial), to something more complicated.

I'm now trying to solve the equation below for a given value of n, using functions in Matlab. But to be honest, I have no clue how to make sure the correct (intermediate) values should get passed along, by calling a function. At this point I'm just very confused and didn't get any code to actually run in a way that produced any results.

I know it's quite an ask, but would be amazing if someone could show me how to solve an example like this.

Greetings,

John

[John597623]

and

[Anton Kogios]

I'd like to help with this, but what exactly are you looking for? I don't think I understand what you're asking. Are the equations in your image seperate? This is what I have so far:

syms n k j t integer
L(k,n) = symsum(1/(factorial(j)*k^j) * 1/factorial(n-k*j),j,1,n/k)

L(k, n) = 

S(k,n) = symsum(L(t,n-k*j),t,1,min(k-1,n-k*j))

S(k, n) = 

L1n = L(1,n) % this doesn't simplify well

L1n = 

Lnn = L(n,n) % this works

Lnn = 

[John597623]

@Anton Kogios I missed your reply earlier, thanks!

No, it's one equation! (In this case it's the probability mass function of the longest cycle occuring for the 100 prisoners problem; in case you're familiar.) It's a recurrence relation that changes depending on different ranges k is in. You can find more info in this paper. I just divided by n! to get the probability instead of the number of permutations. On the page with page number 100, you can find some results of the equation that are given in the form of a triangle.

So, I was thinking of writing a function (but another way is also fine with me) with recurrence. But indeed I didn't know how to combine the parts.

L1n and Lnn are just boundary conditions. I think we need to at least define L11 = 1 to solve the problem. But since I already know the value of L1n and Lnn from the problem statement, I figured I also state those. (The brackets above the first summation denote a floor function.)

[Torsten]

Computing L_2,4 with the formula given, I get

L_2,4 = 1/(1!*2^1) * 4!/2! * L_1,2 + 1/(2!*2^2) * 4!/1 * 0 = 6

But the result should be

L_2,4 = 9

So either I misunderstand your formula or there is something wrong with it.

Answer 1

[Torsten]

I modified your formula slightly, and after this modification, it seems to give correct results:

N = 14;
L = zeros(N);
L(1,1:N) = 1;
for n = 2:N
    for k = 2:n-1
        sum1 = 0.0;
        for j = 1:floor(n/k)
            sum2 = 0.0;
            for t = 1:min(k-1,max(1,n-k*j))
                sum2 = sum2 + L(t,max(1,n-k*j));
            end
            sum1 = sum1 + sum2 * factorial(n)/(factorial(j)*(k^j)*factorial(n-k*j));
        end
        L(k,n) = sum1;
    end
    L(n,n) = factorial(n-1);
end
int64(L(:,N))

ans = 14×1

1 2390479 279199648 2301835536 6178588416 9427017600 11564467200 10897286400 9686476800 8717829120

int64(sum(L(:,N)))

ans = int64 87178291200

int64(factorial(N))

ans = int64 87178291200