OFFSET
2,5
COMMENTS
Alternatively, square array read by antidiagonals: a(n,k) (n >= 1, k >= 1) = number of partitions of (n,k) into pairs (i,j) with i,j>0. The addition rule is (a,b)+(x,y)=(a+x,b+y). E.g., (4,3) = (3,2)+(1,1) = (3,1)+(1,2) = (2,2)+(2,1) = (2,1)+(1,1)+(1,1), so T(4,3)=5. - Christian G. Bower, Jun 03 2005
Permutations of n elements have a polynomial sum x^{ind pi}y^{inv pi} where ind denotes the major index and inv the number of inversions. For example when n=3 the polynomial is 1 + xy + xy^2 + x^2y + x^2y^2 + x^3y^3. The coefficient of x^i y^j when i+j <= n is given by this sequence; in other words, the polynomials approach 1 + xy + x^2y + xy^2 + x^3y + 2x^2y^2 + xy^3 + ... + 4x^3y^3 + ... as n grows. The reasons can be found in the Garsia-Gessel reference.
REFERENCES
Alter, Ronald; Curtz, Thaddeus B.; Wang, Chung C. Permutations with fixed index and number of inversions. Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), pp. 209-228. Congressus Numerantium, No. X, Utilitas Math., Winnipeg, Man., 1974. From N. J. A. Sloane, Mar 20 2012
M. S. Cheema and T. S. Motzkin, "Multipartitions and multipermutations," Proc. Symp. Pure Math. 19 (1971), 39-70, eq. (3.1.3).
LINKS
A. M. Garsia and I. Gessel, Permutation statistics and partitions, Advances in Mathematics, Volume 31, Issue 3, March 1979, Pages 288-305.
Günter Meinardus, Zur additiven Zahlentheorie in mehreren Dimensionen, Teil I, Math. Ann. 132 (1956), 333-346. [Gives asymptotic growth]
N. J. A. Sloane, Transforms
FORMULA
G.f. for T(n, k): 1/Product_{i>=1, j>=1} (1 - w^i * z^j).
Recurrence: m*T(m, n) = Sum_{L>0, j>0, k>=0} j*T(m-L*j, n-L*k). [Cheema and Motzkin]
Also, Euler transform of the table whose g.f. is xy/((1-x)*(1-y)). - Christian G. Bower, Jun 03 2005
EXAMPLE
Triangle T(n,k) begins
1
1 1
1 2 1
1 2 2 1
1 3 4 3 1
The first row is for n=2. When n=6 and there are 3 balls of each color, the four partitions in question are bbbwww; bbww|bw; bw|bw|bw; bbw|bww.
Square array a(n,k) begins:
1 1 1 1 1 ...
1 2 2 3 3 ...
1 2 4 5 7 ...
1 3 5 9 12 ...
1 3 7 12 20 ...
CROSSREFS
KEYWORD
AUTHOR
Don Knuth, Feb 10 2004
EXTENSIONS
More terms from Christian G. Bower, Jun 03 2005
Entry revised by N. J. A. Sloane, Jul 07 2005
STATUS
approved