cp's OEIS Frontend

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

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