I think A059576 if read as a square array rather than as a triangle. This is essentially compositions (ordered partitions) of two colored objects. Think of a compartment of i white objects and j black objects as being i indices of a and j indices of b that are equal. Christian ID Number: A059576 URL: http://www.research.att.com/projects/OEIS?Anum=A059576 Sequence: 1,1,1,2,3,2,4,8,8,4,8,20,26,20,8,16,48,76,76,48,16,32,112, 208,252,208,112,32,64,256,544,768,768,544,256,64,128,576, 1376,2208,2568,2208,1376,576,128,256,1280,3392,6080,8016, 8016,6080,3392,1280,256 Name: Summatory Pascal triangle T(n,k) (0 <= k <= n) read by rows. Top entry is 1. Each entry is the sum of the parallelogram above it. Comments: We may also relabel the entries as U(0,0), U(1,0), U(0,1), U(2,0), U(1,1), U(0,2), U(3,0), ... U(n,k)=Sum_{i<n,j<k} U(i,j)= 2U(n-1,k) + Sum_{i<k} U(n,i). Also U(n,k)=Sum_{j=0..n+k} C(n,j-k+1)*C(k,j-n+1)*2^j - Jon Stadler (jstadler(AT)capital.edu), Apr 30 2003 U(n,k) is the number of ways of writing the vector (n,k) as an ordered sum of vectors, equivalently, the number of paths from (0,0) to (n,k) in which steps may be taken from (i,j) to (p,q) provided (p,q) is to the right and/or above (i,j). - Jon Stadler (jstadler(AT)capital.edu), Apr 30 2003 Links: Index entries for triangles and arrays related to Pascal's triangle Formula: G.f. U(z,w) = Sum_{n >= 0, k >= 0} U(n,k)*z^n*w^k = Sum{n >= 0, k >= 0} T(n,k)*z^(n-k)*w^k = (1-z)*(1-w)/(1-2*w-2*z+2*z*w). Maple code gives another explicit formula for U(n,k). T(n,k)=2*(T(n-1,k-1)+T(n-1,k))-(2-0^(n-2))*T(n-2,k-1) for n>1 and 1<k<n, T(n,0)=T(n,n)=2*T(n-1,0) for n>0, T(0,0)=1. - Reinhard Zumkeller (reinhard.zumkeller(AT)lhsystems.com), Dec 03 2004 Example: 1; 1,1; 2,3,2; 4,8,8,4; ... T(5,2) is the sum of the elements above it in the parallelogram bordered by T(0,0), T(3,0), T(2,2) and T(5,2). Maple: A059576 := proc(n,k) local b,t1; t1 := min(n+k-2,n,k); add( (-1)^b * 2^(n+k-b-2) * (n+k-b-2)! * (1/(b! * (n-b)! * (k-b)!)) * (-2 * n-2 * k+2 * k^2+b^2-3 * k * b+2 * n^2+5 * n * k-3 * n * b), b=0..t1); end; See also: Cf. A035002, A059226, A008288, A059283. First diagonals give A000079, A001792. T(2n, n) gives A052141. Row sums give A003480. Keywords: easy,nonn,tabl,nice Offset: 0 Author(s): Floor van Lamoen (f_DOT_v_DOT_lamoen_AT_wxs_DOT_nl), Jan 23 2001 ------ Original Message ------ Received: Mon, 03 Oct 2005 04:03:20 PM PDT From: "David Wilson" <davidwwilson@comcast.net> To: "Math-Fun" <math-fun@mailman.xmission.com> Subject: [math-fun] Counting problem
Suppose we have m numbers a_1 <= a_2 <= ... <= a_m, and n numbers b_1 <= b2
<= ... <= b_n.
How many different ways can the a_i and b_i be related with < and = ?
For example, if m = 2 and n = 2, two possible arrangements are
a1 < a2 = b1 < b2 (considered equivalent to a1 < b1 = a2 < b2) b1 < a1 = a2 = b2
-------------------------------- - David Wilson