3
$\begingroup$

I am familiar with how to calculate the number of subsets of size $k$ from a set with $n$ elements such that order matters, e.g.: both $\{a,b,c\}$ and $\{c,a,b\}$ are counted as separate, using the formula $\frac{n!}{(n-k)!}$. I also know that you can use the formula $\frac{n!}{k!(n-k)!}$ to calculate the number of subsets such that order doesn't matter, e.g.: $\{a,b,c\}$ and $\{c,a,b\}$ are counted as the same. Despite that, I don't know of any how to calculate the number of distinct subsets (including improper subsets) of a set that has repeated elements and can't find any information online. What I mean specifically by "distinct subsets" are two subsets $T$ and $U$ of a set $S$ where there exist a positive integer $i$ such that $T_i \neq U_i$ where $T_i$ and $U_i$ respectively represent the $i$th elements of $T$ and $U$. For this definition the empty set is not equal to any set except itself. If a set doesn't have any repeated elements I know that $\frac{n!}{(n-k)!}$ correctly calculates the number of distinct subsets.

Looking for a pattern I made the following calculations by hand, the first part of the list represents the base set ($S$ in the definition above) and the numbers that follow represent the number of distinct subsets of of size one, two, et cetera, with zeros omitted. The base sets are sorted in lexicographical (dictionary) order.

  1. $\{a\}$: 1
  2. $\{a,a\}$: 1,1
  3. $\{a,b\}$: 2,2
  4. $\{a,a,a\}$: 1,1,1
  5. $\{a,a,b\}$: 2,3,3
  6. $\{a,b,c\}$: 3,6,6
  7. $\{a,a,a,a\}$: 1,1,1,1
  8. $\{a,a,a,b\}$: 2,3,4,4
  9. $\{a,a,b,b\}$: 2,4,6,6
  10. $\{a,a,b,c\}$: 3,7,12,12

The main pattern of interest that I noticed is that for all of the sets the number of distinct subsets of size equal to the size of the base set and the number of size one less than the size of the base appear to always be the same, for example, for $\{a,a,b,b\}$ there are 6 distinct subsets of size 3 as well as size 4. I tried looking on the OEIS (On-line Encyclopedia of Integer Sequences) for the column sequences haven't found anything and the rows are too short that I can't personally find anything clear on the OEIS from them.

I'm unsure if there is a particular way I should be approaching this problem so any advice, work done by others investigating the problem, and/or resources would be greatly appreciate. As a note, while writing this question the StackExchange software listed the following questions as similar, in my opinion they seem related to me, but how to connect them to my question specifically I am not certain of: How many different permutations are there of the sequence of letters in “MISSISSIPPI”? [specific answer], How to find the number of distinct combinations of a non distinct set of elements? [question], and Permutations with fixed number of distinct elements [question].

$\endgroup$
1
  • $\begingroup$ I'm having a little trouble understanding you because it seems the grammar in your comment is slight off but if I understand you correctly, why is that the case, are you taking in to consideration double counting of sets that are not distinct, and are you willing to write a full answer? (Reply to now deleted comment) $\endgroup$
    – Aaron Quitta
    Commented Aug 17, 2019 at 2:29

2 Answers 2

Reset to default
2
$\begingroup$

Let $E_{m}(x)=\sum_{j=0}^m x^j/j!$ be the $m^{th}$ partial sum of the exponential series. If a multiset $M$ has $r$ distinct elements, where the first element is repeated $n_1$ times, the second $n_2$ times, etc, then the number of ways to choose an ordered list consisting of $k$ elements of $M$ is equal to $$ k![x^k]\prod_{i=1}^rE_{n_i}(x).\tag{*} $$ Here, $[x^k]f(x)$ denotes the coefficient of $x^k$ in the polynomial $f(x)$.

For example, consider the multiset $\{a,a,b,c\}$ from your post. There are $3$ distinct elements, the first, $a$, appearing $n_1=2$ times, and the latter two, $b$ and $c$, appearing $n_2=n_3=1$ time. The product of the partial exponential sums in $(*)$ is therefore \begin{align} E_{2}(x)\cdot E_1(x)\cdot E_1(x) &=(1+x+x^2/2)\cdot(1+x)\cdot(1+x) \\&=1+3x+\frac{7}2x^2+2x^3+\frac12x^4 \\&=1+\frac{\color{red}3}{1!}x+\frac{\color{red}7}{2!}x^2+\frac{\color{red}{12}}{3!}x^3+\frac{\color{red}{12}}{4!}x^4\end{align} Notice that the coefficients of this polynomial correspond to the answer to your combinatorial question $(3,7,12,12)$, divided by an appropriate factorial.

The techniques used in this post are more widely known as exponential generating functions. For more of an explanation on why this works, see generatingfunctionology by Herbert Wilf, especially chapter 3 on exponential generating functions. It is available for free online.

$\endgroup$
4
  • $\begingroup$ Is there a particular name for the $[x^{k}]f(x)$ notation? Is the chapter section that you are specifically referring to 3.3 "Examples of exponential families"? $\endgroup$
    – Aaron Quitta
    Commented Aug 17, 2019 at 3:42
  • $\begingroup$ @AaronQuitta I think $[x^k]$ is referred to as the "coefficient operator" or the "coefficient-of operator." See this Knuth paper and the references therein for some more discussion. $\endgroup$
    – Mike Earnest
    Commented Aug 17, 2019 at 3:51
  • $\begingroup$ Awesome, thank you. Is it appropriate for me to accept this answer even though I don't understand how/why it is correct? $\endgroup$
    – Aaron Quitta
    Commented Aug 17, 2019 at 4:19
  • $\begingroup$ @AaronQuitta Both accepting/not accepting are appropriate. I certainly would understand you not accepting; I did not take the effort to fully explain, since I am a little rusty in this area :P Perhaps someone will come along later and explain more. $\endgroup$
    – Mike Earnest
    Commented Aug 17, 2019 at 4:26
1
$\begingroup$

The best I can do is with generating functions.

Specifically, if we define $A(n;m_1,m_2,\ldots,m_k)$ as the number of distinct sequences of length $n$ from a multiset with $m_i$ copies of $i$ for $1 \leq i \leq k.$ Then $$\prod_{i=1}^k \sum_{p=0}^{m_i} \frac{x^p}{p!} = \sum_{n=0}^\infty A(n;m_1,m_2,\ldots,m_k) \frac{x^n}{n!}$$ which we probably can manipulate to find a recursive definition for $A.$

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! I had never heard the term 'multiset' before but thats exactly what I am thinking of! I am unclear on how exactly the sums/product arise from your description and what specifically my answer is, is it the function $A$ the generating function of $A$, or something else? What do you mean by "manipulate to find a recursive definition for A"? $\endgroup$
    – Aaron Quitta
    Commented Aug 17, 2019 at 2:57
  • $\begingroup$ @AaronQuitta If I've understood your question, your answer would be the function $A$ (depending on $k+1$ variables) The problem is that most generating functions like this yield at best finite sums of simple expressions or recursive formulas. In this case, the only obvious value is when $\sum_i m_i = n,$ in which case $A$ is just the multinomial coefficient $\binom{n}{m_1,m_2,\ldots,m_k},$ so we may be able to use this as a base case in a recursive definition (e.g. try taking the derivative of the generating function and compare coefficients) $\endgroup$
    – Brian Moehring
    Commented Aug 17, 2019 at 3:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .