3
$\begingroup$

I am still in the early phase of getting comfortable with solving recursive problems. I was given
int p(int n) // number of permutations of n objects
int c(int n, int k) // number of unique combinations of k elements out of n elemnts

For instance, {"abc"} as the given string, permutation will be {"abc"}, {"acb"}, {"bac"}, {"bca"}, {"cab"}, {"cba"}. However, combination (order does not matter) will be just simply {"abc"}.

A detail representation of Combination by using Pascal's Triangle from Eric Roberts' book.

enter image description here
enter image description here

I am having a hard time seeing how this pascal's triangle representation relate to the idea of combination.

My initial thought process was based on each of their formulae and using factorial to solve the problem. Clearly, that's not what I was asked to do. I was supposed to define them recursively and implement the recursive definitions for both counting techniques. So, basically, I am unable to solve the two functions without getting the help of factorial.

$\endgroup$
4
  • 3
    $\begingroup$ what is athe difference between p and c? They have the same parameters. $\endgroup$
    – fade2black
    Aug 8 '17 at 5:51
  • 1
    $\begingroup$ I don't understand n, number of elements, k, k selections for permutation $\endgroup$
    – miracle173
    Aug 8 '17 at 6:10
  • $\begingroup$ Please explain what the functions p and c are supposed to do, if possible with examples. $\endgroup$ Aug 8 '17 at 6:50
  • $\begingroup$ Sorry for the late addition of examples, I added examples in the edited question. $\endgroup$
    – Nate Lee
    Aug 8 '17 at 19:04
1
$\begingroup$

The number of permutations of $n$ distinct objects is $n!$. The number of $k$ selections out of $n$ distinct objects is $\binom{n}{k}$ known also as a binomial coefficient. Recursive definition of these numbers are trivial: $$n! = n(n-1)!$$ $$\text{so if } f(n) = n! \text{ then } f(n) = n\times f(n-1), f(0) = 1$$ For binomial coefficients $${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$ or $$ b(n,k) = b(n-1, k-1)+b(n-1, k)$$ where $$b(n,n)=1 = b(n,0)=1 \text{ and } b(n,k)=0 \text{ for } n < k$$

If you want approximate value without too much computation then you may check the Stirling's approximation.


Proof of $${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$ You can prove it using a combinatorial argument or algebraic. The algebraic one is tedious (you need to manipulate factorials). So let's consider a combinatorial proof.

Assume we have $n$ people, numbered from $1$ to $n$, and want to create a team consisting of $k$ people. There are exactly ${\binom {n}{k}}$ ways to create a team, i.e, $k$ people out of total $n$. Consider the first member, number $1$. There are two possibilities: either include her or leave her out.

  • If we choose that member then we need to choose additional $k-1$ people out of remaining $n-1$ people which is equal to $\binom{n-1}{k-1}$.
  • If we leave that member out then we have to select $k$ out of $n-1$ people which equal to $\binom{n-1}{k}$.

Since these both options result in different teams the total number of teams is $$\binom{n-1}{k-1} + \binom{n-1}{k} $$

$\endgroup$
3
  • $\begingroup$ will you use the same deduction approach for combination. I am using an algorithm book by Robert Eric, he presented Pascal's Triangle (a geometric form to represent combination) to showcase combination. I am not sure how to deduce a recursive definition based on the Pascal's Triangle. $\endgroup$
    – Nate Lee
    Aug 8 '17 at 19:11
  • 1
    $\begingroup$ Is the reason of adding (n - 1, k-1) to (n - 1, k) because of the two options (choosing the first member or leaving) are independent of one another? So by adding the two options will give us the total outcomes or combinations, right? $\endgroup$
    – Nate Lee
    Aug 8 '17 at 21:15
  • $\begingroup$ Yes, you are right. These two options complement each other. That's why we add them. $\endgroup$
    – fade2black
    Aug 8 '17 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.