A219274 -id:A219274 - cp's OEIS frontend

A219356 Triangle read by rows: A219274 with rows reversed.

1, 1, 1, 1, 2, 1, 3, 1, 4, 5, 1, 5, 9, 16, 1, 6, 14, 49, 1, 7, 20, 92, 70, 1, 8, 27, 153, 204, 168, 1, 9, 35, 235, 405, 738, 768, 1, 10, 44, 341, 715, 1815, 3300, 1, 11, 54, 474, 1166, 3630, 9460, 7887, 1, 12, 65, 637, 1794, 6578, 21307, 28743, 15015

Offset: 0

Alois P. Heinz, Nov 18 2012

For more information see A219274.

			A219274 with rows reversed begins:
  1;
  1;
  1;
  1,  2;
  1,  3;
  1,  4,  5;
  1,  5,  9,  16;
  1,  6, 14,  49;
  1,  7, 20,  92,  70;
  1,  8, 27, 153, 204, 168;
  1,  9, 35, 235, 405, 738, 768;
  ...

Alois P. Heinz, Rows n = 0..100, flattened

Row lengths are A122797 (for n>0).
Row sums give: A218293.
Last elements of rows give: A219339.

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) local s; s:=i*(i+1)/2;
      `if`(n=s, h([l[], seq(i-j, j=0..i-1)]), `if`(n>s, 0,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i-1, [l[], i]))))
    end:
T:= (n, k)-> `if`(k>n, 0, g(n-k, k-1, [k])):
seq(seq(T(n, n-k), k=0..(n-floor(sqrt(2*n)+1/2))), n=0..14);

A005118 Number of simple allowable sequences on 1..n containing the permutation 12...n.

Original entry on oeis.org

1, 1, 1, 2, 16, 768, 292864, 1100742656, 48608795688960, 29258366996258488320, 273035280663535522487992320, 44261486084874072183645699204710400, 138018895500079485095943559213817088756940800

Offset: 0

N. J. A. Sloane

For n >= 2 by the hook length formula a(n) is also the number of Young tableaux of size 1+2+...+(n-1) = n*(n-1)/2 that correspond to the partition (1,2,...n-1), i.e., triangular Young tableaux. For example, for n=5 the shape of the tableau is xxxx / xxx / xx / x. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 04 2001
Also, a(n) is the degree of the symplectic Grassmannian, the projective variety of all maximal isotropic subspaces in a complex vector space of dimension 2n-2 with a symplectic form. See Hiller's paper. - Burt Totaro (b.totaro(AT)dpmms.cam.ac.uk), Oct 29 2002
Also, for n >= 2, a(n) is the number of maximal chains in the poset of Dyck paths ordered by inclusion. - Jennifer Woodcock (Jennifer.Woodcock(AT)ugdsb.on.ca), May 21 2008
a(n) is the number of minimal decompositions of the "flip" permutation n(n-1)..21 in terms of the n-1 standard Coxeter generators (i i+1) ("reduced decompositions", cf. Stanley). As such, it is also the number of positive n-strand braid words representing the Garside braid Delta(n) (the half-turn) (cf. Epstein's book, lemma 9.1.14). - Maxime Bourrigan, Apr 04 2011
For n >= 1, the normalized volume of the subpolytope of the Birkhoff polytope obtained by taking the convex hull of all (2n)x(2n) permutation matrices corresponding to alternating permutations that also avoid the pattern 123. - Robert Davis, Dec 04 2016

D. B. A. Epstein with J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson and W. P. Thurston, Word Processing in Groups, Jones and Bartlett Publishers, Boston, MA, 1992. xii+330 pp.
J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 102.
G. Kreweras, Sur un problème de scrutin à plus de deux candidats, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..40
Omer Angel, Alexander E. Holroyd, Dan Romik, and Balint Virag, Random Sorting Networks, arXiv preprint arXiv:0609538 [math.PR], 2006.
Joerg Arndt, The a(4)=16 Young tableaux of shape [3, 2, 1].
Sara C. Billey and Peter R. W. McNamara, The contributions of Stanley to the fabric of symmetric and quasisymmetric functions, arXiv preprint, 2015.
Tobias Boege, Alessio D'Alì, Thomas Kahle, Bernd Sturmfels, The Geometry of Gaussoids, arXiv:1710.07175 [math.CO], 2017.
R. Davis and B. Sagan, Pattern-Avoiding Polytopes, 2016
FindStat - Combinatorial Statistic Finder, The number of ways to write a permutation as a minimal length product of simple transpositions
M. J. Hay, J. Schiff, and N. J. Fisch, Maximal energy extraction under discrete diffusive exchange, arXiv preprint arXiv:1508.03499 [physics.plasm-ph], 2015.
H. Hiller, Combinatorics and intersection of Schubert varieties, Comment. Math. Helv. 57 (1982), 41-59.
D. Kim, Finding k Shortest Paths in Cayley Graphs of Finite Groups, Graphs and Combinatorics 40, 120 (2024). See Formula at p. 13.
G. Kreweras, Sur un problème de scrutin à plus de deux candidats, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87. [Annotated scanned copy]
Joshua Maglione and Christopher Voll, Hall-Littlewood polynomials, affine Schubert series, and lattice enumeration, arXiv:2410.08075 [math.CO], 2024. See pp. 34, 39.
R. P. Stanley, A combinatorial miscellany
R. P. Stanley, Ordering events in Minkowski space, arXiv:math/0501256 [math.CO], 2005.
R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., 5 (1984), 359-372.

Cf. A003121, A018241, A057863, A246865, A289778.

A005118 := proc(n) local i; binomial(n,2)!/product( (2*i+1)^(n-i-1), i=0..n-2 ); end;

Table[Binomial[n, 2]!/Product[(2*i + 1)^(n - i - 1), {i, 0, n - 2}], {n, 0, 10}] (* T. D. Noe, May 29 2012 *)

a(n) = C(n, 2)!/(1^{n-1} * 3^{n-2} *...* (2n-3)^1 ).
a(n) = (n*(n-1)/2)!/A057863(n-1) (n>=1). - Emeric Deutsch, May 21 2004
a(n) = A153452(A002110(n-1)). - Naohiro Nomoto, Jan 01 2009
From Alois P. Heinz, Nov 18 2012: (Start)
a(n+1) = A219272(A000217(n),n) = A219274(A000217(n),n) = A219311(A000217(n),n).
a(n) = A193536(n,A000217(n-1)) = A193629(n,A000217(n-1)). (End)
a(n) ~ sqrt(Pi) * n^(n^2/2-n/2+23/24) * exp(n^2/4-n/2+7/24) / (A^(1/2) * 2^(n^2-n/2-7/24)), where A = 1.2824271291... is the Glaisher-Kinkelin constant (see A074962). - Vaclav Kotesovec, Nov 13 2014

Citation corrected by Matthew J. Samuel, Feb 01 2011

A218293 Number of standard Young tableaux with shapes corresponding to partitions into distinct parts.

Original entry on oeis.org

1, 1, 1, 3, 4, 10, 31, 70, 190, 561, 2191, 6226, 22683, 74152, 283349, 1211354, 4572672, 18844177, 77585825, 327472752, 1418056071, 7083303437, 31251988918, 153456264178, 723293387594, 3596567095155, 17360616601051, 89955643932801, 486526881887485, 2551613423040841, 14029592127656040, 76756835252971657, 428044848852530252

Offset: 0

Joerg Arndt, Oct 25 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..120
Wikipedia, Young tableau

Cf. A000085 (standard Young tableaux for all shapes).
Diagonal of A219272, row sums of A219274, A219311. - Alois P. Heinz, Nov 17 2012
Cf. A225121 (tableaux with shapes corresponding to partitions into distinct parts with minimal difference 2).

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) local s; s:=i*(i+1)/2;
      `if`(n=s, h([l[], seq(i-j, j=0..i-1)]), `if`(n>s, 0,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i-1, [l[], i]))))
    end:
a:= n-> g(n, n, []):
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 08 2012

h[l_List] := Module[{n=Length[l]}, 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}]]; g[n_, i_, l_List] := Module[{s=i*(i+1)/2}, If[n == s, h[Join[l, Table[i-j, {j, 0, i-1}]]], If[n > s, 0, g[n, i-1, l] + If[i>n, 0, g[n-i, i-1, Append[l, i]]]]]]; a[n_] := g[n, n, {}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 18 2015, after Alois P. Heinz *)

A219311 Number T(n,k) of standard Young tableaux for partitions of n into exactly k distinct parts; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 3, 0, 1, 9, 0, 1, 14, 16, 0, 1, 34, 35, 0, 1, 55, 134, 0, 1, 125, 435, 0, 1, 209, 1213, 768, 0, 1, 461, 3454, 2310, 0, 1, 791, 10484, 11407, 0, 1, 1715, 28249, 44187, 0, 1, 3002, 80302, 200044, 0, 1, 6434, 231895, 680160, 292864

Offset: 0

Alois P. Heinz, Nov 17 2012

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=A003056(n). T(n,k) = 0 for k>A003056(n).

			A(4,2) = 3:
  +---------+  +---------+  +---------+
  | 1  2  3 |  | 1  2  4 |  | 1  3  4 |
  | 4 .-----+  | 3 .-----+  | 2 .-----+
  +---+        +---+        +---+
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1;
  0,  1,    2;
  0,  1,    3;
  0,  1,    9;
  0,  1,   14,    16;
  0,  1,   34,    35;
  0,  1,   55,   134;
  0,  1,  125,   435;
  0,  1,  209,  1213,   768;
  0,  1,  461,  3454,  2310;
  0,  1,  791, 10484, 11407;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
Wikipedia, Young tableau

Columns k=0-10 give: A000007, A000012 (for n>0), A047171(n) = A037952(n)-1, A219316, A219317, A219318, A219319, A219320, A219321, A219322, A219323.
Row sums give: A218293.
Row lengths are 1 + A003056(n).
T(A000217(k),k) = A005118(k+1).
Cf. A219272, A219274.

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, k, l) `if`(n=0, h(l), `if`(n>k*(i-(k-1)/2), 0,
      g(n, i-1, min(k, i-1), l)+`if`(i>n, 0, g(n-i, i-1, k-1, [l[], i]))))
    end:
A:= proc(n, k) option remember; `if`(k<0, 0, g(n, n, k, [])) end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..20);

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_] := If[n == 0, h[l], If[n > k*(i-(k-1)/2), 0, g[n, i-1, Min[k, i-1], l] + If[i > n, 0, g[n-i, i-1, k-1, Append[l, i]]]]];
a[n_, k_] := a[n, k] = If[k < 0, 0, g[n, n, k, {}]];
t[n_, k_] := a[n, k] - a[n, k-1];
Table[Table[t[n, k], {k, 0, Floor[(Sqrt[1+8*n]-1)/2]}], {n, 0, 20}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

A219272 Number A(n,k) of standard Young tableaux for partitions of n into distinct parts with largest part <= k; triangle A(n,k), k>=0, 0<=n<=k*(k+1)/2, read by columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 5, 16, 1, 1, 1, 3, 4, 9, 25, 49, 70, 168, 768, 1, 1, 1, 3, 4, 10, 30, 63, 162, 372, 1506, 3300, 7887, 15015, 48048, 292864, 1, 1, 1, 3, 4, 10, 31, 69, 182, 525, 1911, 5115, 17347, 43758, 149721, 626769, 1946516, 4934930

Offset: 0

Alois P. Heinz, Nov 17 2012

A(n,k) is defined for n,k >= 0. A(n,k) = 0 iff n > k*(k+1)/2 = A000217(k). The triangle contains only the nonzero terms. A(n,k) = A(n,n) for k>=n.

			A(3,2) = 2:
+------+  +------+
| 1  2 |  | 1  3 |
| 3 .--+  | 2 .--+
+---+     +---+
A(3,3) = 3:
+------+  +------+  +---------+
| 1  2 |  | 1  3 |  | 1  2  3 |
| 3 .--+  | 2 .--+  +---------+
+---+     +---+
Triangle A(n,k) begins:
1,  1,  1,  1,   1,    1,    1,    1,    1, ...
.   1,  1,  1,   1,    1,    1,    1,    1, ...
.       1,  1,   1,    1,    1,    1,    1, ...
.       2,  3,   3,    3,    3,    3,    3, ...
.           3,   4,    4,    4,    4,    4, ...
.           5,   9,   10,   10,   10,   10, ...
.          16,  25,   30,   31,   31,   31, ...
.               49,   63,   69,   70,   70, ...
.               70,  162,  182,  189,  190, ...

Alois P. Heinz, Columns k = 0..22, flattened
Wikipedia, Young tableau

Column heights are A000124.
Column sums give: A219273.
Diagonal gives: A218293.
Leftmost nonzero elements give A219339.
Column of leftmost nonzero element is A002024(n) for n>0.
T(A000217(n),n) = A005118(n+1).

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) local s; s:=i*(i+1)/2;
      `if`(n=s, h([l[], seq(i-j, j=0..i-1)]), `if`(n>s, 0,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i-1, [l[], i]))))
    end:
A:= (n, k)-> g(n, k, []):
seq(seq(A(n, k), n=0..k*(k+1)/2), k=0..7);

h[l_] := With[{n=Length[l]}, 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}]];
g[n_, i_, l_] := g[n, i, l] = With[{s=i*(i+1)/2}, If[n==s, h[Join[l, Table[ i-j, {j, 0, i-1}]]], If[n>s, 0, g[n, i-1, l] + If[i>n, 0, g[n-i, i-1, Append[l, i]]]]]];
A[n_, k_] := g[n, k, {}];
Table[Table[A[n, k], {n, 0, k*(k+1)/2}], {k, 0, 7}] // Flatten (* Jean-François Alcover, Feb 29 2016, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} A219274(n,i).

