A049400 -id:A049400

Search: a049400 -id:a049400

Displaying 1-3 of 3 results found.

page 1

A182172

Number A(n,k) of standard Young tableaux of n cells and height <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

+10
44

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 4, 6, 1, 0, 1, 1, 2, 4, 9, 10, 1, 0, 1, 1, 2, 4, 10, 21, 20, 1, 0, 1, 1, 2, 4, 10, 25, 51, 35, 1, 0, 1, 1, 2, 4, 10, 26, 70, 127, 70, 1, 0, 1, 1, 2, 4, 10, 26, 75, 196, 323, 126, 1, 0, 1, 1, 2, 4, 10, 26, 76, 225, 588, 835, 252, 1, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,13

COMMENTS

Also the number A(n,k) of standard Young tableaux of n cells and <= k columns.

A(n,k) is also the number of n-length words w over a k-ary alphabet {a1,a2,...,ak} such that for every prefix z of w we have #(z,a1) >= #(z,a2) >= ... >= #(z,ak), where #(z,x) counts the letters x in word z. The A(4,4) = 10 words of length 4 over alphabet {a,b,c,d} are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca, abcd.

LINKS

Alois P. Heinz, Antidiagonals n = 0..80, flattened

Wikipedia, Young tableau

FORMULA

Conjecture: A(n,k) ~ k^n/Pi^(k/2) * (k/n)^(k*(k-1)/4) * Product_{j=1..k} Gamma(j/2). - Vaclav Kotesovec, Sep 12 2013

EXAMPLE

A(4,2) = 6, there are 6 standard Young tableaux of 4 cells and height <= 2:

+------+ +------+ +---------+ +---------+ +---------+ +------------+

| 1 3 | | 1 2 | | 1 3 4 | | 1 2 4 | | 1 2 3 | | 1 2 3 4 |

| 2 4 | | 3 4 | | 2 .-----+ | 3 .-----+ | 4 .-----+ +------------+

+------+ +------+ +---+ +---+ +---+

Square array A(n,k) begins:

1, 1, 1, 1, 1, 1, 1, 1, 1, ...

0, 1, 1, 1, 1, 1, 1, 1, 1, ...

0, 1, 2, 2, 2, 2, 2, 2, 2, ...

0, 1, 3, 4, 4, 4, 4, 4, 4, ...

0, 1, 6, 9, 10, 10, 10, 10, 10, ...

0, 1, 10, 21, 25, 26, 26, 26, 26, ...

0, 1, 20, 51, 70, 75, 76, 76, 76, ...

0, 1, 35, 127, 196, 225, 231, 232, 232, ...

0, 1, 70, 323, 588, 715, 756, 763, 764, ...

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) option remember;

`if`(n=0, h(l), `if`(i<1, 0, `if`(i=1, h([l[], 1$n]),

g(n, i-1, l) +`if`(i>n, 0, g(n-i, i, [l[], i])))))

end:

A:= (n, k)-> g(n, k, []):

seq(seq(A(n, d-n), n=0..d), d=0..15);

MATHEMATICA

h[l_List] := Module[{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_, l_List] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Array[1&, n]]], g [n, i-1, l] + If[i > n, 0, g[n-i, i, Append[l, i]]]]]];

a[n_, k_] := g[n, k, {}];

Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 06 2013, translated from Maple *)

CROSSREFS

Columns k=0-12 give: A000007, A000012, A001405, A001006, A005817, A049401, A007579, A007578, A007580, A212915, A212916, A229053, A229068.

Main diagonal gives A000085.

A(2n,n) gives A293128.

Cf. A047884, A049400, A226873, A240608.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Apr 16 2012

STATUS

approved

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.

+10
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

Alois P. Heinz, Rows n = 1..68, flattened

R. P. Stanley, A combinatorial miscellany

Index entries for sequences related to Young tableaux.

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, 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, {}]];

Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Oct 26 2015, after Alois P. Heinz *)

CROSSREFS

Row sums give A000085.

Cf. A049400, A049401, and A178249 which imposes contiguity.

Columns k=1-10 give: A000012, A014495, A217323, A217324, A217325, A217326, A217327, A217328, A217321, A217322. - Alois P. Heinz, Oct 03 2012

a(2n,n) gives A267436.

KEYWORD

nonn,tabl,nice,easy

AUTHOR

Wouter Meeussen

EXTENSIONS

Definition amended ('scattered' added) by Wouter Meeussen, Dec 22 2010

STATUS

approved

A182222

Number T(n,k) of standard Young tableaux of n cells and height >= k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

+10
11

1, 1, 1, 2, 2, 1, 4, 4, 3, 1, 10, 10, 9, 4, 1, 26, 26, 25, 16, 5, 1, 76, 76, 75, 56, 25, 6, 1, 232, 232, 231, 197, 105, 36, 7, 1, 764, 764, 763, 694, 441, 176, 49, 8, 1, 2620, 2620, 2619, 2494, 1785, 856, 273, 64, 9, 1, 9496, 9496, 9495, 9244, 7308, 3952, 1506, 400, 81, 10, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= k. T(4,3) = 4: 1234, 1243, 1324, 2134; T(3,0) = T(3,1) = 4: 123, 132, 213, 321; T(5,3) = 16: 12345, 12354, 12435, 12543, 13245, 13254, 14325, 14523, 15342, 21345, 21354, 21435, 32145, 34125, 42315, 52341.

LINKS

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

Wikipedia, Involution (mathematics)

Wikipedia, Young tableau

FORMULA

T(n,k) = A182172(n,n) - A182172(n,k-1) for k>0, T(n,0) = A182172(n,n).

EXAMPLE

T(4,3) = 4, there are 4 standard Young tableaux of 4 cells and height >= 3:

+---+ +------+ +------+ +------+

| 1 | | 1 2 | | 1 3 | | 1 4 |

| 2 | | 3 .--+ | 2 .--+ | 2 .--+

| 3 | | 4 | | 4 | | 3 |

| 4 | +---+ +---+ +---+

+---+

Triangle T(n,k) begins:

1, 1;

2, 2, 1;

4, 4, 3, 1;

10, 10, 9, 4, 1;

26, 26, 25, 16, 5, 1;

76, 76, 75, 56, 25, 6, 1;

232, 232, 231, 197, 105, 36, 7, 1;

764, 764, 763, 694, 441, 176, 49, 8, 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) option remember;

`if`(n=0, h(l), `if`(i<1, 0, `if`(i=1, h([l[], 1$n]),

g(n, i-1, l) +`if`(i>n, 0, g(n-i, i, [l[], i])))))

end:

T:= (n, k)-> g(n, n, []) -`if`(k=0, 0, g(n, k-1, [])):

seq(seq(T(n, k), k=0..n), n=0..12);

MATHEMATICA

h[l_] := Module[{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_, l_] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Array[1&, n]]], g [n, i-1, l] + If[i > n, 0, g[n-i, i, Append[l, i]]]]]];

t[n_, k_] := g[n, n, {}] - If[k == 0, 0, g[n, k-1, {}]];

Table[Table[t[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

CROSSREFS

Columns 0-10 give: A000085, A000085 (for n>0), A001189, A218263, A218264, A218265, A218266, A218267, A218268, A218269, A218262.

Diagonal and lower diagonals give: A000012, A000027(n+1), A000290(n+1) for n>0, A131423(n+1) for n>1.

T(2n,n) gives A318289.

Cf. A047884, A049400, A182172.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Apr 19 2012

STATUS

approved

page 1

Search completed in 0.007 seconds