A267532 -id:A267532 - cp's OEIS frontend

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

Alois P. Heinz, Feb 19 2016

			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, ...

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

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.

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

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 *)

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

A267479 Number A(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 6, 1, 0, 1, 1, 6, 43, 1, 0, 1, 1, 6, 90, 352, 1, 0, 1, 1, 6, 90, 1879, 3114, 1, 0, 1, 1, 6, 90, 2520, 47024, 29004, 1, 0, 1, 1, 6, 90, 2520, 102011, 1331664, 280221, 1, 0, 1, 1, 6, 90, 2520, 113400, 5176504, 41250519, 2782476, 1, 0

Offset: 0

Alois P. Heinz, Jan 15 2016

			Square array A(n,k) begins:
  1, 1,     1,       1,       1,       1,       1, ...
  0, 1,     1,       1,       1,       1,       1, ...
  0, 1,     6,       6,       6,       6,       6, ...
  0, 1,    43,      90,      90,      90,      90, ...
  0, 1,   352,    1879,    2520,    2520,    2520, ...
  0, 1,  3114,   47024,  102011,  113400,  113400, ...
  0, 1, 29004, 1331664, 5176504, 7235651, 7484400, ...

Alois P. Heinz, Antidiagonals n = 0..30, flattened
Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, arXiv:1505.01389, 2015
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Columns k=0-4 give: A000007, A000012, A220097, A266734, A266735.
Main diagonal gives A000680.
First lower diagonal gives A267532.
Cf. A214015, A267480.

A(n,k) = Sum_{i=0..k} A267480(n,i).

A267480 Number T(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 5, 0, 1, 42, 47, 0, 1, 351, 1527, 641, 0, 1, 3113, 43910, 54987, 11389, 0, 1, 29003, 1302660, 3844840, 2059147, 248749, 0, 1, 280220, 40970298, 265777225, 285588543, 82025038, 6439075, 0, 1, 2782475, 1364750889, 19104601915, 37783672691, 19773928713, 3507289363, 192621953

Offset: 0

Alois P. Heinz, Jan 15 2016

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,      5;
  0, 1,     42,       47;
  0, 1,    351,     1527,       641;
  0, 1,   3113,    43910,     54987,     11389;
  0, 1,  29003,  1302660,   3844840,   2059147,   248749;
  0, 1, 280220, 40970298, 265777225, 285588543, 82025038, 6439075;

Alois P. Heinz, Rows n = 0..18, flattened
Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, arXiv:1505.01389, 2015
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Main diagonal gives A006902.
Row sums give A000680.
Cf. A267479, A267532.

T(n,0) = A267479(n,0), T(n,k) = A267479(n,k) - A267479(n,k-1) for k>0.

Sum_{k=0..n-1} T(n,k) = A267532(n).

A269042 Number of permutations of [2n] avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 132, 15767, 2190688, 370531683, 77182248916, 19835792076675, 6266271456118776, 2413632612087046844, 1120958514818713738544, 619918692943471064695593, 403190647991638511052901232, 304867528413299672718870216538, 265248225675908889875489731636920

Offset: 0

Alois P. Heinz, Feb 18 2016

nonn

			a(2) = 1: 4321.
a(3) = 132: 165432, 216543, 261543, 265143, 265413, 265431, 316542, ..., 653412, 653421, 654132, 654213, 654231, 654312, 654321.

Alois P. Heinz, Table of n, a(n) for n = 0..30

Cf. A010050, A214015, A267532, A269021.

h:= proc(l) (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(
      l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n))(nops(l))
    end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> `if`(n=0, 0, g(2*n, n-1, [])):
seq(a(n), n=0..15);

h[l_] := Function[n, Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], { k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]][Length[l]];
g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Table[1, {n}]]]^2, If[i < 1, 0, Sum[g[n - i*j, i-1, Join[l, Table[i, {j}]]], {j, 0, n/i}]]];
a[n_] := If[n == 0, 0, g[2n, n-1, {}]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 01 2017, translated from Maple *)

a(n) = (2n)! - A269021(n).
a(n) = A214015(2n,n-1) for n>0.
a(n) ~ (2*n)!. - Vaclav Kotesovec, Mar 26 2016

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A267479 Number A(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A267480 Number T(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A269042 Number of permutations of [2n] avoiding the pattern 12...n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula