A208447 -id:A208447 - cp's OEIS frontend

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.

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

Alois P. Heinz, Jul 01 2012

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

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

Alois P. Heinz, Antidiagonals n = 0..70, flattened
Wikipedia, Longest increasing subsequence problem
Wikipedia, Young tableau

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.

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

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

A306100 Square array T(n,k) = number of plane partitions of n with parts colored in (at most) k colors; n >= 0, k >= 0; read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 10, 6, 0, 1, 4, 21, 34, 13, 0, 1, 5, 36, 102, 122, 24, 0, 1, 6, 55, 228, 525, 378, 48, 0, 1, 7, 78, 430, 1540, 2334, 1242, 86, 0, 1, 8, 105, 726, 3605, 8964, 11100, 3690, 160, 0, 1, 9, 136, 1134, 7278, 25980, 56292, 47496, 11266, 282, 0

Offset: 0

M. F. Hasler, Sep 22 2018

			The array starts:
  [1  1    1     1     1      1 ...] = A000012
  [0  1    2     3     4      5 ...] = A001477
  [0  3   10    21    36     55 ...] = A014105
  [0  6   34   102   228    430 ...] = A067389
  [0 13  122   525  1540   3605 ...]
  [0 24  378  2334  8964  25980 ...]
  [0 48 1242 11100 56292 203280 ...]

Alois P. Heinz, Antidiagonals n = 0..50, flattened
OEIS wiki, Plane partitions.
Wikipedia, Plane partition.

Columns k=0-5 give: A000007, A000219, A306099, A306093, A306094, A306095.
See A306101 for a variant.
Cf. A091298, A208447, A001477, A014105, A067389.

A306100(n,k)=sum(j=1,n,A091298(n,j)*k^j)

T(n,k) = Sum_{j=0..n} A091298(n,j)*k^j, assuming A091298(n,0) = A000007(n).

T(n,k) = Sum_{i=0..k} C(k,i) * A319600(n,i). - Alois P. Heinz, Sep 28 2018

Edited by Alois P. Heinz, Sep 26 2018

A306093 Number of plane partitions of n where parts are colored in 3 colors.

Original entry on oeis.org

1, 3, 21, 102, 525, 2334, 11100, 47496, 210756, 886080, 3759114, 15378051, 63685767, 255417357, 1030081827, 4078689249, 16150234665, 62991117084, 245948154087, 947944122906, 3653360869998, 13946363438502, 53149517598207, 200994216333375, 759191650345380

Offset: 0

M. F. Hasler, Sep 22 2018

nonn

a(0) = 1 corresponds to the empty sum, in which all terms are colored in one among three given colors, since there is no term at all.

			For n = 1, there is only the partition [1], which can be colored in any of the three colors, whence a(1) = 3.
For n = 2, there are the partitions [2], [1,1] and [1;1]. Adding colors, this yields a(2) = 3 + 9 + 9 = 21 distinct possibilities.

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

Cf. A091298, A208447.

Column 3 of A306100 and A306101. See A306099 for column 2, A306094 .. A306096 for columns 4 .. 6.

PARI
```
a(n)=sum(k=1,n,A091298(n,k)*3^k,!n)
```

a(n) = Sum_{k=1..n} A091298(n,k)*3^k.

a(12) corrected and a(13)-a(24) added by Alois P. Heinz, Sep 24 2018

A306099 Number of plane partitions of n where parts are colored in 2 colors.

Original entry on oeis.org

1, 2, 10, 34, 122, 378, 1242, 3690, 11266, 32666, 94994, 267202, 754546, 2072578, 5691514, 15364290, 41321962, 109634586, 290048746, 758630698, 1977954706, 5111900410, 13161995010, 33645284962, 85727394018, 217042978882, 547750831210, 1375147078146, 3441516792442

Offset: 0

M. F. Hasler and Rick L. Shepherd, following an idea from David S. Newman, Sep 22 2018

nonn

a(0) = 1 corresponds to the empty sum, in which all terms are colored in one among two given colors, since there is no term at all.

			For n = 1, there is only the partition [1], which can be colored in any of the two colors, whence a(1) = 2.
For n = 2, there are the partitions [2], [1,1] and [1;1]. Adding colors, this yields a(2) = 2 + 4 + 4 = 10 distinct possibilities.

Alois P. Heinz, Table of n, a(n) for n = 0..50
OEIS wiki: Plane partitions
Wikipedia, Plane partition

Cf. A091298, A208447.

Column 2 of A306100 and A306101. See A306093 .. A306096 for columns 3 .. 6.

PARI
```
a(n)=!n+sum(k=1,n,A091298(n,k)<
				
```

