1
$\begingroup$

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?

  • 2
    Also Diophantine equations. This is related to the Frobenius coin problem.2011-11-22

1 Answers 1

4

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)$