login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

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

LINKS

Table of n, a(n) for n=0..65.

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

FORMULA

Let denote sum_{l+u=k, l<=nl, u<=nu} 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).

EXAMPLE

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;

CROSSREFS

Cf. A007318, A000124, A004006, A007283.

Sequence in context: A078013 A086461 A047089 * A072405 A146565 A115594

Adjacent sequences:  A122215 A122216 A122217 * A122219 A122220 A122221

KEYWORD

nonn,tabl

AUTHOR

Thomas Wieder, Aug 27 2006

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 17 03:42 EDT 2021. Contains 347478 sequences. (Running on oeis4.)