A117506 -id:A117506 - cp's OEIS frontend

A264753 Irregular triangle read by rows: T(n,k) = A127671(n,k)/A036040(n,k), n >= 1 and 1 <= k <= A000041(n).

1, 1, -1, 1, -1, 2, 1, -1, -1, 2, -6, 1, -1, -1, 2, 2, -6, 24, 1, -1, -1, -1, 2, 2, 2, -6, -6, 24, -120, 1, -1, -1, -1, 2, 2, 2, 2, -6, -6, -6, 24, 24, -120, 720, 1, -1, -1, -1, -1, 2, 2, 2, 2, 2, -6, -6, -6, -6, -6, 24, 24, 24, -120, -120, 720, -5040

Offset: 1

Johannes W. Meijer, Jul 12 2016

This sequence connects the multinomial coefficients A036040 (M_3) with A127671 (M_5).
The numbers of terms in n-th row is the number of partitions A000041(n). The number of terms T(n, k) with equal values in the n-th row follow the rhythm of A008284(n).
Some row sums are [1, 0, 2, -5, 21, -104, 636, -4511, 36455, -330954, 3334390, -36914039].

			The first few rows of the T(n,k) triangle:
n = 1: 1
n = 2: 1, -1
n = 3: 1, -1, 2
n = 4: 1, -1, -1, 2, -6
n = 5: 1, -1, -1, 2, 2, -6, 24
n = 6: 1, -1, -1, -1, 2, 2, 2, -6, -6, 24, -120
n = 7: 1, -1, -1, -1, 2, 2, 2, 2, -6, -6, -6, 24, 24, -120, 720

Milton Abramowitz and Irene A. Stegun, editors, Multinomials: M_1, M_2 and M_3, Handbook of Mathematical Functions, December 1972, pp. 831-2.

Cf. A036040 (M_3), A127671 (M_5), A000041, A008284, A081362.

Cf. A048996 (M_0), A036038 (M_1), A036039 (M_2), A117506 (M_4).

nmax:=8: with(combinat): A008284 := proc(n, k) option remember; if k < 0 or n < 0 then 0 elif k = 0 then if n = 0 then 1 else 0 fi else A008284(n-1, k-1) + A008284(n-k, k) fi end: for n from 1 to nmax do p:=0: k:=1: while k < numbpart(n)+1 do p := p+1: k1 := A008284(n, p): while k1 > 0 do A264753(n, k) := (-1)^(p+1)*(p-1)!: k := k+1: k1 := k1-1: od: od: od: seq(seq(A264753(n, k), k = 1..numbpart(n)), n = 1..nmax);

nMax = 8; A008284[n_, k_] := A008284[n, k] = If[k<0 || n<0, 0, If[k == 0, If[n == 0, 1, 0], A008284[n-1, k-1] + A008284[n-k, k]]]; For[n = 1, n <= nMax, n++, p = 0; k = 1; While[k < PartitionsP[n]+1, p = p+1; k1 = A008284[n, p]; While[k1>0, A264753[n, k] = (-1)^(p+1)*(p-1)!; k = k+1; k1 = k1-1]]]; Table[Table[A264753[n, k], {k, 1, PartitionsP[n]}], {n, 1, nMax}] // Flatten (* Jean-François Alcover, Oct 01 2016, translated from Maple *)

T(n, k) = A127671(n, k)/A036040(n, k), n >= 1 and 1 <= k <= A000041(n).

A134284 A certain partition array in Abramowitz-Stegun order (A-St order), called M_0(3)/M_0.

Original entry on oeis.org

1, 3, 1, 10, 3, 1, 35, 10, 9, 3, 1, 126, 35, 30, 10, 9, 3, 1, 462, 126, 105, 100, 35, 30, 27, 10, 9, 3, 1, 1716, 462, 378, 350, 126, 105, 100, 90, 35, 30, 27, 10, 9, 3, 1, 6435, 1716, 1386, 1260, 1225, 462, 378, 350, 315, 300, 126, 105, 100, 90, 81, 35, 30, 27, 10, 9, 3, 1

Offset: 1

Wolfdieter Lang, Nov 13 2007

The sequence of row lengths is A000041 (partition numbers) [1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ...].
For the A-St order of partitions see the Abramowitz-Stegun reference given in A117506.
Partition number array M_0(3)= A134283 with each entry divided by the corresponding one of the partition number array M_0 = M_0(2) = A048996; in short M_0(3)/M_0.

			[1]; [3,1]; [10,3,1]; [35,10,9,3,1]; [126,35,30,10,9,3,1]; ...
a(4,3) = 9 = 3^2 because (2^2) is the k=4 partition of n=4 in A-St order and s2(3,2,1)=3.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
W. Lang, First 10 rows and more.

Cf. A134826 (row sums coinciding with those of triangle A134285).

a(n,k) = Product_{j=1..n} s2(3,j,1)^e(n,k,j) with s2(3,n,1) = A035324(n,1) = A001700(n-1) = binomial(2*n-1,n) and with the exponent e(n,k,j) of j in the k-th partition of n in the A-St ordering of the partitions of n.

a(n,k) = A134283(n,k)/A048996(n,k) (division of partition arrays M_0(3) by M_0).

A262030 Partition array in Abramowitz-Stegun order: Schur functions evaluated at 1.

Original entry on oeis.org

1, 3, 1, 10, 8, 1, 35, 45, 20, 15, 1, 126, 224, 175, 126, 75, 24, 1, 462, 1050, 1134, 490, 840, 896, 175, 280, 189, 35, 1, 1716, 4752, 6468, 4704, 4950, 7350, 3528, 2646, 2400, 2940, 784, 540, 392, 48, 1, 6435, 21021, 34320, 33264, 13860, 27027, 50688, 41580, 25872, 15876, 17325, 29700, 15120, 14700, 1764, 5775, 7680, 2352, 945, 720, 63, 1

Offset: 1

Wolfdieter Lang, Oct 15 2015

The length of row n >= 1 of this irregular triangle is A000041(n) (partition numbers).
The Abramowitz-Stegun (A-St) order of the partitions is used.
For Schur functions (or polynomials) s^(lambda) = s(lambda(n, k);x[1], ..., x[n]) defined for the k-th partition of n (here in A-St order) see, e.g., the Macdonald reference, ch. I, 3. S-functions, p. 23, and Wikipedia reference. For the combinatorial interpretation of Schur functions see the Stanley reference.
The partition lambda(n,k) has m = m(n,k) nonincreasing parts lamda_j, j = 1..m, (the reverse of the partitions given in A-St) and n-m 0's are appended to obtain a length n partition. E.g., lambda(4, 3) = (2, 2, 0, 0) with m = 2.
The Schur function s(lambda(n, k),1,...,1) (n 1's) gives the number of semistandard Young tableaux (SSYT) for the Young (Ferrers) diagram of lambda(n, k) (forgetting about trailing 0's) with the box numbers taken out of the set {1, 2, ..., n} where the rows increase weakly and the columns increase strictly. See the Stanley reference pp. 309 and 310, and the example below.
The sum of the row numbers give A209673: 1, 4, 19, 116, 751, 5552, 43219, 366088, ...
Conjecture: The sum of the squares of row numbers give A054688: 1, 10, 165, 3876, ... = binomial(n^2+n-1, n). - Wouter Meeussen, Sep 25 2016

			The irregular triangle begins (commas separate entries for partitions of like numbers of parts in A-St order):
n\k  1     2    3    4    5   6   7    8   9 10 11
1:   1
2:   3,    1
3:  10,    8,   1
4:  35,   45   20,  15,   1
5: 126,  224  175, 126   75, 24,  1
6: 462, 1050 1134  490, 840 896 175, 280 189,35, 1
...
Row 7: 1716, 4752 6468 4704, 4950 7350 3528 2646, 2400 2940 784, 540 392, 48, 1;
Row 8: 6435, 21021 34320 33264 13860, 27027 50688 41580 25872 15876, 17325 29700 15120 14700 1764, 5775 7680 2352, 945 720, 63, 1.
...
n = 4, k = 4: lambda(4, 4) = (2,1,1,0) (m=3), SSYT (we use semicolons to separate the three rows): [1,1;2;3], [1,1;2;4], [1,1;3;4],
  [1,2;2;3], [1,2;2;4], [1,2;3;4],
  [1,3;2;3], [1,3;2;4], [1,3;3;4],
  [1,4;2;3], [1,4;2;4], [1,4;3;4],
  [2,2;3;4], [2,3;3;4], [2,4;3;4], hence a(4, 4) = 15. The three tableaux with distinct numbers are standard Young tableaux and give A117506(4, 4) = 3.

Macdonald, I. G., Symmetric functions and Hall polynomials, Oxford University Press, 1979.
Stanley, R. P., Enumerative Combinatorics, Vol. 2, Cambridge University Press 1999, sect. 7.30, pp. 308-316.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, pp. 831-2.
Wikipedia, Schur functions.

Cf. A054688, A117506, A209673, A210391 (in the diagonal).

a(n, k) = Det_{i,j=1..n} x[i]^(lambda_j + n-j) / Det_{i,j=1..n} x[i]^(n-j), evaluated at x[i] = 1 for i = 1..n (after division). The denominator is the Vandermonde determinant, the numerator an alternant. See, e.g., the Macdonald reference p. 24.

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.

Original entry on oeis.org

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

Graham H. Hawkes, Jul 30 2013

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.

			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

Graham H. Hawkes, MATLAB Program
Graham H. Hawkes, Multidimensional Young Numbers

