|
%I #12 Mar 07 2022 06:31:04
%S 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,
%T 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,
%U 2,6
%N Irregular triangle read by rows where row n is Adelman's sequence containing all permutations of 1..n.
%C 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).
%C Adelman's construction for row n is as follows.
%C - Start with a repeating sequence 1..n-1, 1..n-1, etc., of length n^2-3*n+4.
%C - 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).
%C - Add an n as the first term, and add an n as the last term.
%C 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.)
%H Kevin Ryde, <a href="/A351469/b351469.txt">Table of n, a(n) for rows 2 .. 30, flattened</a>
%H Leonard Adelman, <a href="https://doi.org/10.1016/0012-365X(82)90224-2">Short Permutation Strings</a>, Discrete Mathematics, volume 10, 1974, pages 197-200.
%F T(n,1) = n;
%F T(n,2) = 1;
%F T(n,w) = n, where w = n^2-2*n+4 is the row length;
%F T(n,w-1) = 1 if n=2, or 2 if n>=3; and otherwise
%F T(n,k) = n if r=0, or
%F T(n,k) = 1 + ((r-q) mod (n-1)) if r != 0,
%F where division q = floor((k-2)/(n-1)) remainder r = (k-2) mod (n-1).
%e Triangle begins
%e n=2: 2,1,1,2
%e n=3: 3,1,2,3,1,2,3
%e n=4: 4,1,2,3,4,1,2,4,3,1,2,4
%e n=5: 5,1,2,3,4,5,1,2,3,5,4,1,2,5,3,4,1,2,5
%e For row n=3, the permutations of 1,2,3 are located within the row as follows (some are present in multiple ways too).
%e 3,1,2,3,1,2,3 row n=3
%e 1-2-3 \
%e 1---3---2 | all permutations
%e 2---1---3 | of 1,2,3 within
%e 2-3-1 | row n=3
%e 3-1-2 |
%e 3---2---1 /
%e For n=5, Adelman's construction is
%e 1,2,3,4, 1,2,3, 4,1,2, 3,4,1,2 repeating terms 1..4
%e 5, 5, 5, insert 5's
%e 5 5 first and last 5's
%o (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));
%o (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));
%Y Cf. A117950 (row lengths).
%Y Cf. A351468 (Newey's sequences).
%K nonn,easy,tabf
%O 2,1
%A _Kevin Ryde_, Feb 23 2022
|
