|
Search: id:A090806
|
|
|
| A090806 |
|
Triangular array read by rows: T(n,k) (n >= 2, 1 <= k <= n) = number of partitions of k white balls and n-k black balls in which each part has at least one ball of each color. Also limit of the joint major-index / inversion polynomial for permutations of n elements, as n becomes infinite. |
|
+0
3
|
|
| 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 3, 4, 3, 1, 1, 3, 5, 5, 3, 1, 1, 4, 7, 9, 7, 4, 1, 1, 4, 9, 12, 12, 9, 4, 1, 1, 5, 11, 17, 20, 17, 11, 5, 1, 1, 5, 13, 22, 28, 28, 22, 13, 5, 1, 1, 6, 16, 29, 40, 45, 40, 29, 16, 6, 1, 1, 6, 18, 35, 53, 64, 64, 53, 35, 18, 6, 1, 1, 7, 21, 44, 70, 91, 100, 91
(list; table; graph; listen)
|
|
|
OFFSET
|
2,5
|
|
|
COMMENT
|
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 (bowerc(AT)usa.net), 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
|
M. S. Cheema and T. S. Motzkin, "Multipartitions and multipermutations," Proc. Symp. Pure Math. 19 (1971), 39-70, eq. (3.1.3).
Garsia and Gessel, Advances in Math. 31 (1979), 288-305.
G\"unter Meinardus, "Zur additiven Zahlentheorie in mehreren Dimensionen. I," Math. Ann. 132 (1956), 333-346. [Gives asymptotic growth]
|
|
LINKS
|
G. Meinardus, Zur additiven Zahlentheorie in mehreren Dimensionen, Teil I, Math. Ann. 132 (1956), 333-346.
N. J. A. Sloane, Transforms
|
|
FORMULA
|
G.f. for T(n, k): 1/Product[1-w^i z^j, {i, Infinity}, {j, Infinity}]
Recurrence: m T(m, n) = sum_{l>0, j>0, k>=0} j T(m-lj, n-lk) [Cheema and Motzkin]
Also, Euler transform of the table whose g.f. is xy/((1-x)*(1-y)). - Christian G. Bower (bowerc(AT)usa.net), 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
|
Cf. A108461. Main diagonal: A108469.
Sequence in context: A081206 A156044 A048570 this_sequence A071201 A106476 A101566
Adjacent sequences: A090803 A090804 A090805 this_sequence A090807 A090808 A090809
|
|
KEYWORD
|
easy,nonn,tabl
|
|
AUTHOR
|
D. E. Knuth, Feb 10 2004
|
|
EXTENSIONS
|
More terms from Christian G. Bower (bowerc(AT)usa.net), Jun 03 2005
Entry revised by N. J. A. Sloane (njas(AT)research.att.com), Jul 07 2005
|
|
|
Search completed in 0.002 seconds
|
