title: Simple combinatorics: Number of ways to pair up elements
body: <p>I am trying to solve this question: <a href="https://www.urionlinejudge.com.br/judge/en/problems/view/1616" rel="nofollow noreferrer">https://www.urionlinejudge.com.br/judge/en/problems/view/1616</a></p>
  
  <blockquote>
    <p>It's the end of the year, and finally Rafael is graduating in his
    Computing course. His classmates decided to celebrate the graduation
    organizing a ball, where there would be live music, food and free
    drinks. As all balls, the most expected moment is the one in which
    everyone starts to dance in pairs.</p>
    
    <p>The pairs will be formed between a boy and a girl, and as Rafael's
    classmates are so shy, that they decided to plan ahead what the pairs
    would be. There is only one problem: there are more boys than girls in
    the class. This implies that, if everyone wants to dance at least
    once, one or more girls will have to dance with more than one boy.</p>
    
    <p>Rafael asked your help: in how many ways the pairs can be formed, in
    such a way that all the boys dance exactly once, and all the girls
    dance at least once</p>
  </blockquote>
  
  <p>While there might be a mathematical closed-form solution, I am trying to solve it using dynamic programming. I am not quite able to come up with the recurrence. Could someone point me in the right direction?</p>