tutorial-basic-combinatorics.sws
system:sage


Tutorial: Basic combinatorics in Sage -- Sage Reference Manual v4.6
system:sage

<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index" accesskey="I">index</a></li>
        <li class="right">
          <a href="../modindex.html" title="Global Module Index" accesskey="M">modules</a> |</li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Sage Reference v4.6</a> &raquo;</li>
 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="tutorial-basic-combinatorics-in-sage">
<span id="tutorial-basic-combinatorics"></span><h1>Tutorial: Basic combinatorics in Sage<a class="headerlink" href="#tutorial-basic-combinatorics-in-sage" title="Permalink to this headline">¶</a></h1>
<div class="section" id="exercice-poker-and-probability">
<h2>Exercice: Poker and probability<a class="headerlink" href="#exercice-poker-and-probability" title="Permalink to this headline">¶</a></h2>
<p>A poker card is characterized by a <em>suit</em> (&#8220;spades&#8221;, &#8220;hearts&#8221;, &#8220;diamonds&#8221;,
&#8220;clubs&#8221;) and a <em>rank</em> (<img class="math" src="../_images/math/c14b72ddb47c1a5a508eadcb1b62b31669155c59.png" alt="2, 3, \dots, 9">, &#8220;Jack&#8221;, &#8220;Queen&#8221;, &#8220;King&#8221; and &#8220;Ace&#8221;).
Here is the way to define suits in sage:</p>
<div class="highlight-python">

{{{id=0|
Suits = Set([&quot;spades&quot;, &quot;hearts&quot;, &quot;diamonds&quot;, &quot;clubs&quot;])
///
}}}

</div>
<p>Define similarly the set <tt class="docutils literal"><span class="pre">Ranks</span></tt>:</p>
<div class="highlight-python">

{{{id=1|

///
}}}

</div>
<p>The deck of card is the cartesian product of the set of suits by the set of
ranks. Define a set <tt class="docutils literal"><span class="pre">Cards</span></tt> accordingly:</p>
<div class="highlight-python">

{{{id=2|

///
}}}

</div>
<p>Use the method <tt class="docutils literal"><span class="pre">.cardinality()</span></tt> to compute the number of suits, ranks and
cards:</p>
<div class="highlight-python">

{{{id=3|

///
}}}

</div>
<div class="highlight-python">

{{{id=4|

///
}}}

</div>
<div class="highlight-python">

{{{id=5|

///
}}}

</div>
<p>Draw a card at random:</p>
<div class="highlight-python">

{{{id=6|

///
}}}

</div>
<p>Cards are (currently) returned as lists. To be able to build a set of cards,
we need them to be <em>hashable</em>. Let&#8217;s redefine the set of cards by transforming
cards to tuples:</p>
<div class="highlight-python">

{{{id=7|
Cards = CartesianProduct(Suits, Ranks).map(tuple)
///
}}}

</div>
<p>Use <tt class="docutils literal"><span class="pre">Subsets</span></tt> to draw a hand of five cards at random:</p>
<div class="highlight-python">

{{{id=8|

///
}}}

</div>
<p>Use <tt class="docutils literal"><span class="pre">.cardinality()</span></tt> to compute the number of hands, check the result with
<tt class="docutils literal"><span class="pre">binomial</span></tt>:</p>
<div class="highlight-python">

{{{id=9|

///
}}}

</div>
<p>To go further, see exercises 38, 39, 40 in <em>Calcul Mathématique avec Sage</em>
(version 1.0) page 255.</p>
</div>
<div class="section" id="using-existing-enumerated-sets">
<h2>Using existing Enumerated Sets<a class="headerlink" href="#using-existing-enumerated-sets" title="Permalink to this headline">¶</a></h2>
<ol class="arabic">
<li><p class="first">List all the strict partitions of <img class="math" src="../_images/math/79069377f91364c2f87a64e5f9f562a091c8a6c1.png" alt="5"> (hint: use
<tt class="docutils literal"><span class="pre">Partitions</span></tt> with <tt class="docutils literal"><span class="pre">max_slope</span></tt>):</p>
<div class="highlight-python">

{{{id=10|

///
}}}

</div>
</li>
<li><p class="first">List all the vectors of <tt class="docutils literal"><span class="pre">0</span></tt> and <tt class="docutils literal"><span class="pre">1</span></tt> of length <tt class="docutils literal"><span class="pre">5</span></tt> (hint: use
<tt class="docutils literal"><span class="pre">IntegerVectors</span></tt> with <tt class="docutils literal"><span class="pre">max_part</span></tt>):</p>
<div class="highlight-python">

{{{id=11|

///
}}}

</div>
<p>You can also use a cartesian product:</p>
<div class="highlight-python">

{{{id=12|

///
}}}

</div>
</li>
<li><p class="first">List all the Dyck words of length <tt class="docutils literal"><span class="pre">6</span></tt>:</p>
<div class="highlight-python">

{{{id=13|

///
}}}

</div>
</li>
</ol>
<p>Here is the way to print the standard tableaux of size $4$:</p>
<div class="highlight-python">

{{{id=14|
for t in StandardTableaux(3): t.pp(); print
///
1  2  3

1  3
2

1  2
3

1
2
3
}}}

</div>
<ol class="arabic">
<li><p class="first">Define the set of all the partitions of <img class="math" src="../_images/math/dce34f4dfb2406144304ad0d6106c5382ddd1446.png" alt="1"> to <img class="math" src="../_images/math/79069377f91364c2f87a64e5f9f562a091c8a6c1.png" alt="5"> (hint: use
<tt class="docutils literal"><span class="pre">DisjointUnionEnumeratedSets</span></tt>):</p>
<div class="highlight-python">

{{{id=15|

///
}}}

</div>
</li>
</ol>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="../index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference external" href="">Tutorial: Basic combinatorics in Sage</a><ul>
<li><a class="reference external" href="#exercice-poker-and-probability">Exercice: Poker and probability</a></li>
<li><a class="reference external" href="#using-existing-enumerated-sets">Using existing Enumerated Sets</a></li>
</ul>
</li>
</ul>

            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="../_sources/demos/tutorial-basic-combinatorics.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index">index</a></li>
        <li class="right">
          <a href="../modindex.html" title="Global Module Index">modules</a> |</li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Sage Reference v4.6</a> &raquo;</li>
 
      </ul>
    </div>
    
    <div class="footer">
      &copy; Copyright 2005--2010, The Sage Development Team.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.3.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>