login
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).
3
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,8
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
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)
EXAMPLE
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}.
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;
PROG
(PARI) A122218(n, k) = if(n>1, binomial(n, k)-binomial(n-2, k-1), 0) \\ M. F. Hasler, Jan 06 2024
CROSSREFS
Cf. A072405 (essentially the same).
Sequence in context: A078013 A086461 A047089 * A072405 A146565 A115594
KEYWORD
nonn,tabl
AUTHOR
Thomas Wieder, Aug 27 2006
STATUS
approved