login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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; refs; listen; history; text; internal format)
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).

Garsia and Gessel, Advances in Math. 31 (1979), 288-305.

LINKS

Table of n, a(n) for n=2..87.

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[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, 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: A180980 A275298 A048570 * A241926 A174446 A071201

Adjacent sequences:  A090803 A090804 A090805 * A090807 A090808 A090809

KEYWORD

easy,nonn,tabl

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 07:58 EST 2018. Contains 299365 sequences. (Running on oeis4.)