Number of ways to pick balls from an urn if one type of ball runs out












0












$begingroup$


Assumed you have balls with three different colors in an urn. From each type of ball you have four pieces that are not distinguishable. How many ways are there to pick five balls out of the urn?



Or in general with balls in $k$ different colors and $m$ balls of each of the color how many ways are there to pick $n$ balls out of the urn?



The problem is easy if $n leq m$. Then it is just an unordered selection with repetition allowed. Therefore there are $binom{k+n-1}{n}$ ways to pick. But if $n > m$ repetition is not necessarily allowed and I cannot find a beautiful way to calculate the number of ways. For small examples I might be able to find the solution step by step but on a larger scale I need help.






combinatorics







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Well, I'd implement it recursively. If $F(k,m,n)$ is your answer then looking at the options for the $k^{th}$ color we see that $F(k,m,n)=sum_{i=0}^m F(k-1,m,n-i)$. I don't expect this to have a convenient closed form.
    $endgroup$
    – lulu
    Oct 4 '18 at 12:08










  • $begingroup$
    For the specific numbers $5$ and $4$, there’s an easy ad hoc argument. If there were at least $5$ balls of each color available, there would be ${3+5-1choose5}=21$ ways to pick $5$ balls out of the urn. If the urn contains just $4$ balls of each color, $3$ of these ways are impossible (5 balls of one of the three colors), so there are $18$ ways.
    $endgroup$
    – Steve Kass
    Dec 11 '18 at 15:22
















0












$begingroup$


Assumed you have balls with three different colors in an urn. From each type of ball you have four pieces that are not distinguishable. How many ways are there to pick five balls out of the urn?



Or in general with balls in $k$ different colors and $m$ balls of each of the color how many ways are there to pick $n$ balls out of the urn?



The problem is easy if $n leq m$. Then it is just an unordered selection with repetition allowed. Therefore there are $binom{k+n-1}{n}$ ways to pick. But if $n > m$ repetition is not necessarily allowed and I cannot find a beautiful way to calculate the number of ways. For small examples I might be able to find the solution step by step but on a larger scale I need help.






combinatorics







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Well, I'd implement it recursively. If $F(k,m,n)$ is your answer then looking at the options for the $k^{th}$ color we see that $F(k,m,n)=sum_{i=0}^m F(k-1,m,n-i)$. I don't expect this to have a convenient closed form.
    $endgroup$
    – lulu
    Oct 4 '18 at 12:08










  • $begingroup$
    For the specific numbers $5$ and $4$, there’s an easy ad hoc argument. If there were at least $5$ balls of each color available, there would be ${3+5-1choose5}=21$ ways to pick $5$ balls out of the urn. If the urn contains just $4$ balls of each color, $3$ of these ways are impossible (5 balls of one of the three colors), so there are $18$ ways.
    $endgroup$
    – Steve Kass
    Dec 11 '18 at 15:22














0












0








0





$begingroup$


Assumed you have balls with three different colors in an urn. From each type of ball you have four pieces that are not distinguishable. How many ways are there to pick five balls out of the urn?



Or in general with balls in $k$ different colors and $m$ balls of each of the color how many ways are there to pick $n$ balls out of the urn?



The problem is easy if $n leq m$. Then it is just an unordered selection with repetition allowed. Therefore there are $binom{k+n-1}{n}$ ways to pick. But if $n > m$ repetition is not necessarily allowed and I cannot find a beautiful way to calculate the number of ways. For small examples I might be able to find the solution step by step but on a larger scale I need help.






combinatorics







share|cite|improve this question











$endgroup$




Assumed you have balls with three different colors in an urn. From each type of ball you have four pieces that are not distinguishable. How many ways are there to pick five balls out of the urn?



Or in general with balls in $k$ different colors and $m$ balls of each of the color how many ways are there to pick $n$ balls out of the urn?



The problem is easy if $n leq m$. Then it is just an unordered selection with repetition allowed. Therefore there are $binom{k+n-1}{n}$ ways to pick. But if $n > m$ repetition is not necessarily allowed and I cannot find a beautiful way to calculate the number of ways. For small examples I might be able to find the solution step by step but on a larger scale I need help.






combinatorics




