login
A226651
Multidimensional Young numbers: Given a d-dimensional partition of n, this is the number of ways to fill the associated d-dimensional Young diagram with the integers 1 to n such that the entries are increasing in each positive (orthogonal) direction.
1
1, 1, 1, 2, 1, 3, 2, 6, 1, 4, 5, 6, 12, 8, 24, 1, 5, 9, 10, 5, 16, 20, 25, 30, 20, 16, 60, 40, 120, 1, 6, 14, 15, 14, 25, 20, 21, 30, 54, 60, 30, 96, 40, 66, 61, 75, 90, 48, 120, 150, 180, 120, 96, 80, 360, 240, 720, 1, 7, 20, 21, 28, 64, 35, 14, 70, 56, 90, 42, 42, 98, 105, 98, 245, 140, 147
OFFSET
1,4
COMMENTS
Generalization of the number of standard Young tableaux on a given Young diagram to arbitrary dimension.
The multidimensional Young numbers of partitions which are conjugate are equal. Therefore, the multidimensional Young numbers listed above are indexed with respect to an ordering of the "conjugacy classes" of partitions. This ordering is defined in the attached pdf file.
The number of entries between the m-th and (m+1)-th appearance of 1 (including the m-th appearance, but excluding the (m+1)-th) is the number of infinite dimensional partitions of m up to conjugacy, i.e., sequence A119268.
Let f(m) give the number of 2-dimensional partitions of m up to conjugacy (sequence A005987). Then the first f(m) entries following (and including) the m-th appearance of 1 are standard Young tableaux numbers on 2-dimensional partitions of m, and can be found in sequence A117506.
FORMULA
Let p be a partition of n. Let Q be the set of partitions of n-1 such that for all q in Q, p covers q. Then the Young number of p is given by Y(p) = Sum_{q in Q} Y(q).
EXAMPLE
The ordering of "conjugacy classes" of partitions begins:
(1), (2), (3), (2+1), (4), (3+1), (2+2), ((2+1)+(1)), (5), (4+1), (3+2), (3+1+1), ((3+1)+(1)), ((2+2)+(1)),
(((2+1)+(1))+((1))), ...
The 14th partition, ((2+2)+(1)), is associated to the Young diagram with cubes centered at p_1=(0,0,0), p_2=(1,0,0), p_3=(0,1,0), p_4=(1,1,0), and p_5=(0,0,1). The possible ways to fill the cubes centered on these points so that the numbers are increasing in all directions are;
(For each i=1:5, the i-th integer in a sequence below is placed on p_i.)
1-2-3-4-5
1-3-2-4-5
1-2-3-5-4
1-3-2-5-4
1-2-4-5-3
1-4-2-5-3
1-3-4-5-2
1-4-3-5-2
Hence the 14th term is 8.
The 48th partition, ((2+2)+(2+2)), can be represented as a cube divided into octants. The integers 1 and 8 must lie in opposite octants. Of the three octants adjacent to the one which contains 1, one must contain 2 and one must contain 3. This gives 6 possibilities. For each of these possibilities there are 4 numbers (4, 5, 6, and 7) to choose from for the number placed in the remaining cube in the plane that contains 1, 2, and 3. Regardless of this choice, there are 2 ways to fill in the remaining three octants. Thus there are 6*4*2=48 ways to fill the octants all together--that is, the 48th multidimensional Young number is 48.
Example of recursion:
The partition: p|--6=((3+2)+(1)) covers the following partitions of 5:
q_1|--5=(3+2)
q_2|--5=((3+1)+(1))
q_3|--5=((2+2)+(1)) Thus Y(p)=Y(q_1)+Y(q_2)+Y(q_3)=5+12+8=25
PROG
(MATLAB)
% See MATLAB function in Links.
CROSSREFS
Sequence in context: A075257 A260618 A306286 * A073711 A071690 A319179
KEYWORD
nonn,tabf,changed
AUTHOR
Graham H. Hawkes, Jul 30 2013
STATUS
approved