Search: a177304 -id:a177304
|
| |
|
|
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.
|
|
+10
20
|
|
|
|
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
|
|
|
|
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]];
|
|
|
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.008 seconds
|
