A054225 Triangle read by rows: row n (n>=0) gives the number of partitions of (n,0), (n-1,1), (n-2,2), ..., (0,n) respectively into sums of pairs.

1, 1, 1, 2, 2, 2, 3, 4, 4, 3, 5, 7, 9, 7, 5, 7, 12, 16, 16, 12, 7, 11, 19, 29, 31, 29, 19, 11, 15, 30, 47, 57, 57, 47, 30, 15, 22, 45, 77, 97, 109, 97, 77, 45, 22, 30, 67, 118, 162, 189, 189, 162, 118, 67, 30, 42, 97, 181, 257, 323, 339, 323, 257, 181, 97, 42, 56, 139, 267, 401, 522, 589, 589, 522, 401, 267, 139, 56

Offset: 0

Author

Marc LeBrun, Feb 04 2000

Keywords

• easy
• nonn
• tabl
• nice
• look

Comments

By analogy with ordinary partitions (A000041). The empty partition gives T(0,0)=1 by definition. A054225 and A201377 give partitions of pairs into sums of distinct pairs. Parts (i,j) are "positive" in the sense that min {i,j} >= 0 and max {i,j} >0. The empty partition of (0,0) is counted as 1.

Or, triangle T(n,k) of bipartite partitions of n objects, k of which are black.

Or, number of ways to factor p^(n-k)*q^k where p and q are distinct primes.

In the paper by F. C. Auluck: "On partitions of bipartite numbers", p.74, in the formula for fixed m there should be factor 1/m!. The correct asymptotic formula is p(m, n) ~ (sqrt(6*n)/Pi)^m * exp(Pi*sqrt(2*n/3)) / (4*sqrt(3)*m!*n). - Vaclav Kotesovec, Feb 01 2016

T(n,k)=T(n,k-n) is the number of multiset partitions of the multiset {1^k, 2^(n-k)}, see example link. - Joerg Arndt, Jan 01 2024

Let R be the ring of power series in two countably infinite sets of variables x_1,y_1,x_2,y_2,... that are invariant under the diagonal action (i.e, the group S of permutations of positive integers acts by w(x_i)=x_{w(i)} and w(y_i)=y_{w(i)}). Then T(n,k) is the dimension of the (n,k)-bigraded piece of R, i.e., the bihomogeneous power series of degree n in the x-variables and k in the y-variables that are S-invariant. - Jeremy L. Martin, Nov 27 2024

Examples

			The second row (n=1) is 1,1 since (1,0) and (0,1) each have a single partition.
The third row (n=2) is 2, 2, 2 from (2,0) = (1,0)+(1,0), (1,1) = (1,0)+(0,1), (0,2) = (0,1)+(0,1).
In the fourth row (n=3), T(2,1)=4 from (2,1) = (2,0)+(0,1) = (1,0)+(1,1) = (1,0)+(1,0)+(0,1).
The triangle begins:
   1;
   1,  1;
   2,  2,  2;
   3,  4,  4,  3;
   5,  7,  9,  7,   5;
   7, 12, 16, 16,  12,  7;
  11, 19, 29, 31,  29, 19, 11;
  15, 30, 47, 57,  57, 47, 30, 15;
  22, 45, 77, 97, 109, 97, 77, 45, 22;
  ...
A further example: T(2,2) = 9:
[(2,2)],
[(2,1),(0,1)],
[(2,0),(0,2)],
[(2,0),(0,1),(0,1)],
[(1,2),(1,0)],
[(1,1),(1,1)],
[(1,1),(1,0),(0,1)],
[(1,0),(1,0),(0,2)],
[(1,0),(1,0),(0,1),(0,1)].
		

References

• M. S. Cheema, Tables of partitions of Gaussian integers, National Institute of Sciences of India, New Delhi, 1956.
• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - N. J. A. Sloane, Dec 30 2018

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• Joerg Arndt, Multiset partitions of the multisets {1^r,2^s} for r+s=5.
• F. C. Auluck, On partitions of bipartite numbers, Proc. Cambridge Philos. Soc. 49, (1953). 72-83.
• F. C. Auluck, On partitions of bipartite numbers, annotated scan of a few pages.
• F. C. Auluck, On partitions of bipartite numbers, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 49, Issue 01, January 1953, pp. 72-83. (full article)
• P. A. MacMahon, Memoir on symmetric functions of the roots of systems of equations, Phil. Trans. Royal Soc. London, 181 (1890), 481-536; Coll. Papers II, 32-87.
• Reinhard Zumkeller, Haskell programs for A201376, A054225, A201377, A054242

Crossrefs

See A201376 for the same triangle formatted in a different way.

Columns 0-10: A000041, A000070, A000291, A000412, A000465, A000491, A002755, A002756, A002757, A002758, A002759.

Row sums: A005380. a(2n, n): A002774. a(n, [n/2]): A091437. Cf. A060244.

The outer edges are T(n,0) = T(0,n) = A000041(n).

A054242 gives partitions into sums of distinct pairs.

Programs

Haskell

see Zumkeller link.

Maple

read transforms; t1 := mul( mul( 1/(1-x^(i-j)*y^j), j=0..i), i=1..11): SERIES2(t1,x,y,6);

Mathematica

rows = 11; se = Series[ Product[ 1/(1-x^(n-k)*y^k), {n, 1, rows}, {k, 0, n}], {x, 0, rows}, {y, 0, rows}]; coes = CoefficientList[ se, {x, y}]; Flatten[ Table[ coes[[n-k+1, k]], {n, 1, rows+1}, {k, 1, n}]] (* Jean-François Alcover, Nov 21 2011, after g.f. *)
p = 2; q = 3; b[n_, k_] := b[n, k] = If[n>k, 0, 1] + If[PrimeQ[n], 0, Sum[If[d>k, 0, b[n/d, d]], {d, DeleteCases[Divisors[n], 1|n]}]]; t[n_, k_] := b[p^(n-k)*q^k, p^(n-k)*q^k]; Table[t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 13 2014, after Alois P. Heinz *)

PARI

{T(n, k) = if( n<0 || k<0, 0, polcoeff( polcoeff( prod( i=1, n, prod( j=0, i, 1 / (1 - x^i * y^j), 1 + x * O(x^n))),n),k))} /* Michael Somos, Apr 19 2005 */

Formula

G.f.: Product_{i>=1, j=0..i} 1/(1-x^(i-j)*y^j).

Series ends ... + 7*x^5 + 12*x^4*y + 16*x^3*y^2 + 16*x^2*y^3 + 12*x*y^4 + 7*y^5 + 5*x^4 + 7*x^3*y + 9*x^2*y^2 + 7*x*y^3 + 5*y^4 + 3*x^3 + 4*x^2*y + 4*x*y^2 + 3*y^3 + 2*x^2 + 2*x*y + 2*y^2 + x + y + 1.

Extensions

Entry revised by N. J. A. Sloane, Nov 30 2011, to incorporate corrections provided by Reinhard Zumkeller, who also contributed the alternative version A201376. Once the errors were corrected, this sequence coincided with A060243, due to N. J. A. Sloane, Mar 22 2001, which included edits by Vladeta Jovovic, Mar 23 2001, and Christian G. Bower, Jan 08 2004. The two entries have now been merged.