|
%I #43 Sep 21 2023 19:27:07
%S 1,0,1,0,1,3,0,4,17,15,0,36,181,254,105,0,576,3220,5693,3966,945,0,
%T 14400,86836,177745,161773,67251,10395,0,518400,3313296,7527688,
%U 8134513,4524085,1248483,135135
%N Triangular array T read by rows: T(r,c) is the number of double permutations of the integers from 1 to r which have exactly c different values visible when viewed from the left, in the sense that a higher number hides a lower one.
%C Consider r rectangular cards stacked in a pile with their left and lower edges aligned. Each is of a different color and their widths and heights are independent permutations of the integers 1, 2, ..., r. Then the sequence gives the number of ways in which exactly c colors may be seen, where 0 <= c <= r. The values are entries in a triangular table read from left to right along successive rows from the top, each row giving the value of r and each column giving the value of c. Including a row in the triangle for r = 0 and treating the values as a list a(n) starting with n = 1, n = r(r+1)/2 + c + 1.
%C For example, r = 2. If the widths of the cards from the top of the stack are 1,2 and the heights are 1,2 then two colors are seen; if the widths are 1,2 and the heights are 2,1 then two colors are seen; if 2,1 and 1,2 then two colors are seen; if 2,1 and 2,1 then only one color is seen. Thus the values for c = 1 and c = 2 are 1 and 3 respectively, i.e., a(5) = 1 and a(6) = 3.
%C The triangle up to r = 7 is:
%C r\c 0 1 2 3 4 5 6 7
%C 0 1
%C 1 0 1
%C 2 0 1 3
%C 3 0 4 17 15
%C 4 0 36 181 254 105
%C 5 0 576 3220 5693 3966 945
%C 6 0 14400 86836 177745 161773 67251 10395
%C 7 0 518400 3313296 7527688 8134513 4524085 1248483 135135
%C The sum of row r in the table is (r!)^2 and T(r,1) for r > 0 is ((r-1)!)^2.
%H Zile Hui, <a href="https://arxiv.org/abs/2206.07052">Sequential Optimization Numbers and Conjecture about Edge-Symmetry and Weight-Symmetry Shortest Weight-Constrained Path</a>, arXiv:2206.07052 [cs.DS], 2022.
%o (BASIC)
%o r=5
%o fr=1
%o for i=2 to r : fr=fr*i : next i ' fr=r!
%o dim perm(fr,r), a(fr,r), b(r), count(r), p(r)
%o for i=1 to fr : for j=1 to r : a(i,j)=0 : next j : next i
%o for i=1 to r : count(i)=0 : next i
%o '*** now derive successive permutations p() and populate rows of perm()
%o for k=0 to fr-1
%o for i=1 to r : p(i)=i : next i
%o f=1
%o for j=2 to r
%o f=f*(j-1)
%o a=int(k/f)
%o i=a mod j
%o x=p(j-i) : p(j-i)=p(j) : p(j)=x
%o next j
%o for i=1 to r
%o perm(k+1,i)=p(i)
%o next i
%o next k
%o '***
%o '*** now determine which numbers are visible for each permutation and
%o ' put in a()
%o for k=1 to fr
%o max=perm(k,1)
%o a(k,perm(k,1))=1
%o for i=2 to r
%o if perm(k,i)>max then max=perm(k,i) : a(k,perm(k,i))=1
%o next i
%o next k
%o '***
%o '*** now determine which numbers [b()], and how many [count()], are
%o ' visible for each combination of permutations
%o for i=1 to fr
%o for j=1 to fr
%o tb=0
%o for k=1 to r
%o b(k)=0 : if a(i,k)=1 or a(j,k)=1 then b(k)=1
%o tb=tb+b(k)
%o next k
%o count(tb)=count(tb)+1
%o next j
%o next i
%o '***
%o for c=1 to r
%o print c;" ";count(c)
%o next c
%Y Row sums and T(r,1) for r > 0 give A001044.
%Y Main diagonal gives A001147.
%Y Cf. A132393, giving the analogous table for a single permutation, i.e., cards varying only by width or by height.
%K nonn,tabl,more
%O 0,6
%A _Ian Duff_, Jul 09 2019
|
