cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A214015 Number of permutations A(n,k) in S_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, 2, 1, 0, 1, 1, 2, 5, 1, 0, 1, 1, 2, 6, 14, 1, 0, 1, 1, 2, 6, 23, 42, 1, 0, 1, 1, 2, 6, 24, 103, 132, 1, 0, 1, 1, 2, 6, 24, 119, 513, 429, 1, 0, 1, 1, 2, 6, 24, 120, 694, 2761, 1430, 1, 0, 1, 1, 2, 6, 24, 120, 719, 4582, 15767, 4862, 1, 0
Offset: 0

Views

Author

Alois P. Heinz, Jul 01 2012

Keywords

Comments

A(n,k) is also the sum of the squares of numbers of standard Young tableaux (SYT) of height <= k over all partitions of n.
This array is a larger and reflected version of A047888.
Column k>1 is asymptotic to (Product_{j=1..k} j!) * k^(2*n + k^2/2) / (Pi^((k-1)/2) * 2^((k-1)*(k+2)/2) * n^((k^2-1)/2)). - Vaclav Kotesovec, Sep 10 2014

Examples

			A(4,2) = 14 because 14 permutations of {1,2,3,4} do not contain an increasing subsequence of length > 2: 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.  Permutation 1423 is not counted because it contains the noncontiguous increasing subsequence 123.
A(4,2) = 14 = 2^2 + 3^2 + 1^2 because the partitions of 4 with <= 2 parts are [2,2], [3,1], [4] with 2, 3, 1 standard Young tableaux, respectively:
  +------+  +------+  +---------+  +---------+  +---------+  +------------+
  | 1  3 |  | 1  2 |  | 1  3  4 |  | 1  2  4 |  | 1  2  3 |  | 1  2  3  4 |
  | 2  4 |  | 3  4 |  | 2 .-----+  | 3 .-----+  | 4 .-----+  +------------+
  +------+  +------+  +---+        +---+        +---+
Square array A(n,k) begins:
  1,  1,   1,    1,    1,    1,    1,    1, ...
  0,  1,   1,    1,    1,    1,    1,    1, ...
  0,  1,   2,    2,    2,    2,    2,    2, ...
  0,  1,   5,    6,    6,    6,    6,    6, ...
  0,  1,  14,   23,   24,   24,   24,   24, ...
  0,  1,  42,  103,  119,  120,  120,  120, ...
  0,  1, 132,  513,  694,  719,  720,  720, ...
  0,  1, 429, 2761, 4582, 5003, 5039, 5040, ...

Links

Crossrefs

Columns k=0-10 give: A000007, A000012, A000108, A005802, A047889, A047890, A052399, A072131, A072132, A072133, A072167.
Differences between A000142 and columns k=0-9 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.
Main diagonal and first lower diagonal give: A000142, A033312.
A(2n,n-1) gives A269042(n) for n>0.
Cf. A047887, A047888, A182172, A208447, A214152, A267479.

Programs

  • Maple
    h:= proc(l) local n; n:=nops(l); 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)
    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, k)-> `if`(k>=n, n!, g(n, k, [])):
seq(seq(A(n, d-n), n=0..d), d=0..14);
  • Mathematica
    h[l_] := With[{n = Length[l]}, Sum[i, {i, 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}]];
