Write function for complicated recurrence relation.

7 次查看（过去 30 天）
John597623
John597623 2023-10-12
编辑： Torsten 2023-10-26
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
  4 个评论
显示 2更早的评论
John597623
John597623 2023-10-25
编辑：John597623 2023-10-25
@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
Torsten 2023-10-26
编辑：Torsten 2023-10-26
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Torsten
Torsten 2023-10-26
编辑：Torsten 2023-10-26
Ran in:
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

类别

在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

产品


版本

R2023a

Community Treasure Hunt

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

Start Hunting!

Translated by