cp's OEIS Frontend

A309053 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.

%I A309053 #48 Nov 29 2024 17:55:51
%S A309053 1,0,1,0,1,3,0,4,17,15,0,36,181,254,105,0,576,3220,5693,3966,945,0,
%T A309053 14400,86836,177745,161773,67251,10395,0,518400,3313296,7527688,
%U A309053 8134513,4524085,1248483,135135
%N A309053 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 A309053 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 A309053 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 A309053 The sum of row r in the table is (r!)^2 and T(r,1) for r > 0 is ((r-1)!)^2.
%H A309053 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.
%H A309053 Zile Hui, <a href="https://arxiv.org/abs/2411.17127">C sequential optimization numbers</a>, arXiv:2411.17127 [math.CO], 2024. See p. 8.
%e A309053 The triangle up to r = 7 is:
%e A309053   r\c   0      1       2       3       4       5       6      7
%e A309053   0     1
%e A309053   1     0      1
%e A309053   2     0      1       3
%e A309053   3     0      4      17      15
%e A309053   4     0     36     181     254     105
%e A309053   5     0    576    3220    5693    3966     945
%e A309053   6     0  14400   86836  177745  161773   67251   10395
%e A309053   7     0 518400 3313296 7527688 8134513 4524085 1248483 135135
%o A309053 (BASIC)
%o A309053 r=5
%o A309053 fr=1
%o A309053 for i=2 to r : fr=fr*i : next i            ' fr=r!
%o A309053 dim perm(fr,r), a(fr,r), b(r), count(r), p(r)
%o A309053 for i=1 to fr : for j=1 to r : a(i,j)=0 : next j : next i
%o A309053 for i=1 to r : count(i)=0 : next i
%o A309053 '*** now derive successive permutations p() and populate rows of perm()
%o A309053 for k=0 to fr-1
%o A309053    for i=1 to r : p(i)=i : next i
%o A309053    f=1
%o A309053    for j=2 to r
%o A309053       f=f*(j-1)
%o A309053       a=int(k/f)
%o A309053       i=a mod j
%o A309053       x=p(j-i) : p(j-i)=p(j) : p(j)=x
%o A309053    next j
%o A309053    for i=1 to r
%o A309053       perm(k+1,i)=p(i)
%o A309053    next i
%o A309053 next k
%o A309053 '***
%o A309053 '*** now determine which numbers are visible for each permutation and
%o A309053 '     put in a()
%o A309053 for k=1 to fr
%o A309053    max=perm(k,1)
%o A309053    a(k,perm(k,1))=1
%o A309053    for i=2 to r
%o A309053       if perm(k,i)>max then max=perm(k,i) : a(k,perm(k,i))=1
%o A309053    next i
%o A309053 next k
%o A309053 '***
%o A309053 '*** now determine which numbers [b()], and how many [count()], are
%o A309053 '     visible for each combination of permutations
%o A309053 for i=1 to fr
%o A309053    for j=1 to fr
%o A309053       tb=0
%o A309053       for k=1 to r
%o A309053          b(k)=0 : if a(i,k)=1 or a(j,k)=1 then b(k)=1
%o A309053          tb=tb+b(k)
%o A309053       next k
%o A309053       count(tb)=count(tb)+1
%o A309053    next j
%o A309053 next i
%o A309053 '***
%o A309053 for c=1 to r
%o A309053    print c;"   ";count(c)
%o A309053 next c
%Y A309053 Row sums and T(r,1) for r > 0 give A001044.
%Y A309053 Main diagonal gives A001147.
%Y A309053 Cf. A132393, giving the analogous table for a single permutation, i.e., cards varying only by width or by height.
%K A309053 nonn,tabl,more
%O A309053 0,6
%A A309053 _Ian Duff_, Jul 09 2019