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
KEYWORD
nonn,easy,tabf
AUTHOR
Kevin Ryde, Feb 23 2022
STATUS
approved