Number of combinations from a set with certain rules

Suppose I would like to select $m$ integers from the set $S=\{1,2,...,n\}$ with the following rules:

1) $j$ out of $m$ are necessarily distinct. Denote this as $S_1$

2) the rest $m-j$ are selected from a subset of $S_2$ of $S$ of size of $i<=n$ that contains also $S_1$ (allowing any integer from $S_2$ to be selected more than once).

I would like to compute the number of such "subsets" (no strictly speaking a set as we allow repetitions of elements) of size $m$ and compute the probability that a given "set" of size $m$ will have this property if chosen uniformly at random.

Example: Suppose $S=\{1,2,3,4,5,6,7,8\}$, $m=5$, $S_1=\{1,2,3\}$ (i.e. $j=3$) $S_2=\{1,2,3,4,7,8\}$, then possible candidates are: $\{1,2,3,1,2\},\{1,2,3,4,7\},\{1,2,3,1,1\},\{1,2,3,8,8\},\{1,2,3,3,8\}...$

• It is difficult to tell precisely what you are asking, because several distinct interpretations are possible. Could you perhaps give a small example or two?
– whuber
Aug 31, 2015 at 20:29
• I have re-edited the questions so it is clearer now Aug 31, 2015 at 20:41

Are you simply asking for the number of size-$m$ multisets of $1,\ldots,n$ such that there are anywhere from $j$ up to $i$ distinct elements in the multiset?

That would be $\sum_{k=j}^{k=i}\binom{n}{k}\binom{m-1}{k-1}$, where the binomial coefficients are understood to be zero for "bad" parameters, I think.

• The idea is that there are certainly $j$ different integers in the set and the rest $m-j$ are selected from a set of size $i$ that contains also the $j$ already selected integers... allowing also elements to appear multiple times ...Is your formulae correct or it should be $m-1$?... also where does your formulae captures the fact that integers can appear many times in the "set" selection? Sep 2, 2015 at 22:26
• If you're after a formula F(n,m,i,j), i.e. that specifies only the size, not the content, of those $S$-sets, then what I quoted looks okay on toy examples. For example my F(4,3,2,1) = 16, which counts these ways of picking from {0,1,2,3}: 000 001 002 003 011 022 033 111 112 113 122 133 222 223 233 333. Sep 3, 2015 at 6:14

Your selection is uniquely determined by these data:

1. The set of $j+i$ distinct integers in it.

2. The $j$ unique integers in it.

3. The multiplicities of the remaining $i$ integers.

For instance, an example of the case $n=8, j=2, i=2, m=7$ is the multiset $12^235^3$ (representing the tuple $(1,2,2,3,5,5,5)$ up to permutation). There must be exactly $j=2$ elements with no explicit power in this notation and $i=2$ elements with powers of $2$ or greater. Furthermore, the sum of all the powers is $m$.

If we subtract $2$ from all the powers of the $i$ repeated elements, the powers that are left must sum to $m - j - 2i$. In the example, the powers of the repeated elements are $2$ and $3$; subtracting $2$ from each and adding gives $0+1 = 7 - 2 - 2(2)$.

Consequently, the number of these sets equals

• The number of $j+i$-subsets of $[n]$, equal to $\binom{n}{j+i}$;

• Times the number of $j$-subsets of $[j+i]$, equal to $\binom{j+i}{j}$;

• Times the number of ordered partitions of $m - j - 2i$ things into $i$ parts of size $0$ or larger.

The last can be counted by writing those $m-j-2i$ things down and inserting $i-1$ breaks between them. Those are in one-to-one correspondence with all the ways of selecting $i-1$ positions out of $m-j-2i+(i-1) = m-j-i-1$ locations, as explained at https://math.stackexchange.com/questions/31562.

$$\binom{n}{j+i}\binom{j+i}{j}\binom{m-j-i-1}{i-1}.$$

• I dont think it is correct as the third term in your product could be undefined due to the fact that $i<=n$ could be greater than $m$ Sep 1, 2015 at 22:19
• @Hashed It won't be undefined--it will be zero in such cases.
– whuber
Sep 1, 2015 at 22:19
• Thanks. I have a few comments. There are in total $i$ distinct integers that we choose for our set and not $i+j$. The idea is that $S_1$ contains $j$ distinct integers and lets say $S_2$ (of cardinality $i$) contains $S_1$ and another $i-j$ integers which are distinct. We want to compute number of sets s.t all $j$ integers of $S_1$ appear at least once in each "set" selection and the rest $m-j$ can be from $S_2$ allowing multiplicities. Can you please modify the formulae and confirm you viewed the problem this way? Sep 2, 2015 at 6:45
• If you are using $i$ for the total number of distinct integers, then please edit your post to clarify that point, because that is not what it appears to say. I would like to reiterate my original request for a small example: that will clear things up for all your readers.
– whuber
Sep 2, 2015 at 14:09
• I have re-edited it with example also.. I hope it helps and thanks a lot for your help Sep 2, 2015 at 22:35

Not sure if I understood the question correctly.

There are $n \choose j$ subsets of size $j.$ For each of these choices you then choose $m-j$ points freely (allowing duplicates) from subset $S_1\subset S$ of size $i.$ Thus $i\geq j$.

Let's fix $i.$ For the remainder of the points, you are looking at the number of all functions from $\{1,2,\ldots,m-j\}$ to a set of size $i,$ and there are $i^{m-j}$ such choices.

If $i$ is fixed and specified, the answer is ${n \choose j} i^{m-j}.$ If you are interested in the total number of choices for $i$ in the range $j,j+1,\ldots,n$ you may need to use inclusion exclusion. However, since any solution for a given $i>j$ is also a valid solution for $i'\in \{j+1, \ldots,i\}$ I feel that the answer should be $${n \choose j} n^{m-j}$$ since we can take $i=n.$

• So based on this the proportion of m-tuples with this property is $\dbinom{n}{j}i^{m-j}/n^m$.?? However, in this case there is an issue when selecting for the m-j cases an integer or integers that have been selected before. Sep 1, 2015 at 7:09
• Well, I misinterpreted your statement. Maybe you should have said the remaining are selected from a subset $S_1 \setminus S$ of size $i$? Or is it a subset $S_1 \setminus S$ of size $i-j$? Specify your question more fully and it should be possible to modify the answer. Sep 1, 2015 at 7:49
• The remaining $m-j$ are selected from a subset of $S$ of size $j<=i<=n$ that contains $S_1$ (the set of $j$ already selected). In this case we allow repetitions of integers, e.g. pick twice an integer from set $S_1$. The big problem is that in the selection of $m-j$ if you pick an element from $S_1$ again then this combination is measured twice by your formulae Sep 1, 2015 at 9:24