Suppose we are given $k$ ordered blanks (e.g. a length $k$ word) and $n$ types of objects. Also we have $k>n$. Now we want to fill in these blanks with these objects so that we at least use one object of each kind. In how many ways can we fill these blanks?

The following are my thought: clearly there would be repetitions as the number of blanks is larger than the number of types of objects. I could figure out some cases when plug in certain numbers for $n$ and $k$. But is there a general formula for this?

  • 1
    $\begingroup$ You can use the Inclusion-Exclusion Principle. There are $n^k$ ways to fill the blanks since there are $n$ choices for each of the $k$ blanks. However, we want to exclude those distributions which exclude one or more types of objects. Does that help? $\endgroup$ Oct 13 at 22:06
  • 1
    $\begingroup$ @NFTaussig Isn't this just ordered Stirling numbers $n!S(k,n)$? $\endgroup$ Oct 13 at 22:07
  • $\begingroup$ For an initial exposure to Inclusion-Exclusion, see this article. For a guide to setting up an Inclusion-Exclusion framework, see the first part of this answer. ...see next comment $\endgroup$ Oct 14 at 0:27
  • $\begingroup$ Using N.F. Taussig's comment, and using the syntax in the first part of my answer, for $i \in \{1,2,\cdots,n\}$, let $A_i$ denote the set of $k$ length characters, where character $i$ is excluded. Then, everything should fall into place. $\endgroup$ Oct 14 at 0:29
  • $\begingroup$ @ParclyTaxel It would help if you could give the OP a link to a corresponding article, perhaps a Wikipedia article. I didn't do this because I was unsure and didn't want to cite the wrong article. Once this is done, the OP can compare the results in the posted article with the results obtained by implementing Inclusion-Exclusion, from scratch. $\endgroup$ Oct 14 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.