As in the original
Row of Towers, consider assemblage of unit squares in the form of n towers with heights 1,2,...,n forming a polyomino. In that problem you found the maximum possible perimeter for a given value of n.
Now consider all possible rows of towers for a given n. What is the probability a randomly chosen tower will have the maximum perimeter?
Since my original program actually found all the possible orders while looking for a maximum perimeter, a modification of that program is easily made to count the number of permutations that result in the maximum perimeter:
clearvars,clc
b=[];
for n=1:11
orders=perms(1:n);
best=0; bestOrder=[]; bestCount=0;
for i=1:length(orders)
order=orders(i,:);
peri=2*n+order(1)+order(end) ...
+sum(abs(order(1:end-1)-order(2:end)));
if peri>best
best=peri;
bestOrder=order;
bestCount=1;
elseif peri==best
bestCount=bestCount+1;
end
end
b(end+1)=best;
fprintf('%2d %3d %14.12f\n',n,best,bestCount/length(orders))
fprintf('%3d ',bestCount,length(orders))
fprintf('%s ',sym(bestCount/length(orders)))
fprintf('\n\n')
end
In each group, the first line has n, the maximum perimeter and the probability that a given order is the maximal one.
The second line contains the number of permutations giving the maximum perimeter, the number of permutations altogether and the probability as a common fraction.
1 4 1.000000000000
1 1 1
2 8 1.000000000000
2 2 1
3 14 0.333333333333
2 6 1/3
4 20 0.333333333333
8 24 1/3
5 28 0.100000000000
12 120 1/10
6 36 0.100000000000
72 720 1/10
7 46 0.028571428571
144 5040 1/35
8 56 0.028571428571
1152 40320 1/35
9 68 0.007936507937
2880 362880 1/126
10 80 0.007936507937
28800 3628800 1/126
11 94 0.002164502165
86400 39916800 1/462
The fractions all appear to be Egyptian.
There are ten series in OEIS that match the denominators of these fractions.
However, the numerators and denominators of the raw numbers do each have their own known sequences. The denominators are of course n!. The numerators are found as OEIS's A092186.
The OEIS's title for this sequence is a formula for its computation, but in the form of one formula for even n and another for odd n. However, these can be combined into
(1 + (n+1) mod 2) * (floor(n/2))! * (ceil(n/2))!
That's the numerator, and as the denominator is just n!, the formula sought is
(1 + (n+1) mod 2) * (floor(n/2))! * (ceil(n/2))! / n!
So the table of probabilities can be extended:
[1, 1]
[2, 1]
[3, 1/3]
[4, 1/3]
[5, 1/10]
[6, 1/10]
[7, 1/35]
[8, 1/35]
[9, 1/126]
[10, 1/126]
[11, 1/462]
[12, 1/462]
[13, 1/1716]
[14, 1/1716]
[15, 1/6435]
[16, 1/6435]
[17, 1/24310]
[18, 1/24310]
[19, 1/92378]
[20, 1/92378]
[21, 1/352716]
[22, 1/352716]
[23, 1/1352078]
[24, 1/1352078]
[25, 1/5200300]
Further, this enables us to get the denominators of the Egyptian fractions directly by singling out the appropriate sequence in the OEIS: A128015 Binomial coefficients C(2n+1,n) repeated.
After some experimentation, the probabilities are
1 / C(2*floor((n-1)/2)+1,floor((n-1)/2))
for n=sym(1):25
v=nchoosek(sym(2)*floor((n-1)/2)+1,floor((n-1)/2));
disp([n,sym(1/v)])
end
[1, 1]
[2, 1]
[3, 1/3]
[4, 1/3]
[5, 1/10]
[6, 1/10]
[7, 1/35]
[8, 1/35]
[9, 1/126]
[10, 1/126]
[11, 1/462]
[12, 1/462]
[13, 1/1716]
[14, 1/1716]
[15, 1/6435]
[16, 1/6435]
[17, 1/24310]
[18, 1/24310]
[19, 1/92378]
[20, 1/92378]
[21, 1/352716]
[22, 1/352716]
[23, 1/1352078]
[24, 1/1352078]
[25, 1/5200300]
|
|
Posted by Charlie
on 2024-03-01 13:19:50 |
solution
