|
%I #60 Mar 15 2021 08:24:43
%S 1,1,1,1,2,1,1,5,3,1,1,9,11,4,1,1,19,31,19,5,1,1,34,92,69,29,6,1,1,69,
%T 253,265,127,41,7,1,1,125,709,929,583,209,55,8,1,1,251,1936,3356,2446,
%U 1106,319,71,9,1,1,461,5336,11626,10484,5323,1904,461,89,10,1
%N Triangle of numbers a(n,k) = number of Young tableaux with n cells and k rows (1 <= k <= n); also number of self-inverse permutations on n letters in which the length of the longest scattered (i.e., not necessarily contiguous) increasing subsequence is k.
%D W. Fulton, Young Tableaux, Cambridge, 1997.
%D D. Stanton and D. White, Constructive Combinatorics, Springer, 1986.
%H Alois P. Heinz, <a href="/A047884/b047884.txt">Rows n = 1..68, flattened</a>
%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>
%H <a href="/index/Y#Young">Index entries for sequences related to Young tableaux</a>.
%e For n=3 the 4 tableaux are
%e 1 2 3 . 1 2 . 1 3 . 1
%e . . . . 3 . . 2 . . 2
%e . . . . . . . . . . 3
%e Triangle begins:
%e 1;
%e 1, 1;
%e 1, 2, 1;
%e 1, 5, 3, 1;
%e 1, 9, 11, 4, 1;
%e 1, 19, 31, 19, 5, 1;
%e 1, 34, 92, 69, 29, 6, 1;
%e 1, 69, 253, 265, 127, 41, 7, 1;
%e 1, 125, 709, 929, 583, 209, 55, 8, 1;
%e 1, 251, 1936, 3356, 2446, 1106, 319, 71, 9, 1;
%e 1, 461, 5336, 11626, 10484, 5323, 1904, 461, 89, 10, 1;
%e ...
%p h:= proc(l) local n; n:=nops(l); add(i, i=l)!/mul(mul(1+l[i]-j+
%p add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
%p end:
%p g:= proc(n, i, l) `if`(n=0 or i=1, (p->h(p)*x^`if`(p=[], 0, p[1]))
%p ([l[], 1$n]), add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(g(n$2, [])):
%p seq(T(n), n=1..14); # _Alois P. Heinz_, Apr 16 2012, revised Mar 05 2014
%t Table[ Plus@@( NumberOfTableaux/@ Reverse/@Union[ Sort/@(Compositions[ n-m, m ]+1) ]), {n, 12}, {m, n} ]
%t (* Second program: *)
%t 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}]];
%t g[n_, i_, l_] := If[n== 0|| i==1, Function[p, h[p]*x^If[p == {}, 0, p[[1]] ] ] [ Join[l, Array[1&, n]]], Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]];
%t T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][g[n, n, {}]];
%t Table[T[n], {n, 1, 14}] // Flatten (* _Jean-François Alcover_, Oct 26 2015, after _Alois P. Heinz_ *)
%Y Row sums give A000085.
%Y Cf. A049400, A049401, and A178249 which imposes contiguity.
%Y Columns k=1-10 give: A000012, A014495, A217323, A217324, A217325, A217326, A217327, A217328, A217321, A217322. - _Alois P. Heinz_, Oct 03 2012
%Y a(2n,n) gives A267436.
%K nonn,tabl,nice,easy
%O 1,5
%A _Wouter Meeussen_
%E Definition amended ('scattered' added) by _Wouter Meeussen_, Dec 22 2010
|
