You are Here: Home >< Maths

# Polynomials/counting problem watch

1. Prove that the number of polynomials with nonnegative integer coefficents, whose degree is at most a and the sum of whose coefficients is b, is equal to the number of polynomials whose degree is at most b and the sum of whose coefficients is a.

Working: For a poly of degree r-1 (r-1<=a), the number of different polys with sum of coefficients b will be equal to the number of ways of distributing b elements amongst r subsets. This is equal to .

So the total number of polys of degree <= a will be

To prove the statement I would need to show that the above sum is the same if the a's become b's and vice-versa. But I can show by counterexample that this is not true.

Where is the mistake in my working?
2. Can't you have zero coefficients?
3. (Original post by ian.slater)
Can't you have zero coefficients?
I made a mistake when i wrote 'non-empty'. I still can't see any other mistakes though.
4. Isn't the answer to both 'how many mappings are there from a points into b points?'
5. (Original post by ian.slater)
Isn't the answer to both 'how many mappings are there from a points into b points?'
Could you explain?
6. Your idea is to consider putting b items into a bins, and count the number of ways. b is the coefficient bit and a is the (maximum) degree of polynomial.

Isn't that equivalent to mapping the other way?
7. I'm trying to avoid counting the ways, just showing that each way in one corresponds to an equivalent way in the other.
8. (Original post by ian.slater)
Your idea is to consider putting b items into a bins, and count the number of ways. b is the coefficient bit and a is the (maximum) degree of polynomial.

Isn't that equivalent to mapping the other way?
Counterexample a=3 b=2

3 items into 2 bins: 4
2 items into 3 bins: 6
9. (Original post by 0-))
...
The number of different polys of degree <=a with sum of coefficients b will be equal to the number of ways of distributing b elements amongst a+1 subsets.

Work from there.
10. I just realised how stupid I'm being. I've been making the problem harder than it is.

Thank you to everyone for the help
11. I have a simlilar question which I think is a bit harder.

Find the number of polynomials with nonnegative integer coefficients whose degree plus the sum of the coefficients is equal to c.

I've looked at a few examples but I haven't been able to formulate a method.
12. (Original post by 0-))
I have a simlilar question which I think is a bit harder.

Find the number of polynomials with nonnegative integer coefficients whose degree plus the sum of the coefficients is equal to c.

I've looked at a few examples but I haven't been able to formulate a method.
It really does follow on quite naturally from the last result.

Don't know if you count degree 0, so....
How many of degree 1 and sum c-1 - leave it in nCr format.
How many of degree 2 and sum c-2 ....
Etc.

Edit: Yes, or course you count degree 0!

PS: In case you haven't already realised it, the sum will siimplify.
13. (Original post by ghostwalker)
It really does follow on quite naturally from the last result.

Don't know if you count degree 0, so....
How many of degree 1 and sum c-1 - leave it in nCr format.
How many of degree 2 and sum c-2 ....
Etc.

Edit: Yes, or course you count degree 0!

PS: In case you haven't already realised it, the sum will siimplify.
So the sum is

14. (Original post by 0-))
So the sum is

Looks good to me.

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 11, 2010
The home of Results and Clearing

### 1,505

people online now

### 1,567,000

students helped last year
Today on TSR

### University open days

1. Bournemouth University
Wed, 22 Aug '18
2. University of Buckingham
Thu, 23 Aug '18
3. University of Glasgow
Tue, 28 Aug '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams