A047874 -id:A047874 - cp's OEIS frontend

A245666 Number of permutations of length n with longest increasing subsequence of length 10.

1, 100, 5941, 275705, 11110464, 410474625, 14353045401, 484748595081, 16029615164446, 523952747921310, 17044414451764396, 554568496974014588, 18113988555378974988, 595604303387826752023, 19755504320385394380715, 662039152774864970449891

Offset: 10

Alois P. Heinz, Jul 28 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 10..60

Column k=10 of A047874.

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-> g(n-10, min(n-10, 10), [10]):
seq(a(n), n=10..30);

A026845 Sum_{mu a partition of n} (f^mu/n!)^{-2} where f^mu is the number of standard Young tableaux of shape mu.

Original entry on oeis.org

1, 8, 81, 1424, 32152, 1144937, 53178768, 3360267976, 268737034880, 26735641360265, 3222856389284352, 463078022054303432, 78131995260953112576, 15295767841794798044432, 3438384401028669096232665, 879589866427669147125523584, 254053056142392070125392290952

Offset: 1

Bruce E. Sagan, Apr 06 2002

nonn

Arises from counting coverings of a genus g=2 Riemann surface - expansion of generating function A_g(q) = sum_{n>=0} a_{n,g} q^n where a_{n,g} = sum_{mu a partition of n} (f^mu/n!)^{2-2g}; note that A_0(q) = e^q and A_1(q) = prod_{i>=1} 1/(1-q^i).

Alois P. Heinz, Table of n, a(n) for n = 1..60

Cf. A047874. - Wouter Meeussen, Sep 30 2010

(* version 4.0 *) Needs["DiscreteMath`Combinatorica`"]; Table[Tr[(n!/ (NumberOfTableaux /@ Partitions[n]))^2],{n,20}] (* Wouter Meeussen, Sep 30 2010 *)

Terms 8 to 20 added by Wouter Meeussen, Sep 30 2010

A366503 Triangle read by rows: T(n,k) = number of permutations of (1, 2, ..., n) with longest monotonic subsequence of length k (1<=k<=n).

Original entry on oeis.org

1, 0, 2, 0, 4, 2, 0, 4, 18, 2, 0, 0, 86, 32, 2, 0, 0, 306, 362, 50, 2, 0, 0, 882, 3242, 842, 72, 2, 0, 0, 1764, 24564, 12210, 1682, 98, 2, 0, 0, 1764, 163872, 161158, 32930, 3026, 128, 2, 0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2

Offset: 1

Douglas Boffey, Oct 12 2023

			Triangle begins:
  1;
  0, 2;
  0, 4,    2;
  0, 4,   18,     2;
  0, 0,   86,    32,     2;
  0, 0,  306,   362,    50,    2;
  0, 0,  882,  3242,   842,   72,  2;
  0, 0, 1764, 24564, 12210, 1682, 98, 2;
  ...
The T(4, 2) = 4 permutations are: 2,1,4,3; 2,4,1,3; 3,1,4,2; 3,4,1,2.

Douglas Boffey, C++ program used to generate the sequence

Row sums are A000142.

Cf. A047874.

A331883 The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.

Original entry on oeis.org

0, 1, 1, 5, 26, 132, 834, 6477, 56242

Offset: 1

Ildar Gainullin, Jan 30 2020

Only permutations whose longest increasing subsequence is at most n/2 need to be considered.

			a(3) = 1 because the only permutation whose longest increasing subsequence is 1 is [3,2,1] and this contains two disjoint increasing subsequences of length 1.
The a(4) = 5 permutations are:
  [2,1,4,3],
  [2,4,1,3],
  [3,1,4,2],
  [3,4,1,2],
  [4,3,2,1].

Wikipedia, Longest increasing subsequence problem

Cf. A047874, A047887, A167995.

A380611 Irregular triangle read by rows: T(r,c) is the product of the number of standard Young tableaux (A117506) and the number of semistandard Young tableaux (A262030) for partitions of r.

Original entry on oeis.org

1, 1, 3, 1, 10, 16, 1, 35, 135, 40, 45, 1, 126, 896, 875, 756, 375, 96, 1, 462, 5250, 10206, 8400, 2450, 14336, 2800, 875, 1701, 175, 1, 1716, 28512, 90552, 74250, 65856, 257250, 48000, 74088, 55566, 102900, 8100, 10976, 5488, 288, 1, 6435, 147147, 686400, 567567, 931392, 3244032, 606375, 194040, 2910600, 1448832, 2673000, 202125, 666792, 846720, 1029000, 491520, 19845, 24696, 65856, 14400, 441, 1

Offset: 0

Wouter Meeussen, Jan 28 2025

Partitions are generated in reverse lexicographic order.
Remark that A262030 uses Abramowitz-Stegun (A-St) order.
Sum of row r equals r^r for r > 0 (Robinson-Schensted correspondence).

			Triangle begins:
    1;
    1;
    3,    1;
   10,   16,     1;
   35,  135,    40,   45,    1;
  126,  896,   875,  756,  375,    96,    1;
  462, 5250, 10206, 8400, 2450, 14336, 2800, 875, 1701, 175, 1;
  ...
Fourth row is 1*35, 3*45, 2*20, 3*15, 1*1 with sum 256 = 4^4.

Wikipedia, Young tableau

Row sums give A000312.
Row lengths give A000041.
Leftmost column gives A088218.
Cf. A047874, A059304, A365643, A262030, A117506.

Needs["Combinatorica`"];
hooklength[par_?PartitionQ]:=Table[Count[par,q_/;q>=j]+1-i+par[[i]]-j,{i,Length[par]},{j,par[[i]]}];
countSYT[par_?PartitionQ]:=Tr[par]!/Times@@Flatten[hooklength[par]];
content[par_?PartitionQ]:=Table[j-i,{i,Length[par]},{j,par[[i]]}];
countSSYT[par_?PartitionQ,t_Integer_]:=Times@@((t+Flatten[content[par]])/Flatten[hooklength[par]]);
Table[countSYT[par] countSSYT[par,n],{n,8},{par,IntegerPartitions[n]}]

cp's OEIS Frontend

A245666 Number of permutations of length n with longest increasing subsequence of length 10.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A026845 Sum_{mu a partition of n} (f^mu/n!)^{-2} where f^mu is the number of standard Young tableaux of shape mu.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A366503 Triangle read by rows: T(n,k) = number of permutations of (1, 2, ..., n) with longest monotonic subsequence of length k (1<=k<=n).

Views

Author

Keywords

Examples

Links

Crossrefs

A331883 The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A380611 Irregular triangle read by rows: T(r,c) is the product of the number of standard Young tableaux (A117506) and the number of semistandard Young tableaux (A262030) for partitions of r.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica