Total combinations from number of unique combination

combinationspermutations

How can you find count of the total combinations possible if you have the count of unique combinations?

Suppose I need to form a sum of $3$ using $\{1,2\}$
Unique combn. $(1+1+1)$,
$(1+2)$
hence '$2$' unique
but total is '$3$' i.e,
$(1+1+1)$,
$(1+2)$,
$(2+1)$

I know the elements used to make the combination

Note: Number of unique combinations (ie. 2 here) is known.

How can I find the total number of combination given the unique combinations?

Best Answer

To find the number of restricted compositions (use the correct terminology) with a desired sum $n$ and available numbers $\{1,2\}$, what I will label $f(n)$, recognize the following:

$f(1)=1$ (as the only possibility is the sum with only one term: $(1)$)

$f(2)=2$ (as there are two possibilities: $(1+1)$ and $(2)$)

alternatively, and preferably, recognize that $f(0)=1$ as there is in fact a sum whose sum is zero using terms $1$ and $2$... the "empty sum"... $(~)$. This is somewhat abstract, but I strongly encourage coming to grips with this as using counts related to objects of size zero can greatly simplify arithmetic in many instances

Next, recognize that for each $n\geq 3$ you have $f(n) = f(n-1)+f(n-2)$ which is seen by noting that every such restricted composition either begins with a "$1+\dots$" with a sum of $n-1$ following which can be arranged in $f(n-1)$ ways, or it will begin with $2+\dots$ with a sum of $n-2$ following which can be arranged in $f(n-2)$ ways.

Now... you should recognize this... $f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2)$... this is precisely the fibonacci sequence. So... here we found that $f(n)$ is precisely equal to $F_n$.

No knowledge of the related problem counting restricted partitions rather than restricted compositions was needed.

The technique can obviously be adapted... the number of restricted compositions with sum $n$ using terms $\{1,2,3\}$ for instance would be the tribonacci numbers satisfying the recurrence $t(1)=1, t(2)=2, t(3)=4, t(n)=t(n-1)+t(n-2)+t(n-3)$ or the number of restricted compositions with sum $n$ using terms $\{2,5\}$ for instance would be $a(1)=a(3)=0, a(2)=a(4)=a(5)=1$ and $a(n)=a(n-2)+a(n-5)$ for each $n\geq 6$ and so on...

Coming to terms with the zero object can simplify a lot of the above for finding initial conditions. We could instead have had $a(n)=0$ for all $n<0$ and $a(0)=1$, reducing the need to actually manually find initial conditions

Coming up with a closed form for these types of linear recurrences is already covered in great detail in related chapters in books, and otherwise for now the current presentation of the answer in terms of a recurrence relation is generally considered sufficient.

Related Question