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,6

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

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

Links

Table of n, a(n) for n=0..35.

Zile Hui, Sequential Optimization Numbers and Conjecture about Edge-Symmetry and Weight-Symmetry Shortest Weight-Constrained Path, arXiv:2206.07052 [cs.DS], 2022.

Prog

(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

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.

Sequence in context: A074171 A180657 A094665 * A052439 A261239 A261214

Adjacent sequences: A309050 A309051 A309052 * A309054 A309055 A309056

Keyword

nonn,tabl,more

Author

Ian Duff, Jul 09 2019

Status

approved