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

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

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.

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

Example

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

Prog

(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));

Crossrefs

Cf. A117950 (row lengths).

Cf. A351468 (Newey's sequences).

Sequence in context: A179009 A112757 A219794 * A286334 A118492 A079246

Adjacent sequences: A351466 A351467 A351468 * A351470 A351471 A351472

Keyword

nonn,easy,tabf

Author

Kevin Ryde, Feb 23 2022

Status

approved