A212915 -id:A212915 - cp's OEIS frontend

A182172 Number A(n,k) of standard Young tableaux of n cells and height <= 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, 3, 1, 0, 1, 1, 2, 4, 6, 1, 0, 1, 1, 2, 4, 9, 10, 1, 0, 1, 1, 2, 4, 10, 21, 20, 1, 0, 1, 1, 2, 4, 10, 25, 51, 35, 1, 0, 1, 1, 2, 4, 10, 26, 70, 127, 70, 1, 0, 1, 1, 2, 4, 10, 26, 75, 196, 323, 126, 1, 0, 1, 1, 2, 4, 10, 26, 76, 225, 588, 835, 252, 1, 0

Offset: 0

Alois P. Heinz, Apr 16 2012

Also the number A(n,k) of standard Young tableaux of n cells and <= k columns.

A(n,k) is also the number of n-length words w over a k-ary alphabet {a1,a2,...,ak} such that for every prefix z of w we have #(z,a1) >= #(z,a2) >= ... >= #(z,ak), where #(z,x) counts the letters x in word z. The A(4,4) = 10 words of length 4 over alphabet {a,b,c,d} are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca, abcd.

			A(4,2) = 6, there are 6 standard Young tableaux of 4 cells and height <= 2:
  +------+  +------+  +---------+  +---------+  +---------+  +------------+
  | 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,   1, ...
  0,  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,  2,   2,   2,   2,   2,   2,   2, ...
  0,  1,  3,   4,   4,   4,   4,   4,   4, ...
  0,  1,  6,   9,  10,  10,  10,  10,  10, ...
  0,  1, 10,  21,  25,  26,  26,  26,  26, ...
  0,  1, 20,  51,  70,  75,  76,  76,  76, ...
  0,  1, 35, 127, 196, 225, 231, 232, 232, ...
  0,  1, 70, 323, 588, 715, 756, 763, 764, ...

Alois P. Heinz, Antidiagonals n = 0..80, flattened
Wikipedia, Young tableau

Columns k=0-12 give: A000007, A000012, A001405, A001006, A005817, A049401, A007579, A007578, A007580, A212915, A212916, A229053, A229068.
Main diagonal gives A000085.
A(2n,n) gives A293128.
Cf. A047884, A049400, A226873, A240608.

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:= proc(n, i, l) option remember;
      `if`(n=0, h(l), `if`(i<1, 0, `if`(i=1, h([l[], 1$n]),
        g(n, i-1, l) +`if`(i>n, 0, g(n-i, i, [l[], i])))))
    end:
A:= (n, k)-> g(n, k, []):
seq(seq(A(n, d-n), n=0..d), d=0..15);

h[l_List] := Module[{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_List] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Array[1&, n]]], g [n, i-1, l] + If[i > n, 0, g[n-i, i, Append[l, i]]]]]];
a[n_, k_] := g[n, k, {}];
Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 06 2013, translated from Maple *)

Conjecture: A(n,k) ~ k^n/Pi^(k/2) * (k/n)^(k*(k-1)/4) * Product_{j=1..k} Gamma(j/2). - Vaclav Kotesovec, Sep 12 2013

A293739 Number of multisets of nonempty words with a total of n letters over nonary alphabet such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Original entry on oeis.org

1, 1, 3, 7, 20, 54, 164, 500, 1630, 5472, 19256, 70121, 265723, 1041184, 4225484, 17689505, 76392933, 339283021, 1548592471, 7246210567, 34725853445, 170096822940, 850715642495, 4337263437693, 22519434992230, 118916581795167, 638088881489144, 3475474084479428

Offset: 0

Alois P. Heinz, Oct 15 2017

nonn

This sequence differs from A293110 first at n=10.

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

Column k=9 of A293108.

Cf. A212915, A293110, A293748.

G.f.: Product_{j>=1} 1/(1-x^j)^A212915(j).

a(n) ~ c * 9^n / n^18, where c = 978644175524508179.918397627321774... - Vaclav Kotesovec, Dec 19 2020

A293748 Number of sets of nonempty words with a total of n letters over nonary alphabet such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Original entry on oeis.org

1, 1, 2, 6, 15, 45, 136, 430, 1415, 4845, 17234, 63497, 242720, 958754, 3916799, 16493831, 71586602, 319336319, 1463096806, 6869041635, 33014439494, 162130576595, 812715417240, 4151894763819, 21595739171153, 114222733829429, 613789962584588, 3347502798880170

Offset: 0

Alois P. Heinz, Oct 15 2017

nonn

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

Column k=9 of A293112.

Cf. A212915, A293739.

G.f.: Product_{j>=1} (1+x^j)^A212915(j).

A229053 Number of standard Young tableaux of n cells and height <= 11.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140151, 568491, 2390311, 10347911, 46191551, 211671999, 996269310, 4801547628, 23695885170, 119481280210, 615372604033, 3232009497979, 17302866542177, 94301143232321, 522945331559246, 2947729723188352

Offset: 0

Vaclav Kotesovec, Sep 12 2013

nonn

Vaclav Kotesovec and Alois P. Heinz, Table of n, a(n) for n = 0..400
Index entries for sequences related to Young tableaux.

Cf. A182172, A001405 (k=2), A001006 (k=3), A005817 (k=4), A049401 (k=5), A007579 (k=6), A007578 (k=7), A007580 (k=8), A212915 (k=9), A212916 (k=10).
Column k=11 of A182172.
Cf. A000085.

RecurrenceTable[{-10395 (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) a[-6+n]-3 (-4+n) (-3+n) (-2+n) (-1+n) (28701+2578 n) a[-5+n]+(-3+n) (-2+n) (-1+n) (331317+74458 n+3319 n^2) a[-4+n]+2 (-2+n) (-1+n) (546120+154023 n+11843 n^2+270 n^3) a[-3+n]-(-1+n) (1857231+1090536 n+149299 n^2+7472 n^3+125 n^4) a[-2+n]+(-2755377-1658520 n-265085 n^2-17752 n^3-535 n^4-6 n^5) a[-1+n]+(10+n) (18+n) (24+n) (28+n) (30+n) a[n]==0,a[1]==1,a[2]==2,a[3]==4,a[4]==10,a[5]==26,a[6]==76}, a, {n, 20}]

Recurrence: (n+10)*(n+18)*(n+24)*(n+28)*(n+30)*a(n) = (6*n^5 + 535*n^4 + 17752*n^3 + 265085*n^2 + 1658520*n + 2755377)*a(n-1) + (n-1)*(125*n^4 + 7472*n^3 + 149299*n^2 + 1090536*n + 1857231)*a(n-2) - 2*(n-2)*(n-1)*(270*n^3 + 11843*n^2 + 154023*n + 546120)*a(n-3) - (n-3)*(n-2)*(n-1)*(3319*n^2 + 74458*n + 331317)*a(n-4) + 3*(n-4)*(n-3)*(n-2)*(n-1)*(2578*n + 28701)*a(n-5) + 10395*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*a(n-6).
a(n) ~ 40186125/1024 * 11^(n+55/2)/(Pi^(5/2)*n^(55/2)).
Conjecture: a(n) ~ k^n/Pi^(k/2)*(k/n)^(k*(k-1)/4) * prod(j=1,k,Gamma(j/2)).

A217321 Number of self-inverse permutations in S_n with longest increasing subsequence of length 9.

Original entry on oeis.org

1, 9, 89, 639, 4655, 30330, 198148, 1233743, 7694099, 46938514, 287070944, 1738940782, 10570927022, 64059763010, 389873574058, 2373799261605, 14522526860316, 89060416668016, 548932942208392, 3395326330414774, 21109553761623110, 131785019270029876

Offset: 9

Alois P. Heinz, Sep 30 2012

nonn

Also the number of Young tableaux with n cells and 9 rows.

Alois P. Heinz, Table of n, a(n) for n = 9..350

Column k=9 of A047884.

Cf. A007580, A182172, A212915.

a(n) = A182172(n,9)-A182172(n,8) = A212915(n)-A007580(n).

A217322 Number of self-inverse permutations in S_n with longest increasing subsequence of length 10.

Original entry on oeis.org

1, 10, 109, 857, 6798, 48007, 338529, 2267425, 15164662, 98964444, 645978814, 4168541022, 26949303558, 173445855265, 1119737108943, 7224864497439, 46800745943134, 303692912870933, 1979556048016406, 12943419575576650, 85040314513698164, 560910092712436079

Offset: 10

Alois P. Heinz, Sep 30 2012

nonn

Also the number of Young tableaux with n cells and 10 rows.

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

Column k=10 of A047884.

Cf. A182172, A212915, A212916.

a(n) = A182172(n,10)-A182172(n,9) = A212916(n)-A212915(n).

A218262 Number of standard Young tableaux of n cells and height >= 10.

Original entry on oeis.org

1, 11, 121, 1001, 8086, 59228, 426673, 2946593, 20161558, 135303408, 904408398, 5995379358, 39727129830, 262629161094, 1739604051411, 11535387587595, 76763703224070, 512448824337780, 3436760740882050, 23151339236295810, 156789753069685500, 1067435349046248600

Offset: 10

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 10.

Alois P. Heinz, Table of n, a(n) for n = 10..300
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=10 of A182222.

Cf. A000085, A212915, A182172.

a(n) = A000085(n) - A212915(n) = A182172(n,n) - A182172(n,9).

A229068 Number of standard Young tableaux of n cells and height <= 12.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568503, 2390466, 10349340, 46204720, 211779200, 997134592, 4808141824, 23745792032, 119848119307, 618058083314, 3251373425356, 17442275104496, 95297400355320, 530067682582320, 2998503402985440

Offset: 0

Vaclav Kotesovec, Sep 12 2013

nonn

Conjecture: generally (for tableaux with height <= k), a(n) ~ k^n/Pi^(k/2) * (k/n)^(k*(k-1)/4) * Product_{j=1..k} Gamma(j/2); set k=12 for this sequence.

Vaclav Kotesovec and Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A182172, A001405 (k=2), A001006 (k=3), A005817 (k=4), A049401 (k=5), A007579 (k=6), A007578 (k=7), A007580 (k=8), A212915 (k=9), A212916 (k=10), A229053 (k=11).

Column k=12 of A182172.

RecurrenceTable[{-147456 (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) (12+n) a[-6+n]-110592 (-4+n) (-3+n) (-2+n) (-1+n) (29+2 n) a[-5+n]+256 (-3+n) (-2+n) (-1+n) (121272+32786 n+2343 n^2+49 n^3) a[-4+n]+128 (-2+n) (-1+n) (438597+90321 n+5391 n^2+98 n^3) a[-3+n]-16 (-1+n) (8718630+5347213 n+804616 n^2+49754 n^3+1372 n^4+14 n^5) a[-2+n]-8 (27335490+10162354 n+1206473 n^2+63328 n^3+1533 n^4+14 n^5) a[-1+n]+(11+n) (20+n) (27+n) (32+n) (35+n) (36+n) a[n]==0, a[1]==1, a[2]==2, a[3]==4, a[4]==10, a[5]==26, a[6]==76}, a, {n, 20}]

Recurrence: (n+11)*(n+20)*(n+27)*(n+32)*(n+35)*(n+36)*a(n) = 8*(14*n^5 + 1533*n^4 + 63328*n^3 + 1206473*n^2 + 10162354*n + 27335490)*a(n-1) + 16*(n-1)*(14*n^5 + 1372*n^4 + 49754*n^3 + 804616*n^2 + 5347213*n + 8718630)*a(n-2) - 128*(n-2)*(n-1)*(98*n^3 + 5391*n^2 + 90321*n + 438597)*a(n-3) - 256*(n-3)*(n-2)*(n-1)*(49*n^3 + 2343*n^2 + 32786*n + 121272)*a(n-4) + 110592*(n-4)*(n-3)*(n-2)*(n-1)*(2*n + 29)*a(n-5) + 147456*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n+12)*a(n-6).

a(n) ~ 602791875/128 * 12^(n+33)/(Pi^3*n^33).

cp's OEIS Frontend

A182172 Number A(n,k) of standard Young tableaux of n cells and height <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A293739 Number of multisets of nonempty words with a total of n letters over nonary alphabet such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A293748 Number of sets of nonempty words with a total of n letters over nonary alphabet such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Views

Author

Keywords

Links

Crossrefs

Formula

A229053 Number of standard Young tableaux of n cells and height <= 11.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A217321 Number of self-inverse permutations in S_n with longest increasing subsequence of length 9.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A217322 Number of self-inverse permutations in S_n with longest increasing subsequence of length 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A218262 Number of standard Young tableaux of n cells and height >= 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A229068 Number of standard Young tableaux of n cells and height <= 12.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula