A007580 -id:A007580 - 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

A293738 Number of multisets of nonempty words with a total of n letters over octonary 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, 5471, 19246, 70020, 264961, 1035540, 4187725, 17440159, 74817905, 329400093, 1487844185, 6873585346, 32460719143, 156315314070, 767106102127, 3828629444020, 19423438144438, 99998608025751, 522200287437179, 2762351298913471

Offset: 0

Alois P. Heinz, Oct 15 2017

nonn

This sequence differs from A293110 first at n=9.

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

Column k=8 of A293108.

Cf. A007580, A293110, A293747.

g:= proc(n) option remember; `if`(n<4, [1, 1, 2, 4][n+1],
      ((40*n^3+1084*n^2+8684*n+18480)*g(n-1) +16*(n-1)*
      (5*n^3+107*n^2+610*n+600)*g(n-2) -1024*(n-1)*(n-2)*
      (n+6)*g(n-3) -1024*(n-1)*(n-2)*(n-3)*(n+4)*g(n-4))
       /((n+7)*(n+12)*(n+15)*(n+16)))
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(g(d)
      *d, d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..35);

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

a(n) ~ c * 8^n / n^14, where c = 4485962145436.6348123684794... - Vaclav Kotesovec, Dec 19 2020

A293747 Number of sets of nonempty words with a total of n letters over octonary 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, 4844, 17224, 63397, 241968, 953213, 3879822, 16250333, 70050877, 309714232, 1404000641, 6506809837, 30813282963, 148741986670, 731495853897, 3657808596354, 18588011870288, 95841754173073, 501169433939670, 2654344778727646

Offset: 0

Alois P. Heinz, Oct 15 2017

nonn

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

Column k=8 of A293112.

Cf. A007580, A293738.

g:= proc(n) option remember; `if`(n<4, [1, 1, 2, 4][n+1],
      ((40*n^3+1084*n^2+8684*n+18480)*g(n-1) +16*(n-1)*
      (5*n^3+107*n^2+610*n+600)*g(n-2) -1024*(n-1)*(n-2)*
      (n+6)*g(n-3) -1024*(n-1)*(n-2)*(n-3)*(n+4)*g(n-4))
       /((n+7)*(n+12)*(n+15)*(n+16)))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*binomial(g(i), j), j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..35);

h[l_] := Function[n, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[ l[[k]] < j, 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]][ Length[l]];
g[n_, i_, l_] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Table[1, n]]], g[n, i - 1, l] + If[i > n, 0, g[n - i, i, Append[l, i]]]]]];
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1, k]*Binomial[g[i, k, {}], j], {j, 0, n/i}]]];
a[n_] := b[n, n, 8];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 06 2018, using code from A293112 *)

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

A049400 Partial sums of rows of A047884. Young Tableaux by height.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 6, 9, 10, 1, 10, 21, 25, 26, 1, 20, 51, 70, 75, 76, 1, 35, 127, 196, 225, 231, 232, 1, 70, 323, 588, 715, 756, 763, 764, 1, 126, 835, 1764, 2347, 2556, 2611, 2619, 2620, 1, 252, 2188, 5544, 7990, 9096, 9415, 9486, 9495, 9496, 1, 462, 5798, 17424, 27908, 33231, 35135, 35596

Offset: 1

Alford Arnold

			1;
1,  2;
1,  3,   4;
1,  6,   9,  10;
1, 10,  21,  25,  26;
1, 20,  51,  70,  75,  76;
1, 35, 127, 196, 225, 231, 232;
1, 70, 323, 588, 715, 756, 763, 764;

Seiichi Manyama, Rows n = 1..70, flattened (first 44 rows from Alois P. Heinz)
Index entries for sequences related to Young tableaux.

Cf. A000085, A007579, A007578, A007580, A049401, A293128.

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:
T:= (n, k)-> g(n, k, []):
seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Apr 16 2012

Accumulate /@ Table[ Plus @@ NumberOfTableaux /@ Reverse /@ Union[ Sort /@ (Compositions[n - m, m] + 1)], {n, 1, 12}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 29 2013, after Mathematica program for A047884 *)

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

A217328 Number of self-inverse permutations in S_n with longest increasing subsequence of length 8.

Original entry on oeis.org

1, 8, 71, 461, 3057, 18225, 109446, 628652, 3628517, 20538209, 116808172, 659078098, 3737763884, 21153403644, 120354760098, 685455514294, 3925104616303, 22535893275064, 130089736567064, 753604985013128, 4388755545268226, 25660332309744370, 150802834643569274

Offset: 8

Alois P. Heinz, Sep 30 2012

nonn

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

			a(8) = 1: 12345678.
a(9) = 8: 123456798, 123456879, 123457689, 123465789, 123546789, 124356789, 132456789, 213456789.

Alois P. Heinz, Table of n, a(n) for n = 8..400

Column k=8 of A047884.

Cf. A007578, A007580, A182172.

a(n) = A182172(n,8)-A182172(n,7) = A007580(n)-A007578(n).

A218269 Number of standard Young tableaux of n cells and height >= 9.

Original entry on oeis.org

1, 10, 100, 760, 5656, 38416, 257376, 1660416, 10640692, 67100072, 422374352, 2643349180, 16566306380, 103786892840, 652502735152, 4113403313016, 26057914447911, 165824119892086, 1061381766546172, 6832087071296824, 44260892997918920, 288574772339715376

Offset: 9

Alois P. Heinz, Oct 24 2012

nonn

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

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

Column k=9 of A182222.

b:= proc(n) b(n):= `if`(n<2, 1, b(n-1) +(n-1)*b(n-2)) end:
g:= proc(n) option remember; `if`(n<4, [1, 1, 2, 4][n+1],
      ((40*n^3+1084*n^2+8684*n+18480)*g(n-1) +16*(n-1)
      *(5*n^3+107*n^2+610*n+600)*g(n-2) -1024*(n-1)*(n-2)
      *(n+6)*g(n-3) -1024*(n-1)*(n-2)*(n-3)*(n+4)*g(n-4))/
       ((n+7)*(n+12)*(n+15)*(n+16)))
    end:
a:= n-> b(n) -g(n):
seq(a(n), n=9..30);

a(n) = A000085(n) - A007580(n) = A182172(n,n) - A182172(n,8).

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

A293738 Number of multisets of nonempty words with a total of n letters over octonary 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

Programs

Maple

Formula

A293747 Number of sets of nonempty words with a total of n letters over octonary 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

Programs

Maple

Mathematica

Formula

A049400 Partial sums of rows of A047884. Young Tableaux by height.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

A217328 Number of self-inverse permutations in S_n with longest increasing subsequence of length 8.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A218269 Number of standard Young tableaux of n cells and height >= 9.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

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