MATLAB
```
% See MATLAB function in Links.
```

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

A122932 a(n) = A000085(n) - A000079(n-1).

Original entry on oeis.org

0, 0, 0, 2, 10, 44, 168, 636, 2364, 8984, 34672, 138104, 564408, 2382288, 10333152, 46173968, 211733776, 997182752, 4809439296, 23758139808, 119951644320, 618882541760, 3257839688320, 17492182188992, 95680426983360

Offset: 1

Alford Arnold, Sep 22 2006

Also sums values in A117506 but not in A007318.

			Row five of A117506 is 1 5 9 5 10 16 5 10 9 5 1.
Row five of A007318 is 1 5 10 10 5 1.
So included values are 9 5 16 5 9;
therefore a(5) = 44 = 76 - 32.

Cf. A000079, A000085, A059797, A067924, A117506.

Table[Sum[(2k)!/k!/2^k Binomial[n, 2k], {k, 0, n/2}] - 2^(n - 1) // FullSimplify, {n, 26}] (* Robert G. Wilson v, Sep 27 2006 *)  (* or *)
Table[HypergeometricU[ -(n/2), 1/2, -(1/2)]/(-(1/2))^(-(-n/2)) - 2^(n - 1), {n, 26}] (* Robert G. Wilson v, Sep 27 2006 *)  (* or *)
(* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Table[NumberOfTableaux[M[Star[n+1]]] - 2^(n - 1), {n, 26}] (* Robert G. Wilson v, Sep 27 2006 *)

a(n) = A000085(n) - A000079(n) for n>0.

More terms from Robert G. Wilson v, Sep 27 2006

A167203 Number of Young tableaux with n cells and k inversions.

Original entry on oeis.org

1, 2, 4, 8, 2, 16, 10, 32, 34, 5, 5, 64, 98, 35, 35, 128, 258, 154, 154, 14, 42, 14

Offset: 1

Alford Arnold, Nov 07 2009

The sequence of rowsums is A000085, and the sequence of number of terms in each row is A002865.

			The irregular triangle begins
..1
..2
..4
..8...2
.16..10
.32..34...5...5
.64..98..35..35
128.258.154.154..14..42..14
etc.

FindStat - Combinatorial Statistic Finder, The number of inversions of a tableau

Cf. A000041, A002865, A000079 (rowsum of A007318), A036799 (rowsum of A059797), A117506.

A340398 Number of spanning trees in the Bruhat graph of the symmetric group.

Original entry on oeis.org

1, 1, 81, 22799473113563136

Offset: 1

Richard Ehrenborg, Jan 06 2021

nonn

The Bruhat graph of the symmetric group S_n has the set of all permutations on n elements as the vertex set and two permutations pi and sigma are connected with an edge if pi sigma^{-1} is a transposition.

			For n=3 the number of spanning trees is 81 since the graph is the complete bipartite graph K_{3,3}.
For n=4, the following calculation demonstrates the formula:
  31: 6 - (1-1) - (2-1) - (3-1) - (1-2) = 4;
  22: 6 - (1-1) - (2-1) - (1-2) - (2-2) = 6;
  211: 6 - (1-1) - (2-1) - (1-2) - (1-3) = 8;
  1111: 6 - (1-1) - (1-2) - (1-3) - (1-4) = 12.
Hence the number of spanning trees is given by (1/4!) * 4^9 * 6^4 * 8^9 * 12^1 = 2^48 * 3^4 = 22799473113563136.

R. Ehrenborg, The number of spanning trees of the Bruhat graph, Adv. in Appl. Math. 125 (2021), 102150.
Eric Weisstein's World of Mathematics, Spanning Tree
Eric Weisstein's World of Mathematics, Transposition Graph

Cf. A117506.

a(n) = (1/n!) * Product_{lambda} (n*(n-1)/2 - Sum_{(i,j) in lambda} (j-i))^{f_{lambda}^2} where the product ranges over all integer partition lambda of n different from n, and f_{lambda} is the number of standard Young tableaux of shape lambda (see sequence A117506). Furthermore, the partitions are also viewed as their Ferrers shape, for instance, the partition 31 corresponds to the pairs (1,1), (1,2), (1,3) and (2,1).

cp's OEIS Frontend

A264753 Irregular triangle read by rows: T(n,k) = A127671(n,k)/A036040(n,k), n >= 1 and 1 <= k <= A000041(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A134284 A certain partition array in Abramowitz-Stegun order (A-St order), called M_0(3)/M_0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A262030 Partition array in Abramowitz-Stegun order: Schur functions evaluated at 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Programs

MATLAB

Formula

A122932 a(n) = A000085(n) - A000079(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A167203 Number of Young tableaux with n cells and k inversions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A340398 Number of spanning trees in the Bruhat graph of the symmetric group.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula