OFFSET
0,16
COMMENTS
The array a(n,k), called "Multiset choose 5", is also denoted by MS(5;n,k). It is the fifth member of an l-family of arrays for multiset choose l, called MS(l;n,k).
The row length of this array is A007294=[1, 1, 1, 2, 2, 2, 4, 4, 4, 6, 7, 7,...].
MS(5;n,k) gives for every multiset of the multiset repetition class encoded by the k-th multiset defining partition of n the number of ways to choose five elements from it. The Abramowitz-Stegun (A-St) order for partitions is used (see A036036).
For the characteristic array of multiset repetition class defining partitions of n in A-St order see A176723. See also the W. Lang link there and in A187447.
Note that multiset choose l should not be confused with N multichoose l (see, e.g., Wolfram's Mathworld). Here one picks from a multiset l=4 of its elements.
Ordinary sets appear exactly for n=T(N), with the triangular numbers T(N):=A000217(N). They are defined by the partition (1,2,...,N) for N>=1, and the empty partition for n=N=0. a(T(N),1)= binomial(N,5).
This investigation was stimulated by the Griffiths and Mező paper cited under A176725.
FORMULA
a(n,k) gives the number of ways to choose five elements from the multiset representative defined by the k-th multiset repetition class defining partition of n, with k=1,...,A007294(n).
a(n,k) = binomial(M(n,k)+4,5) -
sum(m(n,k)[4-p]*binomial(M(n,k)+p-1,p),p=0..3) +
m(n,k)[2]*m(n,k)[1] +
(M(n,k)-m(n,k)[1]+2)*binomial(m(n,k)[1],2) + 3*binomial(m(n,k)[1],3),
where M(n,k) = MS(1;n,k) := A176725(n,k), and m(n,k)[j] the j-th member of the multiplicity list m(n,k) of the exponents of the k-th multiset repetition class defining partition of n.
EXAMPLE
n=0..11:
0;
0;
0;
0, 0;
0, 0;
0, 1;
0, 0, 1, 1;
0, 1, 2, 1;
1, 2, 2, 1;
1, 3, 2, 3, 2, 1;
0, 3, 4, 3, 3, 2, 1;
1, 5, 4, 4, 3, 2, 1;
...
a(7,2)=MS(5;7,2)=1 because the second multiset repetition class defining partition of n=7 is [1^3,2^2] (from the characteristic array A176723) encoding the 5-multiset representative {1,1,1,2,2}, and there is 1 possibility to choose 5 elements from this set, namely 1,1,1,2,2.
a(T(4),1)=a(10,1)=MS(5;10,1) = 0 from the ordinary set {1,2,3,4} (defined by the multiset repetition class defining partition 1,2,3,4). This coincides with binomial(4,5)=0.
a(7,3)=MS(5;7,3)=2 from {1,1,1,1,1,2} choose 5 which is 2, namely 1,1,1,1,1 and 1,1,1,1,2. The corresponding multiset repetition class defining partition has exponent list [5,1] and this is the 16th in the A-St ordered list of such partitions (starting with the empty partition).
a(8,3) = 2 = binomial(2+4,5) - (0+0+0+binomial(2+2,3)) + 0 + 0 + 0 = 6-4, because the relevant partition has exponents [6,1] (corresponding to the 7-multiset representative {1,1,1,1,1,1,2}) with MS(1;8,3) = 2, and the multiplicity list of the exponents is m(8,3)=[1,0,0,0,0,1]. Hence m(8,3)[4], m(8,3[3] and m(8,2)[2] vanish, and m(8,2)[1]=1. The two choices are 1,1,1,1 and 1,1,1,2.
a(10,3)= 4 = binomial(3+4,5) - (0+0+0+binomial(3+2,3)*2) + 0 + 3 + 0 = 21-10*2 +3, corresponding to the 7-multiset representative {1,1,1,1,1,2,3} with MS(1;10,3)= 3, exponents [5,1,1] with multiplicity list m(10,3)=[2,0,0,0,1]. Hence m(10,3)[4], m(10,3)[3] and m(10,3)[2] vanish, and m(10,3)[1]=2. The four choices are 1,1,1,1,1; 1,1,1,1,2; 1,1,1,1,3 and 1,1,1,2,3.
CROSSREFS
KEYWORD
nonn,easy,tabf
AUTHOR
Wolfdieter Lang, Apr 04 2011
STATUS
approved