Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm studying a simple counting problem like this:

Given a positive integer $w$ and a collection of positive integers $P = \{p_0 ... p_n\}$ count the number of solutions to $$(p_0 a) + (p_1 b) + \cdots + (p_n z) \leq w.$$

What general category of mathematics does this type of problem belong to?

Perhaps discrete math or combinatorics?

share|improve this question
2  
Also Diophantine equations. This is related to the Frobenius coin problem. –  J. M. Nov 22 '11 at 19:12
add comment

1 Answer

up vote 4 down vote accepted

You can solve this problem by using generating functions:

Let $f(m)$ be the number of partitions of $m$ involving the integers in $P=\{p_0,\dots,p_n\}$. This is the coefficient of $x^m$ in the series:

$$F = \prod\limits_{p_i \in P} \frac{1}{1-x^{p_i}} = (1+x^{p_0}+x^{2p_0}+\cdots)(1+x^{p_1}+x^{2p_1}+\cdots)\cdots(1+x^{p_n}+x^{2p_n}+\cdots)$$

Then your count is $C = \sum\limits_{m=0}^w f(m)$

Example: Let $P=\{1,3\}$. Then $F = (1+x+x^2+\cdots)(1+x^3+x^6+\cdots) = 1+x+x^2+2x^3+2x^4+2x^5+3x^6+\cdots$

So $f(0)=1$, $f(1)=1$, $f(2)=1$, $f(3)=2$, $f(4)=2$, $f(5)=2$, $f(6)=3$, etc.

Thus solving $a1+b3 \leq 6$ we have $C=1+1+1+2+2+2+3=12$ solutions.

[For the record, The solutions are: $a=0,\dots,6$ and $b=0$ or $a=0,\dots 3$ and $b=1$, or $a=0$ and $b=2$. So $7+4+1=12$ solutions.]

I'm sure there are other ways to tackle such a problem, but since you are counting solutions, this is definitely a problem of combinatorics.

Edit: By the way, if you don't want to allow 0's as part of your solutions (i.e. all $a,b,$ etc. are positive integers), then you can replace $F$ with...

$$F = \prod\limits_{p_i \in P} \frac{x^{p_i}}{1-x^{p_i}} = (x^{p_0}+x^{2p_0}+\cdots)(x^{p_1}+x^{2p_1}+\cdots)\cdots(x^{p_n}+x^{2p_n}+\cdots)$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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