Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    9
    ReputationRep:
    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 {b+r-1\choose b}.

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

    \displaystyle \sum_{r=1}^{a+1} {b+r-1\choose b}

    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?
    Offline

    3
    ReputationRep:
    Can't you have zero coefficients?
    • Thread Starter
    Offline

    9
    ReputationRep:
    (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.
    Offline

    3
    ReputationRep:
    Isn't the answer to both 'how many mappings are there from a points into b points?'
    • Thread Starter
    Offline

    9
    ReputationRep:
    (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?
    Offline

    3
    ReputationRep:
    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?
    Offline

    3
    ReputationRep:
    I'm trying to avoid counting the ways, just showing that each way in one corresponds to an equivalent way in the other.
    • Thread Starter
    Offline

    9
    ReputationRep:
    (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
    • Study Helper
    Offline

    13
    Study Helper
    (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.
    • Thread Starter
    Offline

    9
    ReputationRep:
    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
    • Thread Starter
    Offline

    9
    ReputationRep:
    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.
    • Study Helper
    Offline

    13
    Study Helper
    (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.

    Now add.

    Edit: Yes, or course you count degree 0!

    PS: In case you haven't already realised it, the sum will siimplify.
    • Thread Starter
    Offline

    9
    ReputationRep:
    (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.

    Now add.

    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

    \displaystyle \sum_{r=0}^{c-1} {c-1\choose r} = 2^{c-1}
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by 0-))
    So the sum is

    \displaystyle \sum_{r=0}^{c-1} {c-1\choose r} = 2^{c-1}
    Looks good to me.
 
 
 
Poll
Do you agree with the PM's proposal to cut tuition fees for some courses?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.