A351469 Irregular triangle read by rows where row n is Adelman's sequence containing all permutations of 1..n.

2, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 4, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 5, 3, 4, 1, 2, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 6, 5, 1, 2, 3, 6, 4, 5, 1, 2, 6, 3, 4, 5, 1, 2, 6

Offset: 2

Author

Kevin Ryde, Feb 23 2022

Keywords

• nonn
• easy
• tabf

Comments

Row n contains n^2 - 2*n + 4 = A117950(n-1) terms, numbered as columns k >= 1. Row n contains within it all permutations of 1..n as subsequences. These subsequences need not be consecutive terms (and in general are not).

Adelman's construction for row n is as follows.

- Start with a repeating sequence 1..n-1, 1..n-1, etc., of length n^2-3*n+4.

- Insert an n immediately after the i-th occurrence of n-i for each 1 <= i <= n-2, (which means insertions n-2 terms apart).

- Add an n as the first term, and add an n as the last term.

These sequences differ from Newey's A351468 by a cyclic increment, so that 1..n here is 2..n,1 in Newey, and then swap the endmost two terms. (If Adelman's insertion step continued to i=n-1 instead of adding n as the end-most term, then that would be the same as Newey up to symbols.)

Examples

			Triangle begins
  n=2:  2,1,1,2
  n=3:  3,1,2,3,1,2,3
  n=4:  4,1,2,3,4,1,2,4,3,1,2,4
  n=5:  5,1,2,3,4,5,1,2,3,5,4,1,2,5,3,4,1,2,5
For row n=3, the permutations of 1,2,3 are located within the row as follows (some are present in multiple ways too).
  3,1,2,3,1,2,3     row n=3
    1-2-3           \
    1---3---2       | all permutations
      2---1---3     | of 1,2,3 within
      2-3-1         | row n=3
  3-1-2             |
  3---2---1         /
For n=5, Adelman's construction is
    1,2,3,4,  1,2,3,  4,1,2,  3,4,1,2     repeating terms 1..4
            5,      5,      5,            insert 5's
  5                                   5   first and last 5's
		

Links

• Kevin Ryde, Table of n, a(n) for rows 2 .. 30, flattened
• Leonard Adelman, Short Permutation Strings, Discrete Mathematics, volume 10, 1974, pages 197-200.

Crossrefs

Cf. A117950 (row lengths).

Cf. A351468 (Newey's sequences).

Programs

PARI

T(n,k) = if(k==1,n, k==2,1, my(q,r);[q,r]=divrem(k-2,n-1); if(q>=n-1, if(q+r==n,n,n==2,1,2), r==0,n, (r-q)%(n-1) + 1));

PARI

row(n) = my(L=(n-1)^2+3,r=n,t=0); vector(L,i, if(r++>n, r=if(n==2,0,i==1||i==L-n,1,2);n, t++>=n,t=1, t));

Formula

T(n,1) = n;

T(n,2) = 1;

T(n,w) = n, where w = n^2-2*n+4 is the row length;

T(n,w-1) = 1 if n=2, or 2 if n>=3; and otherwise

T(n,k) = n if r=0, or

T(n,k) = 1 + ((r-q) mod (n-1)) if r != 0,

where division q = floor((k-2)/(n-1)) remainder r = (k-2) mod (n-1).