%I #73 Sep 23 2024 07:55:25
%S 1,1,1,1,1,2,1,1,3,2,3,1,1,4,5,6,5,4,1,1,5,9,5,10,16,5,10,9,5,1,1,6,
%T 14,14,15,35,21,21,20,35,14,15,14,6,1,1,7,20,28,14,21,64,70,56,42,35,
%U 90,56,70,14,35,64,28,21,20,7,1
%N Irregular triangle read by rows: dimensions of the irreducible representations of the symmetric group S_n.
%C The n-th row has partition(n) = A000041(n) entries.
%C Also the numbers of standard Young tableaux for Young diagrams (or partitions).
%C Also "generalized" Catalan numbers. For a partition of n, n=(n_1+...+n_d), this is the number of integral lattice paths from (0,...,0) to (n_1,...,n_d) such that for any point p=(p_1,...p_d) on such a path p_i is never less than p_j whenever i<j. - _Graham H. Hawkes_, Jul 05 2013
%C The irreducible representations of S_n correspond to Young diagrams or partitions.
%C Partitions of n are ordered according to Abramowitz-Stegun (A-St) (see the reference, pp. 831-2). In contrast to A-St, a partition has nondecreasing parts (reverse notation of A-St).
%C The dimension of a representation of S_n corresponding to a Young diagram or partition is a(n,k) for the k-th partition of n in this A-St order.
%C One could call these numbers a(n,k) M_4 (similar to M_0, M_1, M_2, M_3 given in A111786, A036038, A036039, A036040, respectively).
%C From _Wolfdieter Lang_, Oct 09 2015: (Start)
%C The first formula given below appears in A. Young, Q.S.A. III, PLMS 28 (1928) 255-292 (third paper on "On Quantitative Substitutional Analysis"), Theorem II on p. 260, and he calls it f; see the collected papers (CP) reference, p. 357. Note the shorthand notation for the products; see Q.S.A. II, PLMS 34 (1902) 361-397, p. 366, CP, p. 97, for the explicit one.
%C This formula also can be found in the Glass-Ng link, Theorem 1, p. 702, using the Vandermonde determinant in the numerator and re-indexing the denominator.
%C The product of the hook length numbers, called H(n, k) in this formula below, is found in A263003(n, k).
%C The squared row entries sum to n!. See A. Young, Q.S.A. II (see above), pp. 367-368, CP pp. 98-99. Also Q.S.A. III, p. 265, CP p. 362.
%C (End)
%D G. de B. Robinson (ed.), The Collected Papers of Alfred Young 1873-1940, University of Toronto Press, 1977.
%D G. B. Wybourne, Symmetry principles and atomic spectroscopy, Wiley, New York, 1970, p. 9.
%H Alois P. Heinz, <a href="/A117506/b117506.txt">Rows n = 0..30, flattened</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H A. M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, pp. 831-2.
%H Kenneth Glass and Chi-Keung Ng, <a href="http://www.jstor.org/stable/4145043?seq=1#page_scan_tab_contents">A Simple Proof of the Hook Length Formula</a>, Am. Math. Monthly 111 (2004) 700 - 704.
%H Graham H. Hawkes, <a href="http://arxiv.org/abs/1310.5919">An Elementary Proof of a Formula for SYT</a>, arXiv preprint arXiv:1310.5919 [math.CO], 2013-2014.
%H Wolfdieter Lang, <a href="/A117506/a117506.pdf">First 15 rows.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HookLengthFormula.html">Hook length formula.</a>
%H Doron Zeilberger, <a href="http://dx.doi.org/10.1016/0012-365X(83)90200-5">Andre's Reflection Proof Generalized to the Many-Candidate Ballot Problem</a>, Discrete Mathematics 44 (1983) 325-326.
%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%F a(n,k) = n!/H(n,k) with H(n,k):= Product_{i=1..m(n,k)} (x_i)!/Det(x_i^(m(n,k)-j)) with the Vandermonde determinant for the variables x_i:=lambda(n,k)_i + m(n,k)-i, i,j=1..m(n,k) if m(n,k) is the number of parts of the k-th partition of n, called lambda(n,k), in the A-St order (see above). Lambda(n,k)_i denotes the i-th part of the partition lambda(n,k), sorted in decreasing order (this is the reverse of the A-St notation).
%F a(n,k) = n!/Product_{j=1..n}(h(n,k,j) with the hook numbers h(n,k,j) of the Young diagram of the partition lambda(n,k) in the A-St order. See the link for 'hook length formula'.
%e [1];
%e [1];
%e [1, 1];
%e [1, 2, 1];
%e [1, 3, 2, 3, 1];
%e [1, 4, 5, 6, 5, 4, 1];
%e [1, 5, 9, 5, 10, 16, 5, 10, 9, 5, 1];...
%e a(4,4)=3 because the 4th partition of n=4 in A-St order is [2,1,1],
%e and H(4,4)=(4!*2!*1!)/Vandermonde([4,2,1]) = (4!*2)/6 =4*2, hence
%e 4!/H(4,4) = 3.
%e a(4,4)=3 because the hook lengths of the Young diagram of [2,1,1] are [4, 1; 2; 1], hence 4!/(4*1*2*1) = 3.
%e The sum of the squared entries of each row gives n!: n = 5: 2*(1^1 + 4^2 + 5^2) + 6^2 = 120 = 5!. - _Wolfdieter Lang_, Oct 09 2015
%p h:= l-> (n-> mul(mul(1+l[i]-j+add(`if`(l[k]>=j, 1, 0),
%p k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
%p g:= (n, i, l)-> `if`(n=0 or i=1, [h([l[], 1$n])],
%p [g(n, i-1, l)[], g(n-i, min(n-i, i), [l[], i])[]]):
%p T:= n-> map(x-> n!/x, g(n$2, []))[]:
%p seq(T(n), n=0..10); # _Alois P. Heinz_, Nov 05 2015
%t h[l_List] := Function[n, Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]][Length[l]]; g[n_, i_, l_List] := If[n==0 || i==1, Join[{h[Join[l, Array[1&, n]]]}], If[i<1, {}, Join[{g[n, i-1, l]}, If[i>n, {}, g[n-i, i, Join[l, {i}]]]]]] // Flatten; T[n_] := n!/ g[n, n, {}]; Table[T[n], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Dec 19 2015, after _Alois P. Heinz_ *)
%Y Cf. A000041, A000085 (row sums), A060240 (rows sorted), A263003.
%Y Cf. A067924.
%K nonn,easy,tabf
%O 0,6
%A _Wolfdieter Lang_, Apr 13 2006
%E Row n=0 prepended by _Alois P. Heinz_, Nov 05 2015