|
|
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.
|
|
19
|
|
|
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, 253, 265, 127, 41, 7, 1, 1, 125, 709, 929, 583, 209, 55, 8, 1, 1, 251, 1936, 3356, 2446, 1106, 319, 71, 9, 1, 1, 461, 5336, 11626, 10484, 5323, 1904, 461, 89, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
REFERENCES
|
W. Fulton, Young Tableaux, Cambridge, 1997.
D. Stanton and D. White, Constructive Combinatorics, Springer, 1986.
|
|
LINKS
|
|
|
EXAMPLE
|
For n=3 the 4 tableaux are
1 2 3 . 1 2 . 1 3 . 1
. . . . 3 . . 2 . . 2
. . . . . . . . . . 3
Triangle begins:
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, 253, 265, 127, 41, 7, 1;
1, 125, 709, 929, 583, 209, 55, 8, 1;
1, 251, 1936, 3356, 2446, 1106, 319, 71, 9, 1;
1, 461, 5336, 11626, 10484, 5323, 1904, 461, 89, 10, 1;
...
|
|
MAPLE
|
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) `if`(n=0 or i=1, (p->h(p)*x^`if`(p=[], 0, p[1]))
([l[], 1$n]), add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(g(n$2, [])):
seq(T(n), n=1..14); # Alois P. Heinz, Apr 16 2012, revised Mar 05 2014
|
|
MATHEMATICA
|
Table[ Plus@@( NumberOfTableaux/@ Reverse/@Union[ Sort/@(Compositions[ n-m, m ]+1) ]), {n, 12}, {m, n} ]
(* Second program: *)
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_] := 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[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][g[n, n, {}]];
|
|
CROSSREFS
|
Columns k=1-10 give: A000012, A014495, A217323, A217324, A217325, A217326, A217327, A217328, A217321, A217322. - Alois P. Heinz, Oct 03 2012
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|