2
$\begingroup$

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\}...$

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – whuber
    Aug 31, 2015 at 20:29
  • $\begingroup$ I have re-edited the questions so it is clearer now $\endgroup$
    – Hashed
    Aug 31, 2015 at 20:41

3 Answers 3

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Hashed
    Sep 2, 2015 at 22:26
  • $\begingroup$ 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. $\endgroup$
    – Creosote
    Sep 3, 2015 at 6:14
1
$\begingroup$

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.

The answer therefore is

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

$\endgroup$
5
  • $\begingroup$ 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$ $\endgroup$
    – Hashed
    Sep 1, 2015 at 22:19
  • $\begingroup$ @Hashed It won't be undefined--it will be zero in such cases. $\endgroup$
    – whuber
    Sep 1, 2015 at 22:19
  • $\begingroup$ 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? $\endgroup$
    – Hashed
    Sep 2, 2015 at 6:45
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Sep 2, 2015 at 14:09
  • $\begingroup$ I have re-edited it with example also.. I hope it helps and thanks a lot for your help $\endgroup$
    – Hashed
    Sep 2, 2015 at 22:35
0
$\begingroup$

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.$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Hashed
    Sep 1, 2015 at 7:09
  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Sep 1, 2015 at 7:49
  • $\begingroup$ 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 $\endgroup$
    – Hashed
    Sep 1, 2015 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.