A219339 Number of standard Young tableaux for partitions of n into distinct parts with largest part floor(sqrt(2*n)+1/2).

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 16, 49, 70, 168, 768, 3300, 7887, 15015, 48048, 292864, 1946516, 4934930, 14454726, 34918884, 141892608, 1100742656, 9732668946, 32773404950, 97848532782, 344699731090, 1020872973120, 5091106775040, 48608795688960, 586393249199550

Offset: 0

Alois P. Heinz, Nov 18 2012

nonn

a(n) is the leftmost nonzero element in row n of A219272, A219274.

Floor(sqrt(2*n)+1/2) = A002024(n) for n>0. There are no partitions of n into distinct parts with a smaller largest part.

			For n=5, we have floor(sqrt(2*n)+1/2) = 3, and a(5) = 5, because there are 5 standard Young tableaux for partitions of 5 into distinct parts with largest part 3:
+---------+  +---------+  +---------+  +---------+  +---------+
| 1  2  3 |  | 1  2  4 |  | 1  2  5 |  | 1  3  4 |  | 1  3  5 |
| 4  5 .--+  | 3  5 .--+  | 3  4 .--+  | 2  5 .--+  | 2  4 .--+
+------+     +------+     +------+     +------+     +------+

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

Cf. A005118 (subsequence), A219347.

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) local s; s:=i*(i+1)/2;
      `if`(n=s, h([l[], seq(i-j, j=0..i-1)]), `if`(n>s, 0,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i-1, [l[], i]))))
    end:
a:= n-> g(n, floor(sqrt(2*n)+1/2), []):
seq(a(n), n=0..30);

h[l_] := (n = Length[l]; 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}]); g[n_, i_, l_] := g[n, i, l] = (s = i*(i+1)/2; If[n==s, h[Join[l, Table[i-j, {j, 0, i-1}]] ], If[n>s, 0, g[n, i-1, l]+If[i>n, 0, g[n-i, i-1, Append[l, i]]]]] ); a[n_] := g[n, Floor[Sqrt[2*n]+1/2], {}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 16 2017, translated from Maple *)

a(n) = A219272(n,floor(sqrt(2*n)+1/2)) = A219274(n,floor(sqrt(2*n)+1/2)).

A219275 Number of standard Young tableaux for partitions of nonnegative integers into distinct parts with largest part n.

Original entry on oeis.org

1, 1, 3, 25, 1069, 368168, 1299366501, 55208013380403, 32401197537296758130, 297072961835477978342245712, 47538199827835784548062928051198402, 146779873623344672821145371965795071455181183, 9581411392319396646028223743176779937161862866453789852

Offset: 0

Alois P. Heinz, Nov 17 2012

nonn

			a(2) = 3:
+------+  +------+  +------+
| 1  2 |  | 1  3 |  | 1  2 |
| 3 .--+  | 2 .--+  +------+
+---+     +---+

Alois P. Heinz, Table of n, a(n) for n = 0..22
Wikipedia, Young tableau

Column sums of A219274.

First differences of A219273.

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:
b:= (n, l)-> `if`(n<1, h(l), b(n-1, l) +b(n-1, [l[], n])):
a:= n-> `if`(n=0, 1, b(n-1, [n])):
seq(a(n), n=0..12);

h[l_] := With[{n = Length[l]}, 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}]];
b[n_, l_] := If[n < 1, h[l], b[n - 1, l] + b[n - 1, Append[l, n]]];
a[n_] := If[n == 0, 1, b[n - 1, {n}]];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Nov 02 2022, after Alois P. Heinz *)

cp's OEIS Frontend

A219356 Triangle read by rows: A219274 with rows reversed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A005118 Number of simple allowable sequences on 1..n containing the permutation 12...n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A218293 Number of standard Young tableaux with shapes corresponding to partitions into distinct parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A219311 Number T(n,k) of standard Young tableaux for partitions of n into exactly k distinct parts; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A219272 Number A(n,k) of standard Young tableaux for partitions of n into distinct parts with largest part <= k; triangle A(n,k), k>=0, 0<=n<=k*(k+1)/2, read by columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A219339 Number of standard Young tableaux for partitions of n into distinct parts with largest part floor(sqrt(2*n)+1/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A219275 Number of standard Young tableaux for partitions of nonnegative integers into distinct parts with largest part n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica