login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A331562 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding absolute differences between adjacent elements larger than one; square array A(n,k), n>=0, k>=0, read by antidiagonals. 19
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 6, 2, 1, 1, 1, 20, 12, 2, 1, 1, 1, 70, 92, 26, 2, 1, 1, 1, 252, 780, 506, 48, 2, 1, 1, 1, 924, 7002, 11482, 2288, 86, 2, 1, 1, 1, 3432, 65226, 284002, 135040, 10010, 148, 2, 1, 1, 1, 12870, 623576, 7426610, 8956752, 1543862, 41618, 250, 2, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,9

COMMENTS

All columns are linear recurrences with constant coefficients and for k > 0 the order of the recurrence is bounded by 3*k-1. For k up to at least 17 this upper bound is exact. - Andrew Howroyd, May 16 2020

LINKS

Andrew Howroyd, Antidiagonals n = 0..50, flattened (antidiagonals 0..15 from Alois P. Heinz)

EXAMPLE

A(2,2) = 6: 1122, 1212, 1221, 2112, 2121, 2211.

A(3,2) = 12: 112233, 112323, 112332, 121233, 123321, 211233, 233211, 321123, 323211, 332112, 332121, 332211.

A(2,3) = 20: 111222, 112122, 112212, 112221, 121122, 121212, 121221, 122112, 122121, 122211, 211122, 211212, 211221, 212112, 212121, 212211, 221112, 221121, 221211, 222111.

A(3,3) = 92: 111222333, 111223233, 111223323, 111223332, ..., 333221112, 333221121, 333221211, 333222111.

Square array A(n,k) begins:

  1, 1,  1,     1,       1,         1,           1, ...

  1, 1,  1,     1,       1,         1,           1, ...

  1, 2,  6,    20,      70,       252,         924, ...

  1, 2, 12,    92,     780,      7002,       65226, ...

  1, 2, 26,   506,   11482,    284002,     7426610, ...

  1, 2, 48,  2288,  135040,   8956752,   640160976, ...

  1, 2, 86, 10010, 1543862, 276285002, 54331653686, ...

MAPLE

b:= proc(l, q) option remember; (n-> `if`(n<2, 1, add(

     `if`(l[j]=1, `if`(j in [1, n], b(subsop(j=[][], l),

     `if`(j=1, 0, n)), 0), b(subsop(j=l[j]-1, l), j)), j=

     `if`(q<0, 1..n, max(1, q-1)..min(n, q+1)))))(nops(l))

    end:

A:= (n, k)-> `if`(k=0, 1, b([k$n], -1)):

seq(seq(A(n, d-n), n=0..d), d=0..10);

MATHEMATICA

b[l_, q_] := b[l, q] = With[{n = Length[l]}, If[n < 2, 1, Sum[

      If[l[[j]] == 1, If[j == 1 || j == n, b[ReplacePart[l, j -> Nothing],

      If[j == 1, 0, n]], 0], b[ReplacePart[l, j -> l[[j]] - 1], j]], {j,

      If[q < 0, Range[n], Range[Max[1, q - 1], Min[n, q + 1]]]}]]];

A[n_, k_] := If[k == 0, 1, b[Table[k, {n}], -1]];

Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-Fran├žois Alcover, Jan 03 2021, after Alois P. Heinz *)

PROG

(PARI)

step(m, R)={my(M=matrix(3, m+1, q, p, q--; p--; sum(j=0, m-p-q, sum(i=max(p+j-#R+1, 2*p+q+j-m), p, R[1+q, 1+p+j-i] * binomial(p, i) * binomial(p+q+j-i-1, j) * binomial(m-1, 2*p+q+j-i-1))))); M[3, ]+=2*M[2, ]+M[1, ]; M[2, ]+=M[1, ]; M}

AdjPathsBySig(sig)={if(#sig<1, 1, my(R=[1; 1; 1]); for(i=1, #sig-1, R=step(sig[i], R)); my(m=sig[#sig]); sum(i=1, min(m, #R), binomial(m-1, i-1)*R[3, i]))}

T(n, k) = {if(k==0, 1, AdjPathsBySig(vector(n, i, k)))} \\ Andrew Howroyd, May 16 2020

CROSSREFS

Columns k=0-9 give: A000012, A130130 (for n>0), A177282, A177291, A177298, A177301, A177304, A177307, A177310, A177313.

Rows n=0+1, 2-9 give: A000012, A000984, A103882, A177316, A177317, A177318, A177319, A177320, A177321.

Main diagonal gives A331623.

Cf. A269129, A275784.

Sequence in context: A331283 A060185 A129110 * A257101 A112624 A294875

Adjacent sequences:  A331559 A331560 A331561 * A331563 A331564 A331565

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jan 20 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 26 10:48 EDT 2021. Contains 346294 sequences. (Running on oeis4.)