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$
  • $\begingroup$ if repetition is allowed, then why aren't $PP,QQ,RR$ valid? $\endgroup$ – lulu Dec 9 '15 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 Dec 9 '15 at 21:11
  • $\begingroup$ I am really sorry. Posted the correct thing now. $\endgroup$ – Farhan Anam Dec 9 '15 at 21:14
  • $\begingroup$ @SubhadeepDey I have edited my question. Please read it once more. $\endgroup$ – Farhan Anam Dec 9 '15 at 21:23
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$
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$
  • $\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$ – Farhan Anam Dec 9 '15 at 21:17

Your Answer

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

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