A122218 Pascal array A(n,p,k) for selection of k elements from two sets L and U with n elements in total whereat the nl = n - p elements in L are labeled and the nu = p elements in U are unlabeled and (in this example) with p = 2 (read by rows).

0, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 4, 3, 1, 1, 4, 7, 7, 4, 1, 1, 5, 11, 14, 11, 5, 1, 1, 6, 16, 25, 25, 16, 6, 1, 1, 7, 22, 41, 50, 41, 22, 7, 1, 1, 8, 29, 63, 91, 91, 63, 29, 8, 1, 1, 9, 37, 92, 154, 182, 154, 92, 37, 9, 1

Offset: 0

Author

Thomas Wieder, Aug 27 2006

Keywords

• nonn
• tabl

Comments

See Maple's command choose applied to lists (not sets): e.g., with p = 3 choose([1,2,a,a],3) gives [[1, 2, a], [1, a, a], [2, a, a]]. Furthermore nops(choose([1,2,a,a],3)) gives 3. For p = 0 one gets the usual Pascal triangle. For p=2 and k=2 we have the sequence 1,2,4,7,11,16,22,29,37,... = A000124 = Central polygonal numbers. For p=2 and k=3 we have the sequence 3,7,14,25,41,63,92,... = A004006 = C(n,1)+C(n,2)+C(n,3), or n*(n^2+5)/6. For p=2 the row sums form sequence A007283 = 3*2^n.

This is a triangular array like the Pascal triangle. [I.e., T(n+1,k) = T(n,k-1) + T(n,k) for n <> 1, cf. formulas. - M. F. Hasler, Jan 06 2024]

It appears that for n > 2, a(n) = A072405(n) (C(n,k)-C(n-2,k-1)). - Gerald McGarvey, Sep 30 2008

Examples

			From _M. F. Hasler_, Jan 06 2024: (Start)
The triangle T(n,k) := A(n,2,k) starts:
  n |row(n) = (A(n,2,0), ..., A(n,2,n))
----+------------------------------------
  0 | 0,
  1 | 0, 0,
  2 | 1, 1,  1,
  3 | 1, 2,  2,  1,
  4 | 1, 3,  4,  3,   1,
  5 | 1, 4,  7,  7,   4,   1,
  6 | 1, 5, 11, 14,  11,   5,   1
  7 | 1, 6, 16, 25,  25,  16,   6,  1,
  8 | 1, 7, 22, 41,  50,  41,  22,  7,  1,
  9 | 1, 8, 29, 63,  91,  91,  63, 29,  8, 1,
  10| 1, 9, 37, 92, 154, 182, 154, 92, 37, 9, 1
(End)
For n = 4 and p = 2 we have nl = 2, nu = 2 and we have the sets L = {1,2} and U = {a,a}, or L+U = {1,2,a,a}.
Then for k = 1 we have A(4,2,1) = 3 because we can select {1}, {2}, {a}.
Then for k = 2 we have A(4,2,2) = 4 because we can select {1,2}, {1,a}, {2,a}, {a,a}.
Then for k = 3 we have A(4,2,3) = 3 because we can select {1,2,a}, {1,a,a,}, {2,a,a}.
Then for k = 4 we have A(4,2,4) = 1 because we can select {1,2,a,a}.
For n = 4 and p = 3 we have nl = 1, nu = 3 and we have the sets L = {1} and U = {a,a,a}, or L+U = {1,a,a,a}.
Then for k = 1 we have A(4,3,1) = 2 because we can select {1}, {a}.
Then for k = 2 we have A(4,3,2) = 2 because we can select {1,a}, {a,a}.
Then for k = 3 we have A(4,3,3) = 2 because we can select {1,a,a}, {a,a,a,}.
Then for k = 4 we have A(4,3,4) = 1 because we can select {1,a,a,a}.
		

Links

• H. S. Wilf, Lecture notes on combinatorics and Maple.

Crossrefs

Cf. A007318, A000124, A004006, A007283.

Cf. A072405 (essentially the same).

Programs

Maple

CallPascalLU := proc() local n,p,k,nl,nv; global result,ierr;
for n from 0 to 10 do p:=2; nl:=n-p; nv:=p; for k from 0 to n do PascalLU(n,nl,nv,k,result,ierr); if ierr <> 0 then print("An error has occured!"); fi; print("CallPascalLU: n, p, k, C(n,p,k):",n,p,k,result); end do; end do; end proc;
PascalLU := proc(n::integer,nl::integer,nv::integer,k::integer)
local i,l,u,prttn,prttnlst,swap;
global result,ierr;
ierr:=0;
if nl+nv <> n or k > n or n < 0 or k < 0 then ierr=1; return; fi;
prttnlst:=NULL;
result:=0;
if k>=2 then
prttnlst:=PartitionList(k,2);
prttnlst:=op(prttnlst);
end if;
prttnlst:=prttnlst,[k,0];
prttnlst:=[prttnlst];
#print("PascalLU: n, k, prttnlst:",n,k,prttnlst);
for i from 1 to nops(prttnlst) do
prttn:=op(i,prttnlst);
l:=op(1,prttn);
u:=op(2,prttn);
#print("PascalLU: i, prttn, l, u:",i,prttn,l,u);
if l <= nl and u <= nv then
result:=result+binomial(nl,l)*binomial(u,u);
end if;
swap:=u; u:=l; l:=swap;
if l <> u and l <= nl and u <= nv then
result:=result+binomial(nl,l)*binomial(u,u);
end if;
end do;
#print("n,k,result",n,k,summe)
end proc;
PartitionList := proc (n, k)
# Herbert S. Wilf and Joanna Nordlicht,
# Lecture Notes "East Side West Side,..."
# Available from Wilf link.
# Calculates the partitions of n into k parts.
# E.g. PartitionList(5,2) --> [[4, 1], [3, 2]].
local East, West;
if n < 1 or k < 1 or n < k then
RETURN([])
elif n = 1 then
RETURN([[1]])
else if n < 2 or k < 2 or n < k then
West := []
else
West := map(proc (x) options operator, arrow;
[op(x), 1] end proc,PartitionList(n-1,k-1)) end if;
if k <= n-k then
East := map(proc (y) options operator, arrow;
map(proc (x) options operator, arrow; x+1 end proc,y) end proc,PartitionList(n-k,k))
else East := [] end if;
RETURN([op(West), op(East)])
end if;
end proc;

PARI

A122218(n,k) = if(n>1, binomial(n,k)-binomial(n-2,k-1), 0) \\ M. F. Hasler, Jan 06 2024

Formula

Let Sum_{l+u = k, l <= nl, u <= nu} denote the sum over all integer partitions [l,u] of k into the 2 parts l and u with the following properties:

1.) l <= nl, u <= nu,

2.) [l,u] and [u,l] are considered as two different partitions,

3.) but the partition [l=k/2, u=k/2], i.e., if l=u, is taken only once,

4.) [l=k,0] and [0, u=k] are considered to be partitions of k into 2 parts also. As usual, C(nl,l) and C(u,u) are binomial coefficients ("nl choose l" and "u choose u"). The Pascal array A(nl,l,nu,u,k) = A(n,p,k) gives the number of possible sets which can be taken from L and U (with elements either from both sets L and U or just from one of the sets L or U). Then A(n,p,k) = Sum_{l+u=k, l<=nl, u<=nu} C(n-p,l,k) C(u,u).

From M. F. Hasler, Jan 06 2024: (Start)

T(n,k) = A(n,2,k) = C(n,k) - C(n-2,k-1) except for (n,k) = (0,0) and (1,0).

Pascal-type triangle: T(n+1,k) = T(n,k-1)+ T(n,k) for all n <> 1, with T(n,k) = 0 for k < 0 or k > n. (End)