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.

1, 0, 1, 0, 1, 3, 0, 4, 17, 15, 0, 36, 181, 254, 105, 0, 576, 3220, 5693, 3966, 945, 0, 14400, 86836, 177745, 161773, 67251, 10395, 0, 518400, 3313296, 7527688, 8134513, 4524085, 1248483, 135135

Offset: 0

Author

Ian Duff, Jul 09 2019

Keywords

• nonn
• tabl
• more

Comments

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.

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.

The sum of row r in the table is (r!)^2 and T(r,1) for r > 0 is ((r-1)!)^2.

Examples

			The triangle up to r = 7 is:
  r\c   0      1       2       3       4       5       6      7
  0     1
  1     0      1
  2     0      1       3
  3     0      4      17      15
  4     0     36     181     254     105
  5     0    576    3220    5693    3966     945
  6     0  14400   86836  177745  161773   67251   10395
  7     0 518400 3313296 7527688 8134513 4524085 1248483 135135
		

Links

• Zile Hui, Sequential Optimization Numbers and Conjecture about Edge-Symmetry and Weight-Symmetry Shortest Weight-Constrained Path, arXiv:2206.07052 [cs.DS], 2022.
• Zile Hui, C sequential optimization numbers, arXiv:2411.17127 [math.CO], 2024. See p. 8.

Crossrefs

Row sums and T(r,1) for r > 0 give A001044.

Main diagonal gives A001147.

Cf. A132393, giving the analogous table for a single permutation, i.e., cards varying only by width or by height.

Programs

BASIC

r=5
fr=1
for i=2 to r : fr=fr*i : next i            ' fr=r!
dim perm(fr,r), a(fr,r), b(r), count(r), p(r)
for i=1 to fr : for j=1 to r : a(i,j)=0 : next j : next i
for i=1 to r : count(i)=0 : next i
'*** now derive successive permutations p() and populate rows of perm()
for k=0 to fr-1
   for i=1 to r : p(i)=i : next i
   f=1
   for j=2 to r
      f=f*(j-1)
      a=int(k/f)
      i=a mod j
      x=p(j-i) : p(j-i)=p(j) : p(j)=x
   next j
   for i=1 to r
      perm(k+1,i)=p(i)
   next i
next k
'***
'*** now determine which numbers are visible for each permutation and
'     put in a()
for k=1 to fr
   max=perm(k,1)
   a(k,perm(k,1))=1
   for i=2 to r
      if perm(k,i)>max then max=perm(k,i) : a(k,perm(k,i))=1
   next i
next k
'***
'*** now determine which numbers [b()], and how many [count()], are
'     visible for each combination of permutations
for i=1 to fr
   for j=1 to fr
      tb=0
      for k=1 to r
         b(k)=0 : if a(i,k)=1 or a(j,k)=1 then b(k)=1
         tb=tb+b(k)
      next k
      count(tb)=count(tb)+1
   next j
next i
'***
for c=1 to r
   print c;"   ";count(c)
next c