4
$\begingroup$

The postal stamps of three different valuations viz $2$ cents, $3$ cents and $4$ cents are available. If the number of ways in which these stamps can be posted on envelope one after the other so that the total valuation of stamps on the envelope is $10$ cents is $N$. Find $N$.

I have actually solved the problem using the method given below. Consider the function $$f(n)=f(n-2)+f(n-3)+f(n-4)$$ where $f(n)$ represents the ways in which stamps so arranged give the sum as $n$ on the envelope. Hence we need to find $f(10)$. Now on quick brute force we get $f(2)=1, f(3)=1, f(4)=2$ and $f(5)=2$. Using these I got $f(10)$ as $17$ which is the correct answer.

But I want to solve this problem using the binomial coefficient method. For example the answer to this question must be equal to the coefficient of $x^{10}$ in the expansion of $$(x^0+x^2+x^4+x^6+x^8+x^{10})(x^0+x^3+x^6+x^9)(x^0+x^4+x^8)$$

But using this I get the coefficient of $x^{10}$ as $5$ which isn't the correct answer. Can someone please check my method and place your suggestions over how should I continue in this method.

Note : I think that many similar questions might have been asked on MSE but I am focusing on just one particular method to solve such problem. So please don't mark it as duplicate.

$\endgroup$
  • 1
    $\begingroup$ Why is $f(5) = 2$? Does order matter? $\endgroup$ – feynhat Jan 10 '18 at 17:01
  • $\begingroup$ @feynhat $(3, 2)\ (2,3)$ $\endgroup$ – John Lou Jan 10 '18 at 17:02
  • $\begingroup$ @JohnLou Oh right. OP didn't mention that order mattered. $\endgroup$ – feynhat Jan 10 '18 at 17:05
  • $\begingroup$ Well I did- " If the number of ways in which these stamps can be posted on envelope ""one after the other """ $\endgroup$ – Rohan Shinde Jan 10 '18 at 17:16
5
$\begingroup$

Five two-cents; one four-cent and three two-cents; two four-cents and one two-cent; two three-cents and two two-cents; two three-cents and one four-cent.

Those are the five combinations of denominations, which you got from the $x^{10}$ coefficient.

As for arranging the stamps, that's a different problem entirely. The number of arrangements for each case above are $1,4,3,6,3$, respectively, which gives your $17$.

Looks like the two methods are meant for different problems.

$\endgroup$
  • $\begingroup$ So can one directly manipulate the arrangement of the stamps from the coefficients itself or by modifying the coefficients a bit. $\endgroup$ – Rohan Shinde Jan 10 '18 at 17:15
  • $\begingroup$ The short answer is no. $\endgroup$ – John Jan 10 '18 at 17:31

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.