g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]];
A[n_, k_] := If[k >= n, n!, g[n, k, {}]];
Table [Table [A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)

A267532 Number of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length < n.

Original entry on oeis.org

0, 0, 1, 43, 1879, 102011, 7235651, 674641325, 81537026047, 12498099730471, 2375632826877259, 548818073236649129, 151476182218777630655, 49229890784448694885163, 18608906461974462064310179, 8094874797394331233877338741, 4015057931973886657462193434111
Offset: 0

Views

Author

Alois P. Heinz, Jan 16 2016

Keywords

Comments

Or number of words on {1,1,2,2,...,n,n} avoiding the pattern 12...n.

Examples

			a(2) = 1: 2211.
a(3) = 43: 113322, 131322, 133122, 133212, 133221, 211332, 213132, 213312, 213321, 221133, 221313, 221331, 223113, 223131, 223311, 231132, 231312, 231321, 232113, 232131, 232311, 233112, 233121, 233211, 311322, 313122, 313212, 313221, 321132, 321312, 321321, 322113, 322131, 322311, 323112, 323121, 323211, 331122, 331212, 331221, 332112, 332121, 332211.

Links

Crossrefs

Cf. A000079, A000142, A000680, A006902, A010050, A267479, A267480, A269042.
Column k=2 of A269129.

Programs

  • Maple
    b:= proc(n) option remember; `if`(n<3, [1$2, 5][n+1], (
      (n^3+n^2-7*n+4)*b(n-1)-2*(2*n-3)*(n-1)^3*b(n-2))/(n-2))
    end:
a:= n-> (2*n)!/(2^n)-b(n):
seq(a(n), n=0..20);

Formula

a(n) = (2*n)! * ( 1/(2^n) - Sum_{k=0..n} (-1)^k * C(n,k) / (n+k)! ).
a(n) = A000680(n) - A006902(n).
a(n) = A267479(n,n-1) for n>0.
a(n) = Sum_{k=0..n-1} A267480(n,k).

A269021 Number of permutations of [2n] containing an increasing subsequence of length n.

Original entry on oeis.org

1, 2, 23, 588, 24553, 1438112, 108469917, 9996042284, 1086997811325, 136102249609224, 19269396089593156, 3042212958893941456, 529708789768374664407, 100813134967124531098768, 20816198414187782633783462, 4634136282168760818748363080
Offset: 0

Views

Author

Alois P. Heinz, Feb 17 2016

Keywords

Examples

			a(1) = 2: 12, 21.
a(2) = 23: all 4! permutations of {1,2,3,4} with the exception of 4321.

Links

Crossrefs

Cf. A010050, A214152, A269042.

Programs

  • Maple
    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, 1, (2*n)!-g(2*n, n-1, [])):
seq(a(n), n=0..16);
  • Mathematica
    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, 1, (2n)! - g[2n, n-1, {}]];
Table[a[n], {n, 0, 16}] (* Jean-François Alcover, Apr 01 2017, translated from Maple *)

Formula

a(n) = A214152(2n,n).
a(n) = (2n)! - A269042(n).
a(n) ~ 16^n * (n-1)! / (Pi * exp(2)). - Vaclav Kotesovec, Mar 27 2016
Conjectured recurrence: -64*(1 + n)^2*(2 + n)^2*(3 + n)*(1 + 2*n)^2*(3 + 2*n)^2*(5 + 2*n)^2*(549760 + 3266000*n + 7264534*n^2 + 8663374*n^3 + 6333869*n^4 + 3012795*n^5 + 952323*n^6 + 198469*n^7 + 26156*n^8 + 1968*n^9 + 64*n^10)*a(n) + 16*(2 + n)^2*(3 + n)*(3 + 2*n)^2*(5 + 2*n)^2*(-5543040 - 487964*n + 78563984*n^2 + 229526554*n^3 + 325846005*n^4 + 284054698*n^5 + 165789363*n^6 + 67385886*n^7 + 19359535*n^8 + 3917758*n^9 + 545913*n^10 + 49788*n^11 + 2672*n^12 + 64*n^13)*a(n+1) - 4*(3 + n)*(5 + 2*n)^2*(-250467360 - 946158512*n - 562569136*n^2 + 3271711596*n^3 + 9313604242*n^4 + 12741784568*n^5 + 11118771121*n^6 + 6753094929*n^7 + 2966908118*n^8 + 959068672*n^9 + 228837227*n^10 + 39928763*n^11 + 4969164*n^12 + 419248*n^13 + 21568*n^14 + 512*n^15)*a(n+2) + 2*(-1300242000 - 6360099840*n - 10812498240*n^2 - 778719870*n^3 + 27672902302*n^4 + 55047935941*n^5 + 60004107039*n^6 + 43766004538*n^7 + 22820793074*n^8 + 8747566435*n^9 + 2488583381*n^10 + 523718876*n^11 + 80260596*n^12 + 8677944*n^13 + 624800*n^14 + 26752*n^15 + 512*n^16)*a(n+3) - 3*(4 + n)*(8 + 3*n)*(10 + 3*n)*(-15900 - 61278*n - 68928*n^2 + 48699*n^3 + 204716*n^4 + 233810*n^5 + 143536*n^6 + 52389*n^7 + 11324*n^8 + 1328*n^9 + 64*n^10)*a(n+4) = 0. - Manuel Kauers and Christoph Koutschan, Mar 01 2023
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.