combinatorics






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Oct 5 '18 at 9:26









N. F. Taussig

44.4k93357




44.4k93357










asked Oct 4 '18 at 11:58









Erdbeer0815Erdbeer0815

1887




1887








  • 1




    $begingroup$
    Well, I'd implement it recursively. If $F(k,m,n)$ is your answer then looking at the options for the $k^{th}$ color we see that $F(k,m,n)=sum_{i=0}^m F(k-1,m,n-i)$. I don't expect this to have a convenient closed form.
    $endgroup$
    – lulu
    Oct 4 '18 at 12:08










  • $begingroup$
    For the specific numbers $5$ and $4$, there’s an easy ad hoc argument. If there were at least $5$ balls of each color available, there would be ${3+5-1choose5}=21$ ways to pick $5$ balls out of the urn. If the urn contains just $4$ balls of each color, $3$ of these ways are impossible (5 balls of one of the three colors), so there are $18$ ways.
    $endgroup$
    – Steve Kass
    Dec 11 '18 at 15:22














  • 1




    $begingroup$
    Well, I'd implement it recursively. If $F(k,m,n)$ is your answer then looking at the options for the $k^{th}$ color we see that $F(k,m,n)=sum_{i=0}^m F(k-1,m,n-i)$. I don't expect this to have a convenient closed form.
    $endgroup$
    – lulu
    Oct 4 '18 at 12:08










  • $begingroup$
    For the specific numbers $5$ and $4$, there’s an easy ad hoc argument. If there were at least $5$ balls of each color available, there would be ${3+5-1choose5}=21$ ways to pick $5$ balls out of the urn. If the urn contains just $4$ balls of each color, $3$ of these ways are impossible (5 balls of one of the three colors), so there are $18$ ways.
    $endgroup$
    – Steve Kass
    Dec 11 '18 at 15:22








1




1




$begingroup$
Well, I'd implement it recursively. If $F(k,m,n)$ is your answer then looking at the options for the $k^{th}$ color we see that $F(k,m,n)=sum_{i=0}^m F(k-1,m,n-i)$. I don't expect this to have a convenient closed form.
$endgroup$
– lulu
Oct 4 '18 at 12:08




$begingroup$
Well, I'd implement it recursively. If $F(k,m,n)$ is your answer then looking at the options for the $k^{th}$ color we see that $F(k,m,n)=sum_{i=0}^m F(k-1,m,n-i)$. I don't expect this to have a convenient closed form.
$endgroup$
– lulu
Oct 4 '18 at 12:08












$begingroup$
For the specific numbers $5$ and $4$, there’s an easy ad hoc argument. If there were at least $5$ balls of each color available, there would be ${3+5-1choose5}=21$ ways to pick $5$ balls out of the urn. If the urn contains just $4$ balls of each color, $3$ of these ways are impossible (5 balls of one of the three colors), so there are $18$ ways.
$endgroup$
– Steve Kass
Dec 11 '18 at 15:22




$begingroup$
For the specific numbers $5$ and $4$, there’s an easy ad hoc argument. If there were at least $5$ balls of each color available, there would be ${3+5-1choose5}=21$ ways to pick $5$ balls out of the urn. If the urn contains just $4$ balls of each color, $3$ of these ways are impossible (5 balls of one of the three colors), so there are $18$ ways.
$endgroup$
– Steve Kass
Dec 11 '18 at 15:22










2 Answers
2






active

oldest

votes


















1












$begingroup$

If you compute
$$f(x):=(1+x+x^2+ldots+x^m)^k$$
by multiplying distributively you obtain for each legal pick of $m_1$, $m_2$, $ldots$, $m_k$ balls with total $m_1+m_2+ldots+m_k=n$ a term $x^{m_1+m_2+ldots+m_k}=x^n$. We therefore have to compute the coefficient of $x^n$ in the expansion
$$f(x)=left({1-x^{m+1}over1-x}right)^k=sum_{j=0}^k{kchoose j}bigl(-x^{m+1}bigr)^jcdotsum_{l=0}^infty{k+l-1choose l},x^l .$$
Collecting terms we obtain a finite alternating sum of products of binomial coefficients. This sum can be interpreted combinatorially as result of a certain inclusion/exclusion process. Maybe someone will put forward a solution in this other realm.






share|cite|improve this answer









$endgroup$





















    0












    $begingroup$

    This is the same question as asking the number of ways to fit $n$ blocks into a Young diagram with sides of length $k$ and $m$, and involves q-binomials in the solution. So if you have $n$ blocks where $0leq nleq k m$, then the answer is the $n$th coefficient of the polynomial gained from the q-binomial term:



    $left[
    begin{array}{c}
    h+j \
    j \
    end{array}
    right]_q$



    Here's some links, the first gives an example of how to work it.



    http://mathworld.wolfram.com/q-BinomialCoefficient.html



    https://www.math.upenn.edu/~pemantle/papers/Preprints/qBinomial.pdf



    This paper by Dr. Proctor is just a fun read, and has a nice graphic showing the problem.



    https://www.jstor.org/stable/pdf/2975833.pdf?refreqid=excelsior%3A0abe07e98cab72b8b5fe076b50358d86






    share|cite|improve this answer











    $endgroup$













      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      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%2f2942028%2fnumber-of-ways-to-pick-balls-from-an-urn-if-one-type-of-ball-runs-out%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$

      If you compute
      $$f(x):=(1+x+x^2+ldots+x^m)^k$$
      by multiplying distributively you obtain for each legal pick of $m_1$, $m_2$, $ldots$, $m_k$ balls with total $m_1+m_2+ldots+m_k=n$ a term $x^{m_1+m_2+ldots+m_k}=x^n$. We therefore have to compute the coefficient of $x^n$ in the expansion
      $$f(x)=left({1-x^{m+1}over1-x}right)^k=sum_{j=0}^k{kchoose j}bigl(-x^{m+1}bigr)^jcdotsum_{l=0}^infty{k+l-1choose l},x^l .$$
      Collecting terms we obtain a finite alternating sum of products of binomial coefficients. This sum can be interpreted combinatorially as result of a certain inclusion/exclusion process. Maybe someone will put forward a solution in this other realm.






      share|cite|improve this answer









      $endgroup$


















        1












        $begingroup$

        If you compute
        $$f(x):=(1+x+x^2+ldots+x^m)^k$$
        by multiplying distributively you obtain for each legal pick of $m_1$, $m_2$, $ldots$, $m_k$ balls with total $m_1+m_2+ldots+m_k=n$ a term $x^{m_1+m_2+ldots+m_k}=x^n$. We therefore have to compute the coefficient of $x^n$ in the expansion
        $$f(x)=left({1-x^{m+1}over1-x}right)^k=sum_{j=0}^k{kchoose j}bigl(-x^{m+1}bigr)^jcdotsum_{l=0}^infty{k+l-1choose l},x^l .$$
        Collecting terms we obtain a finite alternating sum of products of binomial coefficients. This sum can be interpreted combinatorially as result of a certain inclusion/exclusion process. Maybe someone will put forward a solution in this other realm.






        share|cite|improve this answer









        $endgroup$
















          1












          1








          1





          $begingroup$

          If you compute
          $$f(x):=(1+x+x^2+ldots+x^m)^k$$
          by multiplying distributively you obtain for each legal pick of $m_1$, $m_2$, $ldots$, $m_k$ balls with total $m_1+m_2+ldots+m_k=n$ a term $x^{m_1+m_2+ldots+m_k}=x^n$. We therefore have to compute the coefficient of $x^n$ in the expansion
          $$f(x)=left({1-x^{m+1}over1-x}right)^k=sum_{j=0}^k{kchoose j}bigl(-x^{m+1}bigr)^jcdotsum_{l=0}^infty{k+l-1choose l},x^l .$$
          Collecting terms we obtain a finite alternating sum of products of binomial coefficients. This sum can be interpreted combinatorially as result of a certain inclusion/exclusion process. Maybe someone will put forward a solution in this other realm.






          share|cite|improve this answer









          $endgroup$



          If you compute
          $$f(x):=(1+x+x^2+ldots+x^m)^k$$
          by multiplying distributively you obtain for each legal pick of $m_1$, $m_2$, $ldots$, $m_k$ balls with total $m_1+m_2+ldots+m_k=n$ a term $x^{m_1+m_2+ldots+m_k}=x^n$. We therefore have to compute the coefficient of $x^n$ in the expansion
          $$f(x)=left({1-x^{m+1}over1-x}right)^k=sum_{j=0}^k{kchoose j}bigl(-x^{m+1}bigr)^jcdotsum_{l=0}^infty{k+l-1choose l},x^l .$$
          Collecting terms we obtain a finite alternating sum of products of binomial coefficients. This sum can be interpreted combinatorially as result of a certain inclusion/exclusion process. Maybe someone will put forward a solution in this other realm.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Oct 4 '18 at 13:20









          Christian BlatterChristian Blatter

          174k8115327




          174k8115327























              0












              $begingroup$

              This is the same question as asking the number of ways to fit $n$ blocks into a Young diagram with sides of length $k$ and $m$, and involves q-binomials in the solution. So if you have $n$ blocks where $0leq nleq k m$, then the answer is the $n$th coefficient of the polynomial gained from the q-binomial term:



              $left[
              begin{array}{c}
              h+j \
              j \
              end{array}
              right]_q$



              Here's some links, the first gives an example of how to work it.



              http://mathworld.wolfram.com/q-BinomialCoefficient.html



              https://www.math.upenn.edu/~pemantle/papers/Preprints/qBinomial.pdf



              This paper by Dr. Proctor is just a fun read, and has a nice graphic showing the problem.



              https://www.jstor.org/stable/pdf/2975833.pdf?refreqid=excelsior%3A0abe07e98cab72b8b5fe076b50358d86






              share|cite|improve this answer











              $endgroup$


















                0












                $begingroup$

                This is the same question as asking the number of ways to fit $n$ blocks into a Young diagram with sides of length $k$ and $m$, and involves q-binomials in the solution. So if you have $n$ blocks where $0leq nleq k m$, then the answer is the $n$th coefficient of the polynomial gained from the q-binomial term:



                $left[
                begin{array}{c}
                h+j \
                j \
                end{array}
                right]_q$



                Here's some links, the first gives an example of how to work it.



                http://mathworld.wolfram.com/q-BinomialCoefficient.html



                https://www.math.upenn.edu/~pemantle/papers/Preprints/qBinomial.pdf



                This paper by Dr. Proctor is just a fun read, and has a nice graphic showing the problem.



                https://www.jstor.org/stable/pdf/2975833.pdf?refreqid=excelsior%3A0abe07e98cab72b8b5fe076b50358d86






                share|cite|improve this answer











                $endgroup$
















                  0












                  0








                  0





                  $begingroup$

                  This is the same question as asking the number of ways to fit $n$ blocks into a Young diagram with sides of length $k$ and $m$, and involves q-binomials in the solution. So if you have $n$ blocks where $0leq nleq k m$, then the answer is the $n$th coefficient of the polynomial gained from the q-binomial term:



                  $left[
                  begin{array}{c}
                  h+j \
                  j \
                  end{array}
                  right]_q$



                  Here's some links, the first gives an example of how to work it.



                  http://mathworld.wolfram.com/q-BinomialCoefficient.html



                  https://www.math.upenn.edu/~pemantle/papers/Preprints/qBinomial.pdf



                  This paper by Dr. Proctor is just a fun read, and has a nice graphic showing the problem.



                  https://www.jstor.org/stable/pdf/2975833.pdf?refreqid=excelsior%3A0abe07e98cab72b8b5fe076b50358d86






                  share|cite|improve this answer











                  $endgroup$



                  This is the same question as asking the number of ways to fit $n$ blocks into a Young diagram with sides of length $k$ and $m$, and involves q-binomials in the solution. So if you have $n$ blocks where $0leq nleq k m$, then the answer is the $n$th coefficient of the polynomial gained from the q-binomial term:



                  $left[
                  begin{array}{c}
                  h+j \
                  j \
                  end{array}
                  right]_q$



                  Here's some links, the first gives an example of how to work it.



                  http://mathworld.wolfram.com/q-BinomialCoefficient.html



                  https://www.math.upenn.edu/~pemantle/papers/Preprints/qBinomial.pdf



                  This paper by Dr. Proctor is just a fun read, and has a nice graphic showing the problem.



                  https://www.jstor.org/stable/pdf/2975833.pdf?refreqid=excelsior%3A0abe07e98cab72b8b5fe076b50358d86







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Dec 11 '18 at 15:53

























                  answered Dec 11 '18 at 14:09









                  MikeYMikeY

                  1938




                  1938






























                      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%2f2942028%2fnumber-of-ways-to-pick-balls-from-an-urn-if-one-type-of-ball-runs-out%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

                      Plaza Victoria

                      Image
                      Plaza Victoria Plaza Victoria en 2017 Otros nombres Plaza de La Victoria Localización El Almendral, Valparaíso, Chile Vías adyacentes Chacabuco, Molina, Plaza Victoria y Edwards Creación 1841 Metro Bellavista Ubicación 33°02′46″S 71°37′11″O  /  -33.04624167, -71.61980833 Coordenadas: 33°02′46″S 71°37′11″O  /  -33.04624167, -71.61980833 [editar datos en Wikidata] La Plaza Victoria , también llamada Plaza de la Victoria , [ 1 ] ​ es una plaza ubicada en el sector El Almendral del plan de la ciudad de Valparaíso, Chile, de importancia patrimonial, que incluye valiosas estatuas y especies vegetales. [ 2 ] ​ La plaza se creó como tal en la primera mitad del siglo XIX, tomando previamente los nombres de Plaza Nueva y Plaza de Orrego . Si bien desde sus inicios tuvo relevancia histórica, no fue sino a partir de fines de los años 1860 cuando comenzó a cobrar mayor importancia y se convirtió en uno de los principales centros sociales de l...
                      Read more

                      Brian Clough

                      Image
                      Brian Clough Datos personales Nombre completo Brian Howard Clough Apodo(s) Old Big 'Ead, Cloughie [ 1 ] ​ Nacimiento Middlesbrough, Inglaterra, Reino Unido 21 de marzo de 1935 Nacionalidad(es) Fallecimiento Derby, Reino Unido 20 de septiembre de 2004 (69 años) Altura 1,78 [ 1 ] ​ metros Carrera Deporte Fútbol Debut deportivo 1955 (Como jugador) 1965 (Como entrenador) (Middlesbrough F. C. (Como jugador) Hartlepool United F. C. (Como entrenador) ) Posición Delantero Goles en clubes 269 [ 2 ] ​ Retirada deportiva 1964 (Como jugador) 1993 (Como entrenador) (Sunderland A. F. C. (Como jugador) Nottingham Forest (Como entrenador) ) Carrera internacional Part. 2 [editar datos en Wikidata] Brian Howard Clough , OBE [ 3 ] ​ (Middlesbrough, Inglaterra, Reino Unido, 21 de marzo de 1935 – Derby, Inglaterra, Reino Unido, 20 de septiembre de 2004) fue un jugador y entrenador británico de fútbol. Es conocido por...
                      Read more

                      Cáceres

                      Image
                      Para otros usos de este término, véase Cáceres (desambiguación). Cáceres Municipio y ciudad Bandera Escudo Collage de Cáceres Cáceres Ubicación de Cáceres en España. Cáceres Ubicación de Cáceres en la provincia de Cáceres. País  España • Com. autónoma  Extremadura • Provincia  Cáceres • Partido judicial Cáceres Ubicación 39°28′23″N 6°22′16″O  /  39.473055555556, -6.3711111111111 Coordenadas: 39°28′23″N 6°22′16″O  /  39.473055555556, -6.3711111111111 • Altitud 457 [ 1 ] ​ msnm (mín.:211 [ 2 ] ​, máx.:708 [ 2 ] ​) Superficie 1750,33 km² Núcleos de población Cáceres Estación Arroyo-Malpartida Rincón de Ballesteros Valdesalor Fundación 34 a. C. Población 96 068 hab. (2018) • Densidad 54,8 hab./km² Gentilicio Cacereño/a [ 3 ] ​ Código postal 10001-10005, 10195 Alcaldesa (2015) María Elena Nevado del Campo [ 4 ] ​ Presupuesto 69.045.004€ [ 5 ] ​  (año ...
                      Read more