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
Examples
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, ...
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
Crossrefs
Programs
-
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); # second Maple program: 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 *)