A269129 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding the pattern 12...n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 5, 1, 0, 0, 1, 43, 23, 1, 0, 0, 1, 374, 1879, 119, 1, 0, 0, 1, 3199, 173891, 102011, 719, 1, 0, 0, 1, 26945, 16140983, 117392909, 7235651, 5039, 1, 0, 0, 1, 224296, 1474050783, 142951955371, 117108036719, 674641325, 40319, 1

Offset

0,14

Links

Alois P. Heinz, Antidiagonals n = 0..50, flattened

J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Formula

A(n,k) = A089759(k,n) - A047909(k,n) = A187783(n,k) - A047909(k,n).

Example

Square array A(n,k) begins:
  0,   0,      0,         0,            0,               0, ...
  1,   0,      0,         0,            0,               0, ...
  1,   1,      1,         1,            1,               1, ...
  1,   5,     43,       374,         3199,           26945, ...
  1,  23,   1879,    173891,     16140983,      1474050783, ...
  1, 119, 102011, 117392909, 142951955371, 173996758190594, ...

Maple

g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*
      binomial(n-1, l[-1]-1)+add(f(sort(subsop(j=l[j]
      -1, l))), j=1..nops(l)-1))(add(i, i=l))
    end:
f:= l->(n->`if`(n=0, 1, `if`(l[1]=0, 0, `if`(n=1 or l[-1]=1, 1,
    `if`(n=2, binomial(l[1]+l[2], l[1])-1, g(l))))))(nops(l)):
A:= (n, k)-> (k*n)!/k!^n - f([k$n]):
seq(seq(A(n, d-n), n=0..d), d=0..12);
# Alternative:
b:= proc(k, p, j, l, t) option remember;
      `if`(k=0, (-1)^t/l!, `if`(p<0, 0, add(b(k-i, p-1,
       j+1, l+i*j, irem(t+i*j, 2))/(i!*p!^i), i=0..k)))
    end:
A:= (n, k)-> (n*k)!*(1/k!^n-b(n, k-1, 1, 0, irem(n, 2))*n!):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Mar 03 2016

Mathematica

b[k_, p_, j_, l_, t_] := b[k, p, j, l, t] = If[k == 0, (-1)^t/l!, If[p < 0, 0, Sum[b[k-i, p-1, j+1, l + i j, Mod[t + i j, 2]]/(i! p!^i), {i, 0, k}]] ];
A[n_, k_] := (n k)! (1/k!^n - b[n, k-1, 1, 0, Mod[n, 2]] n!); Table[ Table[ A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Apr 07 2016, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A057427, A033312, A267532, A269113, A269114, A269115, A269116, A269117, A269118, A269119, A269120.

Rows n=0-10 give: A000004, A000007, A000012, A269121, A269122, A269123, A269124, A269125, A269126, A269127, A269128.

Main diagonal gives: A268751.

Cf. A047909, A089759, A187783, A331562.

Sequence in context: A098173 A180977 A371761 * A320606 A343016 A386715

Adjacent sequences: A269126 A269127 A269128 * A269130 A269131 A269132

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 19 2016

Status

approved