How many ways to pay The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How many different ways to combine $2?Ordinary Generating functions for $b_n$What happens to the exponential generating function if the sequence is “stretched”?Generating function - the number of ways to distribute 100 dollars to n people.How to find an exponential generating function if we know a usual generating function?Find generating function of a sequence if A(x) is generating function of sequence $a_n$.How To Find the Generating Function of the Following Problemmoney changing problemNumber of ways to pay (generating functions)Finding the generating function of a sequence for $n$ pennies

How to determine omitted units in a publication

Is an up-to-date browser secure on an out-of-date OS?

How did the audience guess the pentatonic scale in Bobby McFerrin's presentation?

Why can't wing-mounted spoilers be used to steepen approaches?

Sub-subscripts in strings cause different spacings than subscripts

Would an alien lifeform be able to achieve space travel if lacking in vision?

ELI5: Why do they say that Israel would have been the fourth country to land a spacecraft on the Moon and why do they call it low cost?

Can the DM override racial traits?

Example of compact Riemannian manifold with only one geodesic.

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

How to support a colleague who finds meetings extremely tiring?

What can I do if neighbor is blocking my solar panels intentionally?

How do you keep chess fun when your opponent constantly beats you?

Do warforged have souls?

Are spiders unable to hurt humans, especially very small spiders?

should truth entail possible truth

Mortgage adviser recommends a longer term than necessary combined with overpayments

Make it rain characters

For what reasons would an animal species NOT cross a *horizontal* land bridge?

How do spell lists change if the party levels up without taking a long rest?

Python - Fishing Simulator

60's-70's movie: home appliances revolting against the owners

Do ℕ, mathbbN, BbbN, symbbN effectively differ, and is there a "canonical" specification of the naturals?

Windows 10: How to Lock (not sleep) laptop on lid close?



How many ways to pay



The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How many different ways to combine $2?Ordinary Generating functions for $b_n$What happens to the exponential generating function if the sequence is “stretched”?Generating function - the number of ways to distribute 100 dollars to n people.How to find an exponential generating function if we know a usual generating function?Find generating function of a sequence if A(x) is generating function of sequence $a_n$.How To Find the Generating Function of the Following Problemmoney changing problemNumber of ways to pay (generating functions)Finding the generating function of a sequence for $n$ pennies










0












$begingroup$



Let $a_n$ be the number of ways in which you can pay $n$ amount with coins valued at 1, 2, 5, 10, 20, 50. Find the generating function for $(a_0,a_1,a_2,…)$. And find the value of $a_23$.
Find the generating function where you can use at most 10 coins valued at 1, 7 coins valued at 2 and 6 coins valued at 5.




What I have so far is $f(x) = frac11-xfrac11-x^2frac11-x^5frac11-x^10frac11-x^20frac11-x^50$



How would I proceed with finding the answer for $a_23$?










share|cite|improve this question











$endgroup$







  • 1




    $begingroup$
    are you allowed to use a computer program that implements a recursive function perhaps?
    $endgroup$
    – Confused Soul
    Mar 24 at 17:54










  • $begingroup$
    You don't need the $50$ --- one can't pay $23$ if you use one or more $50$'s [then already over $23$] Doesn't decrease calculation much though. Of course $50$ still needed for generating function in general.
    $endgroup$
    – coffeemath
    Mar 24 at 18:50











  • $begingroup$
    @ConfusedSoul It's an exercise so it's not really specified
    $endgroup$
    – J. Lastin
    Mar 24 at 20:43










  • $begingroup$
    This is from Miklas Bona's Combinatorics book is it not?
    $endgroup$
    – Matthew Graham
    Mar 24 at 21:51















0












$begingroup$



Let $a_n$ be the number of ways in which you can pay $n$ amount with coins valued at 1, 2, 5, 10, 20, 50. Find the generating function for $(a_0,a_1,a_2,…)$. And find the value of $a_23$.
Find the generating function where you can use at most 10 coins valued at 1, 7 coins valued at 2 and 6 coins valued at 5.




What I have so far is $f(x) = frac11-xfrac11-x^2frac11-x^5frac11-x^10frac11-x^20frac11-x^50$



How would I proceed with finding the answer for $a_23$?










share|cite|improve this question











$endgroup$







  • 1




    $begingroup$
    are you allowed to use a computer program that implements a recursive function perhaps?
    $endgroup$
    – Confused Soul
    Mar 24 at 17:54










  • $begingroup$
    You don't need the $50$ --- one can't pay $23$ if you use one or more $50$'s [then already over $23$] Doesn't decrease calculation much though. Of course $50$ still needed for generating function in general.
    $endgroup$
    – coffeemath
    Mar 24 at 18:50











  • $begingroup$
    @ConfusedSoul It's an exercise so it's not really specified
    $endgroup$
    – J. Lastin
    Mar 24 at 20:43










  • $begingroup$
    This is from Miklas Bona's Combinatorics book is it not?
    $endgroup$
    – Matthew Graham
    Mar 24 at 21:51













0












0








0


1



$begingroup$



Let $a_n$ be the number of ways in which you can pay $n$ amount with coins valued at 1, 2, 5, 10, 20, 50. Find the generating function for $(a_0,a_1,a_2,…)$. And find the value of $a_23$.
Find the generating function where you can use at most 10 coins valued at 1, 7 coins valued at 2 and 6 coins valued at 5.




What I have so far is $f(x) = frac11-xfrac11-x^2frac11-x^5frac11-x^10frac11-x^20frac11-x^50$



How would I proceed with finding the answer for $a_23$?










share|cite|improve this question











$endgroup$





Let $a_n$ be the number of ways in which you can pay $n$ amount with coins valued at 1, 2, 5, 10, 20, 50. Find the generating function for $(a_0,a_1,a_2,…)$. And find the value of $a_23$.
Find the generating function where you can use at most 10 coins valued at 1, 7 coins valued at 2 and 6 coins valued at 5.




What I have so far is $f(x) = frac11-xfrac11-x^2frac11-x^5frac11-x^10frac11-x^20frac11-x^50$



How would I proceed with finding the answer for $a_23$?







combinatorics generating-functions






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Mar 24 at 17:42







J. Lastin

















asked Mar 24 at 17:38









J. LastinJ. Lastin

12212




12212







  • 1




    $begingroup$
    are you allowed to use a computer program that implements a recursive function perhaps?
    $endgroup$
    – Confused Soul
    Mar 24 at 17:54










  • $begingroup$
    You don't need the $50$ --- one can't pay $23$ if you use one or more $50$'s [then already over $23$] Doesn't decrease calculation much though. Of course $50$ still needed for generating function in general.
    $endgroup$
    – coffeemath
    Mar 24 at 18:50











  • $begingroup$
    @ConfusedSoul It's an exercise so it's not really specified
    $endgroup$
    – J. Lastin
    Mar 24 at 20:43










  • $begingroup$
    This is from Miklas Bona's Combinatorics book is it not?
    $endgroup$
    – Matthew Graham
    Mar 24 at 21:51












  • 1




    $begingroup$
    are you allowed to use a computer program that implements a recursive function perhaps?
    $endgroup$
    – Confused Soul
    Mar 24 at 17:54










  • $begingroup$
    You don't need the $50$ --- one can't pay $23$ if you use one or more $50$'s [then already over $23$] Doesn't decrease calculation much though. Of course $50$ still needed for generating function in general.
    $endgroup$
    – coffeemath
    Mar 24 at 18:50











  • $begingroup$
    @ConfusedSoul It's an exercise so it's not really specified
    $endgroup$
    – J. Lastin
    Mar 24 at 20:43










  • $begingroup$
    This is from Miklas Bona's Combinatorics book is it not?
    $endgroup$
    – Matthew Graham
    Mar 24 at 21:51







1




1




$begingroup$
are you allowed to use a computer program that implements a recursive function perhaps?
$endgroup$
– Confused Soul
Mar 24 at 17:54




$begingroup$
are you allowed to use a computer program that implements a recursive function perhaps?
$endgroup$
– Confused Soul
Mar 24 at 17:54












$begingroup$
You don't need the $50$ --- one can't pay $23$ if you use one or more $50$'s [then already over $23$] Doesn't decrease calculation much though. Of course $50$ still needed for generating function in general.
$endgroup$
– coffeemath
Mar 24 at 18:50





$begingroup$
You don't need the $50$ --- one can't pay $23$ if you use one or more $50$'s [then already over $23$] Doesn't decrease calculation much though. Of course $50$ still needed for generating function in general.
$endgroup$
– coffeemath
Mar 24 at 18:50













$begingroup$
@ConfusedSoul It's an exercise so it's not really specified
$endgroup$
– J. Lastin
Mar 24 at 20:43




$begingroup$
@ConfusedSoul It's an exercise so it's not really specified
$endgroup$
– J. Lastin
Mar 24 at 20:43












$begingroup$
This is from Miklas Bona's Combinatorics book is it not?
$endgroup$
– Matthew Graham
Mar 24 at 21:51




$begingroup$
This is from Miklas Bona's Combinatorics book is it not?
$endgroup$
– Matthew Graham
Mar 24 at 21:51










2 Answers
2






active

oldest

votes


















1












$begingroup$

You have found the generating function. Cool. The reason we use generating functions is because they're shorthand for certain series, and the way multiplication of those series work closely mimics the way the combinatorics of your coin problem works.



So, in order to use the generating functions to actually find an answer, the most straight-forward way is to go back to those series, and find the coefficient of the $x^23$ term:
$$
f(x) = (1+x+x^2 + cdots)cdot (1 + x^2 + x^4 + cdots)cdot(1 + x^5 + x^10 + cdots)\
cdot(1 + x^10 + x^20 + cdots)cdot(1 + x^20 + x^40 + cdots)cdot(1 + x^50 + x^100 + cdots)
$$

We see immedaitely that any term of higher degree than $23$ may be safely discarded without changing our result:
$$
f(x)approx(1 + x + x^2 + cdots + x^23)cdot(1 + x^2 + x^4 + cdots + x^22)\
cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)
$$

And then we get to multiplying (still discarding any terms higher than $x^23$ as we go):
$$
approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)\
approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + 2x^20)\
approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
cdot(1 + x^5 + 2x^10 + 2x^15 + 4x^20)
$$

And now that we only have two brackets we can forget everything else, and look directly at the terms whose degrees add up to $23$. We get:
$$
12x^23cdot 1 + 10x^18cdot x^5 + 7x^13cdot 2x^10 + 5x^8cdot 2x^15 + 2x^3cdot 4x^20\
= 54x^23
$$

So there are 54 ways to make $23$ with the given coins.



With the given limitation, instead of the infinite series we get finite series (polynomials) for the limited coins. So instead of $(1 + x + x^2 + cdots)$, we use $(1 + x + x^2 + cdots + x^10)$, or its more succinct representative $frac1-x^111-x$. Similarily, the two-coin terms changes to $frac1 - x^161-x^2$ and the five-coin term to $frac1-x^351-x^5$. So we get the generating function
$$
g(x) = frac1-x^111-xcdotfrac1 - x^161-x^2cdotfrac1-x^351-x^5cdotfrac11-x^10cdotfrac11-x^20cdotfrac11-x^50
$$






share|cite|improve this answer









$endgroup$




















    1












    $begingroup$

    Let $b_n$ be the number of ways to make change from $[1,2]$. Fill out the table $b_1,b_2,dots,b_23$ by brute force.



    Let $c_n$ be the number of ways to make change from $[1,2,5]$. Note that
    $$
    c_n=c_n-5+b_n,
    $$

    so use that recursion, plus the filled out $b$ table, to fill out $c_1,c_2,dots,c_23$.



    Then, let $d_n$ be the number of ways to make change from $[1,2,5,10]$, and use the $c$ table and a similar recursion to fill out the $d$ table, then let $e_n$ the number of ways to make change from $[1,2,5,10,20]$ and do the same. You want $e_23$.






    share|cite|improve this answer









    $endgroup$













      Your Answer








      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "69"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader:
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      ,
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













      draft saved

      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3160816%2fhow-many-ways-to-pay%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      1












      $begingroup$

      You have found the generating function. Cool. The reason we use generating functions is because they're shorthand for certain series, and the way multiplication of those series work closely mimics the way the combinatorics of your coin problem works.



      So, in order to use the generating functions to actually find an answer, the most straight-forward way is to go back to those series, and find the coefficient of the $x^23$ term:
      $$
      f(x) = (1+x+x^2 + cdots)cdot (1 + x^2 + x^4 + cdots)cdot(1 + x^5 + x^10 + cdots)\
      cdot(1 + x^10 + x^20 + cdots)cdot(1 + x^20 + x^40 + cdots)cdot(1 + x^50 + x^100 + cdots)
      $$

      We see immedaitely that any term of higher degree than $23$ may be safely discarded without changing our result:
      $$
      f(x)approx(1 + x + x^2 + cdots + x^23)cdot(1 + x^2 + x^4 + cdots + x^22)\
      cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)
      $$

      And then we get to multiplying (still discarding any terms higher than $x^23$ as we go):
      $$
      approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
      cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)\
      approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
      cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + 2x^20)\
      approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
      cdot(1 + x^5 + 2x^10 + 2x^15 + 4x^20)
      $$

      And now that we only have two brackets we can forget everything else, and look directly at the terms whose degrees add up to $23$. We get:
      $$
      12x^23cdot 1 + 10x^18cdot x^5 + 7x^13cdot 2x^10 + 5x^8cdot 2x^15 + 2x^3cdot 4x^20\
      = 54x^23
      $$

      So there are 54 ways to make $23$ with the given coins.



      With the given limitation, instead of the infinite series we get finite series (polynomials) for the limited coins. So instead of $(1 + x + x^2 + cdots)$, we use $(1 + x + x^2 + cdots + x^10)$, or its more succinct representative $frac1-x^111-x$. Similarily, the two-coin terms changes to $frac1 - x^161-x^2$ and the five-coin term to $frac1-x^351-x^5$. So we get the generating function
      $$
      g(x) = frac1-x^111-xcdotfrac1 - x^161-x^2cdotfrac1-x^351-x^5cdotfrac11-x^10cdotfrac11-x^20cdotfrac11-x^50
      $$






      share|cite|improve this answer









      $endgroup$

















        1












        $begingroup$

        You have found the generating function. Cool. The reason we use generating functions is because they're shorthand for certain series, and the way multiplication of those series work closely mimics the way the combinatorics of your coin problem works.



        So, in order to use the generating functions to actually find an answer, the most straight-forward way is to go back to those series, and find the coefficient of the $x^23$ term:
        $$
        f(x) = (1+x+x^2 + cdots)cdot (1 + x^2 + x^4 + cdots)cdot(1 + x^5 + x^10 + cdots)\
        cdot(1 + x^10 + x^20 + cdots)cdot(1 + x^20 + x^40 + cdots)cdot(1 + x^50 + x^100 + cdots)
        $$

        We see immedaitely that any term of higher degree than $23$ may be safely discarded without changing our result:
        $$
        f(x)approx(1 + x + x^2 + cdots + x^23)cdot(1 + x^2 + x^4 + cdots + x^22)\
        cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)
        $$

        And then we get to multiplying (still discarding any terms higher than $x^23$ as we go):
        $$
        approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
        cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)\
        approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
        cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + 2x^20)\
        approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
        cdot(1 + x^5 + 2x^10 + 2x^15 + 4x^20)
        $$

        And now that we only have two brackets we can forget everything else, and look directly at the terms whose degrees add up to $23$. We get:
        $$
        12x^23cdot 1 + 10x^18cdot x^5 + 7x^13cdot 2x^10 + 5x^8cdot 2x^15 + 2x^3cdot 4x^20\
        = 54x^23
        $$

        So there are 54 ways to make $23$ with the given coins.



        With the given limitation, instead of the infinite series we get finite series (polynomials) for the limited coins. So instead of $(1 + x + x^2 + cdots)$, we use $(1 + x + x^2 + cdots + x^10)$, or its more succinct representative $frac1-x^111-x$. Similarily, the two-coin terms changes to $frac1 - x^161-x^2$ and the five-coin term to $frac1-x^351-x^5$. So we get the generating function
        $$
        g(x) = frac1-x^111-xcdotfrac1 - x^161-x^2cdotfrac1-x^351-x^5cdotfrac11-x^10cdotfrac11-x^20cdotfrac11-x^50
        $$






        share|cite|improve this answer









        $endgroup$















          1












          1








          1





          $begingroup$

          You have found the generating function. Cool. The reason we use generating functions is because they're shorthand for certain series, and the way multiplication of those series work closely mimics the way the combinatorics of your coin problem works.



          So, in order to use the generating functions to actually find an answer, the most straight-forward way is to go back to those series, and find the coefficient of the $x^23$ term:
          $$
          f(x) = (1+x+x^2 + cdots)cdot (1 + x^2 + x^4 + cdots)cdot(1 + x^5 + x^10 + cdots)\
          cdot(1 + x^10 + x^20 + cdots)cdot(1 + x^20 + x^40 + cdots)cdot(1 + x^50 + x^100 + cdots)
          $$

          We see immedaitely that any term of higher degree than $23$ may be safely discarded without changing our result:
          $$
          f(x)approx(1 + x + x^2 + cdots + x^23)cdot(1 + x^2 + x^4 + cdots + x^22)\
          cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)
          $$

          And then we get to multiplying (still discarding any terms higher than $x^23$ as we go):
          $$
          approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
          cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)\
          approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
          cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + 2x^20)\
          approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
          cdot(1 + x^5 + 2x^10 + 2x^15 + 4x^20)
          $$

          And now that we only have two brackets we can forget everything else, and look directly at the terms whose degrees add up to $23$. We get:
          $$
          12x^23cdot 1 + 10x^18cdot x^5 + 7x^13cdot 2x^10 + 5x^8cdot 2x^15 + 2x^3cdot 4x^20\
          = 54x^23
          $$

          So there are 54 ways to make $23$ with the given coins.



          With the given limitation, instead of the infinite series we get finite series (polynomials) for the limited coins. So instead of $(1 + x + x^2 + cdots)$, we use $(1 + x + x^2 + cdots + x^10)$, or its more succinct representative $frac1-x^111-x$. Similarily, the two-coin terms changes to $frac1 - x^161-x^2$ and the five-coin term to $frac1-x^351-x^5$. So we get the generating function
          $$
          g(x) = frac1-x^111-xcdotfrac1 - x^161-x^2cdotfrac1-x^351-x^5cdotfrac11-x^10cdotfrac11-x^20cdotfrac11-x^50
          $$






          share|cite|improve this answer









          $endgroup$



          You have found the generating function. Cool. The reason we use generating functions is because they're shorthand for certain series, and the way multiplication of those series work closely mimics the way the combinatorics of your coin problem works.



          So, in order to use the generating functions to actually find an answer, the most straight-forward way is to go back to those series, and find the coefficient of the $x^23$ term:
          $$
          f(x) = (1+x+x^2 + cdots)cdot (1 + x^2 + x^4 + cdots)cdot(1 + x^5 + x^10 + cdots)\
          cdot(1 + x^10 + x^20 + cdots)cdot(1 + x^20 + x^40 + cdots)cdot(1 + x^50 + x^100 + cdots)
          $$

          We see immedaitely that any term of higher degree than $23$ may be safely discarded without changing our result:
          $$
          f(x)approx(1 + x + x^2 + cdots + x^23)cdot(1 + x^2 + x^4 + cdots + x^22)\
          cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)
          $$

          And then we get to multiplying (still discarding any terms higher than $x^23$ as we go):
          $$
          approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
          cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + x^20)cdot(1 + x^20)\
          approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
          cdot(1 + x^5 + x^10 + x^15 + x^20)cdot(1 + x^10 + 2x^20)\
          approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + cdots + 12x^22 + 12x^23)\
          cdot(1 + x^5 + 2x^10 + 2x^15 + 4x^20)
          $$

          And now that we only have two brackets we can forget everything else, and look directly at the terms whose degrees add up to $23$. We get:
          $$
          12x^23cdot 1 + 10x^18cdot x^5 + 7x^13cdot 2x^10 + 5x^8cdot 2x^15 + 2x^3cdot 4x^20\
          = 54x^23
          $$

          So there are 54 ways to make $23$ with the given coins.



          With the given limitation, instead of the infinite series we get finite series (polynomials) for the limited coins. So instead of $(1 + x + x^2 + cdots)$, we use $(1 + x + x^2 + cdots + x^10)$, or its more succinct representative $frac1-x^111-x$. Similarily, the two-coin terms changes to $frac1 - x^161-x^2$ and the five-coin term to $frac1-x^351-x^5$. So we get the generating function
          $$
          g(x) = frac1-x^111-xcdotfrac1 - x^161-x^2cdotfrac1-x^351-x^5cdotfrac11-x^10cdotfrac11-x^20cdotfrac11-x^50
          $$







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Mar 25 at 9:42









          ArthurArthur

          123k7122211




          123k7122211





















              1












              $begingroup$

              Let $b_n$ be the number of ways to make change from $[1,2]$. Fill out the table $b_1,b_2,dots,b_23$ by brute force.



              Let $c_n$ be the number of ways to make change from $[1,2,5]$. Note that
              $$
              c_n=c_n-5+b_n,
              $$

              so use that recursion, plus the filled out $b$ table, to fill out $c_1,c_2,dots,c_23$.



              Then, let $d_n$ be the number of ways to make change from $[1,2,5,10]$, and use the $c$ table and a similar recursion to fill out the $d$ table, then let $e_n$ the number of ways to make change from $[1,2,5,10,20]$ and do the same. You want $e_23$.






              share|cite|improve this answer









              $endgroup$

















                1












                $begingroup$

                Let $b_n$ be the number of ways to make change from $[1,2]$. Fill out the table $b_1,b_2,dots,b_23$ by brute force.



                Let $c_n$ be the number of ways to make change from $[1,2,5]$. Note that
                $$
                c_n=c_n-5+b_n,
                $$

                so use that recursion, plus the filled out $b$ table, to fill out $c_1,c_2,dots,c_23$.



                Then, let $d_n$ be the number of ways to make change from $[1,2,5,10]$, and use the $c$ table and a similar recursion to fill out the $d$ table, then let $e_n$ the number of ways to make change from $[1,2,5,10,20]$ and do the same. You want $e_23$.






                share|cite|improve this answer









                $endgroup$















                  1












                  1








                  1





                  $begingroup$

                  Let $b_n$ be the number of ways to make change from $[1,2]$. Fill out the table $b_1,b_2,dots,b_23$ by brute force.



                  Let $c_n$ be the number of ways to make change from $[1,2,5]$. Note that
                  $$
                  c_n=c_n-5+b_n,
                  $$

                  so use that recursion, plus the filled out $b$ table, to fill out $c_1,c_2,dots,c_23$.



                  Then, let $d_n$ be the number of ways to make change from $[1,2,5,10]$, and use the $c$ table and a similar recursion to fill out the $d$ table, then let $e_n$ the number of ways to make change from $[1,2,5,10,20]$ and do the same. You want $e_23$.






                  share|cite|improve this answer









                  $endgroup$



                  Let $b_n$ be the number of ways to make change from $[1,2]$. Fill out the table $b_1,b_2,dots,b_23$ by brute force.



                  Let $c_n$ be the number of ways to make change from $[1,2,5]$. Note that
                  $$
                  c_n=c_n-5+b_n,
                  $$

                  so use that recursion, plus the filled out $b$ table, to fill out $c_1,c_2,dots,c_23$.



                  Then, let $d_n$ be the number of ways to make change from $[1,2,5,10]$, and use the $c$ table and a similar recursion to fill out the $d$ table, then let $e_n$ the number of ways to make change from $[1,2,5,10,20]$ and do the same. You want $e_23$.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Mar 24 at 20:40









                  Mike EarnestMike Earnest

                  27.8k22152




                  27.8k22152



























                      draft saved

                      draft discarded
















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid


                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.

                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3160816%2fhow-many-ways-to-pay%23new-answer', 'question_page');

                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      How should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer

                      random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

                      Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye