login
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.
21

%I #25 Jan 21 2020 09:47:18

%S 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,

%T 1,3199,173891,102011,719,1,0,0,1,26945,16140983,117392909,7235651,

%U 5039,1,0,0,1,224296,1474050783,142951955371,117108036719,674641325,40319,1

%N 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.

%H Alois P. Heinz, <a href="/A269129/b269129.txt">Antidiagonals n = 0..50, flattened</a>

%H J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. <a href="http://www.ams.org/mathscinet-getitem?mr=681905">MR 681905</a>

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

%e Square array A(n,k) begins:

%e 0, 0, 0, 0, 0, 0, ...

%e 1, 0, 0, 0, 0, 0, ...

%e 1, 1, 1, 1, 1, 1, ...

%e 1, 5, 43, 374, 3199, 26945, ...

%e 1, 23, 1879, 173891, 16140983, 1474050783, ...

%e 1, 119, 102011, 117392909, 142951955371, 173996758190594, ...

%p g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*

%p binomial(n-1, l[-1]-1)+add(f(sort(subsop(j=l[j]

%p -1, l))), j=1..nops(l)-1))(add(i, i=l))

%p end:

%p f:= l->(n->`if`(n=0, 1, `if`(l[1]=0, 0, `if`(n=1 or l[-1]=1, 1,

%p `if`(n=2, binomial(l[1]+l[2], l[1])-1, g(l))))))(nops(l)):

%p A:= (n, k)-> (k*n)!/k!^n - f([k$n]):

%p seq(seq(A(n, d-n), n=0..d), d=0..12);

%p # second Maple program:

%p b:= proc(k, p, j, l, t) option remember;

%p `if`(k=0, (-1)^t/l!, `if`(p<0, 0, add(b(k-i, p-1,

%p j+1, l+i*j, irem(t+i*j, 2))/(i!*p!^i), i=0..k)))

%p end:

%p A:= (n, k)-> (n*k)!*(1/k!^n-b(n, k-1, 1, 0, irem(n, 2))*n!):

%p seq(seq(A(n, d-n), n=0..d), d=0..12); # _Alois P. Heinz_, Mar 03 2016

%t 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}]] ];

%t 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_ *)

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

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

%Y Main diagonal gives: A268751.

%Y Cf. A047909, A089759, A187783, A331562.

%K nonn,tabl

%O 0,14

%A _Alois P. Heinz_, Feb 19 2016