A187445 Number of ways to choose two elements from the multiset representative corresponding to the k-th multiset repetition class defining partition of n in Abramowitz-Stegun order.

0, 0, 1, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 5, 4, 3, 3, 2, 1, 6, 5, 4, 3, 3, 2, 1, 7, 5, 4, 3, 3, 2, 1, 7, 6, 5, 5, 3, 4, 3, 3, 2, 1, 8, 7, 6, 5, 5, 3, 4, 3, 3, 2, 1, 8, 7, 6, 5, 5, 3, 4, 3, 3, 2, 1, 10, 8, 6, 7, 6, 5, 5, 3, 5, 3, 4, 3, 3, 2, 1, 11, 9, 8, 8, 6, 7, 6, 5, 5, 3, 5, 3, 4, 3, 3, 2, 1, 11, 9, 8, 8, 6, 7, 6, 5, 5, 3, 5, 3, 4, 3, 3, 2, 1, 12, 11, 9, 6, 8, 6, 8, 6, 5, 7, 6, 5, 3, 5, 3, 5, 3, 4, 3, 3, 2, 1, 12, 11, 9, 9, 8, 6, 8, 6, 8, 6, 5, 7, 6, 5, 3, 5, 3, 5, 3, 4, 3, 3, 2, 1, 10, 12, 11, 9, 9, 8, 6, 8, 6, 8, 6, 5, 7, 6, 5, 3, 5, 3, 5, 3, 4, 3, 3, 2, 1

Offset

0,6

Comments

This array a(n,k), called (Multiset choose 2), is also denoted by MS(2;n,k).

MS(2;n,k) gives the number of ways to choose two elements from the multiset encoded by the k-th multiset repetition class defining partition of n. The Abramowitz-Stegun (A-St) order for partitions is used (see A036036).

The row lengths of this array are A007294(n).

For the characteristic array of multiset repetition class defining partitions of n in A-St order see A176723.

This is the second member of an l-family of arrays for multiset choose l, called MS(l;n,k).

For a list of the multiset repetition class defining partitions of n=1..15 see the link under A176725. For n=0 the empty partition appears.

Note that multiset choose k should not be confused with N multichoose k (see, e.g., Wolfram's Mathworld). Here one picks from a multiset k=2 of its elements.

Ordinary sets appear exactly for n=T(N), N>=1, with the triangular numbers T(N):=A000217(N). They are defined by the partitions 1,2,...,N, and a(T(N),1)= binomial(N,2).

References

See A176725.

Links

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

Formula

a(n,k) gives the number of ways to choose two elements from the multiset defined by the k-th multiset defining partition of n, with k=1,...,A007294(n).

a(n,k) = binomial(MS(1;n,k)+1,2) - m(n,k)[1], with MS(1;n,k):=A176725(n,k), and m(n,k)[1] the first member of the multiplicity list m(n,k) of the exponents of the k-th multiset defining partition of n.

Example

n=0..10:
[0],
[0],
[1],
[1, 1],
[2, 1],
[2, 1],
[3, 3, 2, 1],
[4, 3, 2, 1],
[4, 3, 2, 1],
[5, 4, 3, 3, 2, 1],
[6, 5, 4, 3, 3, 2, 1],
...
a(6,2)=MS(2;6,2)=3 because the second multiset repetition class defining partition of n=6 is 1^2,2^2 (from the characteristic array A176723) encoding the 4-multiset representative {1,1,2,2}, and there are 3 ways to choose 2 elements from this set, namely 1,1; 2,2; and 1,2.
a(T(4),1)=a(10,1)=MS(2;10,1) = 6, from the ordinary set {1,2,3,4} (defined by the multiset repetition class defining partition 1,2,3,4), coinciding with binomial(4,2).
a(8,2)= 3 = binomial(2+1,2) - 0, because the relevant partition has exponents [4,2] (corresponding to the 6-multiset {1,1,1,1,2,2})  with MS(1;8,2)= 2, and the multiplicity list of the exponents is m(8,2)=[0,1,0,1], hence m(8,2)[1]=0.
a(10,3)= 4 = binomial(3+1,2) - 2, corresponding to the 7-multiset {1,1,1,1,1,2,3} with MS(1;10,3)= 3 and exponents [5,1,1] with multiplicity m(10,3)=[2,0,0,0,1], hence m(10,3)[1]=2.

Crossrefs

Cf. A176725 MS(1;n,k), A187449 MS(3;n,k).

Sequence in context: A309892 A078899 A055172 * A318362 A213237 A029334

Adjacent sequences: A187442 A187443 A187444 * A187446 A187447 A187448

Keyword

nonn,tabf

Author

Wolfdieter Lang, Mar 11 2011

Extensions

Changed in response to comments by Franklin T. Adams-Watters - Wolfdieter Lang, Apr 02 2011.

Status

approved