0
$\begingroup$

How do I calculate the possible number of combinations (order does not matter, repetition allowed) for $n$ items taking $1...p$ items. For Example:

Suppose there are 3 letters - $P$, $Q$ and $R$.

So, the number of combinations would be :

$1$ Item $\to3$ ($P$, $Q$ and $R$)
$2$ Items $\to6$ ($PQ$, $QR$, $RP$ $PP$, $QQ$, and $RR$)

Total $\to(3+6)$ or $9$.

Edit - It seems I am not being able to frame the question correctly. What I am trying to achieve is the total number of possible words with max length of $P$ formed with the alphabet.

  • Repetition of letters allowed.
  • Capitalization matters.
$\endgroup$
4
  • $\begingroup$ if repetition is allowed, then why aren't $PP,QQ,RR$ valid? $\endgroup$
    – lulu
    Commented Dec 9, 2015 at 21:11
  • $\begingroup$ Your examples contradicts your statement "repetition allowed". If so, then $PP,QQ,RR$ should be in two item selection $\endgroup$
    – user249332
    Commented Dec 9, 2015 at 21:11
  • $\begingroup$ I am really sorry. Posted the correct thing now. $\endgroup$ Commented Dec 9, 2015 at 21:14
  • $\begingroup$ @SubhadeepDey I have edited my question. Please read it once more. $\endgroup$ Commented Dec 9, 2015 at 21:23

2 Answers 2

3
$\begingroup$

With the conditions that "repetitions are allowed" and "order does not matter", a solution is fully given by how many copies of each letter it contains. So we're looking for the number of nonnegative integer solutions to $$ 0 < x_1 + x_2 + x_3 + \cdots + x_n \le p $$ This is easier to solve if we add an additional variable to get the sum up to exactly $p$: $$ \tag{*} x_1 + x_2 + x_3 + \cdots + x_n + y = p $$ where we then have to exclude the solution where $y=p$ and all the $x_i$ are zero. But it will be easy to subtract one at the end.

The number of solutions to $\text{(*)}$ is a typical stars-and-bars problem with $p$ stars and $n$ bars, corresponding to the $n$ plus signs on the left-hand side. There are $\binom{n+p}{n}$ different solutions, and excluding the $(0,0,\ldots,0,p)$ solution the count is now $$ \binom{n+p}{n} - 1 $$

$\endgroup$
0
1
$\begingroup$

Note: This answers an earlier version of the question.

From your example it looks like you're for the number of non-empty subsets of a set with $n$ elements?

There are $2^n$ subsets in total, but one of them is the empty set, which it looks like you don't want to count. So subtract one from $2^n$.

$\endgroup$
1
  • $\begingroup$ This helped me as well but that is not my question. I didn't know this even. Got to learn this so thanks. $\endgroup$ Commented Dec 9, 2015 at 21:17

You must log in to answer this question.

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