Let be the set of integers (from 2 through 150) that are
divisible
by i for i=2,3,5,7,11. The number of remaining prime numbers are 149 (since
there are 149 integers from 2 through 150) minus the size of the union of
the
. We can calculate the size of this union using
inclusion-exclusion.
The number of integers not exceeding 150 (and greater than 1) that are
divisible by all the primes in a subsets of 2, 3, 5, 7, 11 is
, where N is the product of the
primes in this subset. This follows, since any two of the these primes
have no common factor. Consequently, the number of primes is
= 5 + 149 -75-50-30-21-13 +25+15+10+6+10+7+4+4+2+1 -5-3-2-2-1-0-1-0-0-0 + 0+0+0+0+0-0 = 35 Hence, there are 35 primes between 1 and 150.
Hence, the required generating function for making k dollars is
let y=3x , we have
This is the required generating function.
This is a typical partition problem and there are
ways
to do this partitioning.
is the coefficient of
.
and since we have
, hence
is the coefficient of
which is
.
is the coefficient of
. Hence,
.