a(n) = Sum_{k=1..n} A091298(n,k)*2^k.

a(12) corrected and a(13)-a(28) added by Alois P. Heinz, Sep 24 2018

A306101 Square array T(n,k) = number of plane partitions of n with parts colored in (at most) k colors; n, k >= 1; read by antidiagonals.

Original entry on oeis.org

1, 2, 3, 3, 10, 6, 4, 21, 34, 13, 5, 36, 102, 122, 24, 6, 55, 228, 525, 378, 48, 7, 78, 430, 1540, 2334, 1242, 86, 8, 105, 726, 3605, 8964, 11100, 3690, 160, 9, 136, 1134, 7278, 25980, 56292, 47496, 11266, 282, 10, 171, 1672, 13237, 62574, 203280, 316388, 210756, 32666, 500, 11, 210, 2358, 22280, 132258, 586878, 1417530

Offset: 1

M. F. Hasler, Sep 22 2018

One could have included a row 0 with all 1's, since there is exactly one partition of n = 0, the empty sum, for which all terms (since there are none) are colored in one among k colors.

			The array starts:
  [      1       2       3       4       5 ...] = A000027
  [      3      10      21      36      55 ...] = A014105
  [      6      34     102     228     430 ...] = A067389
  [     13     122     525    1540    3605 ...]
  [     24     378    2334    8964   25980 ...]
  [     48    1242   11100   56292  203280 ...]
   A000219 A306099 A306093 A306094 A306094
For concrete examples, see A306099 and A306093.

Alois P. Heinz, Antidiagonals n = 1..50, flattened

Cf. A091298, A208447, A000219, A000027, A014105, A067389.
See A306100 for a variant.
Cf. A000219, A306099, A306093, A306094, A306095 for columns 1..5.

A306101(n,k)=sum(j=1,n,A091298(n,j)*k^j)

T(n,k) = Sum_{j=1..n} A091298(n,j)*k^j.

A306094 Number of plane partitions of n where parts are colored in (at most) 4 colors.

Original entry on oeis.org

1, 4, 36, 228, 1540, 8964, 56292, 316388, 1857028, 10301892, 57884132, 312915172, 1720407492, 9132560068, 48898964964, 256790538660, 1350883911620, 6992031608260, 36296271612324, 185785685287076, 952221494828996, 4831039856692356, 24489621255994276

Offset: 0

M. F. Hasler, Sep 22 2018

nonn

a(0) = 1 corresponds to the empty sum, in which all terms are colored in one among four given colors, since there is no term at all.

			For n = 1, there is only the partition [1], which can be colored in any of the four colors, whence a(1) = 4.
For n = 2, there are the partitions [2], [1,1] and [1;1]. Adding colors, this yields a(2) = 4 + 16 + 16 = 36 distinct possibilities.

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

Cf. A091298, A208447.

Column 4 of A306100 and A306101. See A306099 and A306093 for columns 2 and 3.

PARI
```
a(n)=!n+sum(k=1,n,A091298(n,k)*4^k)
```

a(n) = Sum_{k=1..n} A091298(n,k)*4^k.

a(12) corrected and a(13)-a(22) added by Alois P. Heinz, Sep 24 2018

A306095 Number of plane partitions of n where parts are colored in (at most) 5 colors.

Original entry on oeis.org

1, 5, 55, 430, 3605, 25980, 203280, 1417530, 10373080, 71595830, 501688880, 3376856755, 23181027055, 153326091805, 1024829902855, 6713038952355, 44092634675905, 284723995000530, 1845944380173205, 11791816763005330, 75485171060740630, 478105767714603130

Offset: 0

M. F. Hasler, Sep 22 2018

nonn

a(0) = 1 corresponds to the empty sum, in which all terms are colored in one among five given colors, since there is no term at all.

			For n = 1, there is only the partition [1], which can be colored in any of the five colors, whence a(1) = 5.
For n = 2, there are the partitions [2], [1,1] and [1;1]. Adding colors, this yields a(2) = 5 + 25 + 25 = 55 distinct possibilities.

M. F. Hasler, Table of n, a(n) for n = 0..50

Cf. A091298, A208447.

Column 5 of A306100 and A306101. See A306099, A306093, A306094, A306096 for columns 2, 3, 4 and 6.

PARI
```
a(n)=!n+sum(k=1,n,A091298(n,k)*5^k)
```

a(n) = Sum_{k=1..n} A091298(n,k)*5^k.

A306096 Number of plane partitions of n where parts are colored in (at most) 6 colors.

Original entry on oeis.org

1, 6, 78, 726, 7278, 62574, 586878, 4889166, 42892710, 354335982, 2976581670, 23990771094, 197564663094, 1565310230790, 12548473437822, 98526949264374, 776195574339102, 6008457242324814, 46729763436714126, 357901583160822990, 2748384845416097718

Offset: 0

M. F. Hasler, Oct 16 2018

nonn

a(0) = 1 corresponds to the empty sum, in which all terms are colored in one among six given colors, since there is no term at all.

			For n = 1, there is only the partition [1], which can be colored in any of the six colors, whence a(1) = 6.
For n = 2, there are the partitions [2], [1,1] and [1;1]. Adding colors, this yields a(2) = 6 + 36 + 36 = 78 distinct possibilities.

M. F. Hasler, Table of n, a(n) for n = 0..50

Cf. A091298, A208447.

Column 6 of A306100 and A306101. See A306099, A306093, A306094, A306095 for columns 2, 3, 4 and 5.

PARI
```
a(n)=sum(k=1,n,A091298(n,k)*6^k,!n)
```

a(n) = Sum_{k=1..n} A091298(n,k)*6^k, for n > 0.

A129627 Sum of the 4th powers of the degrees of irreducible representations of S_n, the symmetric group on n letters.

Original entry on oeis.org

1, 2, 18, 180, 3060, 101160, 3807720, 174986280, 10699554600, 927701102160, 95030461809360, 10905467528783520, 1431935974242053280, 222906109589537774400, 42471495822490670295360, 9447237366839585591438160, 2329156499421828313498781520

Offset: 1

Dmitrii Pasechnik, May 30 2007

nonn

a(n) is also the sum of the fourth powers of the numbers of standard Young tableaux over all partitions of n. - Thotsaporn Thanatipanonda, Feb 25 2012

Alois P. Heinz, Table of n, a(n) for n = 1..60
Thotsaporn Thanatipanonda, Maple code for A129627

Cf. A000142, A000085.

Column k=4 of A208447. - Alois P. Heinz, Feb 28 2012

List([1..20],n->Sum(List(Irr(CharacterTable("Symmetric",n)), x->x[1]^4)));

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_, k_, l_] := g[n, i, l, k] = If[n == 0, h[l]^k, If[i < 1, 0, g[n, i - 1, k, l] + If[i > n, 0, g[n - i, i, k, Append[l, i]]]]];
a[n_] := If[n == 0, 1, g[n, n, 4, {}]];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, May 18 2017, after Alois P. Heinz *)

A130721 Sum of the cubes of the number of standard Young tableaux over all partitions of n.

Original entry on oeis.org

1, 1, 2, 10, 64, 596, 8056, 130432, 2534960, 59822884, 1718480368, 56754444440, 2110577206816, 87981286785328, 4129351961475872, 218382856010529472, 12813477368159567200, 822337333595479929044, 57213666993723455063392, 4305630141314873304140008

Offset: 0

David A. Madore, Jul 03 2007

nonn

The sum of the zeroth power of the number f(p) of standard Young tableaux gives the partition function (A000041), the sum of the first power of f(p) gives the involution function (A000085), the sum of the squares of f(p) gives the factorial function (A000142), so this sequence is the natural one after them.

			a(4) = 1^3 + 3^3 + 2^3 + 3^3 + 1^3 because the five partitions of 4 (namely 4, 3+1, 2+2, 2+1+1, 1+1+1+1) have respectively 1, 3, 2, 3, 1 standard Young tableaux.

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

Cf. A000041, A000085, A000142.

Column k=3 of A208447.

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_, k_, l_] := g[n, i, l, k] = If[n == 0, h[l]^k, If[i < 1, 0, g[n, i - 1, k, l] + If[i > n, 0, g[n - i, i, k, Append[l, i]]]]];
a[n_] := If[n == 0, 1, g[n, n, 3, {}]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 18 2017, after Alois P. Heinz *)

For p a partition of n, let f(p) be the number of standard Young tableaux with shape p. Then a(n) = sum(f(p)^3) where the sum ranges over all partitions p of n.

More terms from Alois P. Heinz, Feb 26 2012

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A306100 Square array T(n,k) = number of plane partitions of n with parts colored in (at most) k colors; n >= 0, k >= 0; read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A306093 Number of plane partitions of n where parts are colored in 3 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A306099 Number of plane partitions of n where parts are colored in 2 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A306101 Square array T(n,k) = number of plane partitions of n with parts colored in (at most) k colors; n, k >= 1; read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A306094 Number of plane partitions of n where parts are colored in (at most) 4 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A306095 Number of plane partitions of n where parts are colored in (at most) 5 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI