{"id":316,"date":"2014-11-23T12:00:02","date_gmt":"2014-11-23T20:00:02","guid":{"rendered":"http:\/\/mostlymental.com\/?p=316"},"modified":"2014-11-24T20:12:14","modified_gmt":"2014-11-25T04:12:14","slug":"permutations","status":"publish","type":"post","link":"http:\/\/mostlymental.com\/?p=316","title":{"rendered":"Permutations"},"content":{"rendered":"<p>Hello everyone!<\/p>\n<p>This week, I'd like to talk about permutations.\u00a0 A permutation of a list is another list with the same elements in some order.\u00a0 For instance, imagine a deck of playing cards.\u00a0 Any way you shuffle the cards, you get the same cards, but you might get a different order.\u00a0 So the resulting ordering is a permutation of the original ordering.<\/p>\n<p>It turns out that for permutations, the specific items in our list don't matter all that much.\u00a0 We can rename the items in the list however we like.\u00a0 For instance, we could take our deck of cards and give each a different color, or we could number them <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_7cb34aec1f29f93734a0500bcc87edd9.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.\u00a0 Then we can think of shuffling the cards as rearranging <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_9a1158154dfa42caddbd0694a4e9bdc8.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> colors or permuting the numbers <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_c4ca4238a0b923820dcc509a6f75849b.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> through <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_9a1158154dfa42caddbd0694a4e9bdc8.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p><!--more--><\/p>\n<p>&nbsp;<\/p>\n<p>The first thing we might want to know is how many permutations of <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_5c7f2194df8be663421ba6a6dcca7050.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> there are.\u00a0 For instance, when <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_fa346db4ae0286d4c297bdfea3041cab.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, we have <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_1679091c5a880faf6fb5e6087eb1b2dc.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> permutations, as shown below.<a href=\"http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"size-medium wp-image-338 aligncenter\" src=\"http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_3-113x300.png\" alt=\"perm_3\" width=\"113\" height=\"300\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p>To answer more generally, let's look at each element of our list.\u00a0 There are <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> possible values that our list could start with.\u00a0 We can't reuse this first value, so there are <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_f69fdffb82267fca1be8c6913635b318.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> values that could come next.\u00a0 We can't reuse either of these values, so there are <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_18f83fb5ad488b078566b61892a9ff40.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> possibilities for the next value.\u00a0 And so on, until we're left with only one choice for the last value.\u00a0 That gives us <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_9e330ea7bb6052225be8b4528bb40c76.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> total permutations.\u00a0 That formula's a bit unwieldy, and it shows up a lot, so we usually simplify it to <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_e6e622bea689b34e7409a5d98adca446.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> (pronounced \"<span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> factorial\").\u00a0 Thus, there are <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_e6e622bea689b34e7409a5d98adca446.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> permutations of <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> elements. <a href=\"http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_tree_simple.png\"><img loading=\"lazy\" decoding=\"async\" class=\"size-medium wp-image-371 aligncenter\" src=\"http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_tree_simple-300x208.png\" alt=\"perm_tree_simple\" width=\"300\" height=\"208\" srcset=\"http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_tree_simple-300x208.png 300w, http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_tree_simple.png 543w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p>We're talking about combinatorics here, so let's count that a different way.\u00a0 Say we color the numbers <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_03c48c8de9613f3b9039d1dbf9f277c1.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> red and the numbers <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_512bc8e44abda87b905582af2b3668aa.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> blue.\u00a0 How many ways can we permute them now?<a href=\"http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_choose.png\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-337 aligncenter\" src=\"http:\/\/mostlymental.com\/wp-content\/uploads\/2014\/11\/perm_choose.png\" alt=\"perm_choose\" width=\"255\" height=\"300\" \/><\/a>First, let's choose which positions end up with a red number.\u00a0 We're trying to place <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> numbers, and <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of them are red, so we have <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_faafdfefb6f6bb072b219a2597fb4cc4.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> ways to pick red numbers.\u00a0 (If you don't remember this symbol, I talked about it in a <a href=\"http:\/\/mostlymental.com\/?p=157\">previous post<\/a>.)\u00a0 We then have to pick an order for the red numbers, which as we saw earlier, can happen in <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_f63bd46cc3a1250b4815e3d1740b5d83.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> ways.\u00a0 We also have to arrange the blue numbers, which can happen in <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_8723d62962035b1e73b34654f49a3d09.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> ways.\u00a0 Putting it all together, we get <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_89519e5bc418084c04f91c1ec1fac489.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> permutations.But as we saw earlier, there are also <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_e6e622bea689b34e7409a5d98adca446.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> permutations.\u00a0 So <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_ba6b44f3cbda397a4703e61d8e2446b8.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.\u00a0 Rearranging, we get <span class='MathJax_Preview'><img src='http:\/\/mostlymental.com\/wp-content\/plugins\/latex\/cache\/tex_606833371656a8eece77c95effa48060.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.\u00a0 This gives us a nice formula for our binomial coefficients!<\/p>\n<p>&nbsp;<\/p>\n<p>There's plenty more to say about permutations.\u00a0 They lead naturally into topics like <a href=\"http:\/\/groupprops.subwiki.org\/wiki\/Cycle_decomposition_for_permutations\">cycle decomposition<\/a>, <a href=\"http:\/\/www.cut-the-knot.org\/do_you_know\/sgroups.shtml\">symmetric groups<\/a>,\u00a0 and <a href=\"http:\/\/www.artofproblemsolving.com\/Wiki\/index.php\/Derangement\">derangements<\/a>.\u00a0 If you'd like to know more, I'm happy to talk about things in the comments.<\/p>\n<a class=\"synved-social-button synved-social-button-share synved-social-size-48 synved-social-resolution-single synved-social-provider-facebook nolightbox\" data-provider=\"facebook\" target=\"_blank\" rel=\"nofollow\" title=\"Share on Facebook\" href=\"https:\/\/www.facebook.com\/sharer.php?u=http%3A%2F%2Fmostlymental.com&amp;t=Permutations&amp;s=100&amp;p[url]=http%3A%2F%2Fmostlymental.com&amp;p[images][0]=http%3A%2F%2Fmostlymental.com%2Fwp-content%2Fuploads%2F2014%2F11%2Fperm_3-113x300.png&amp;p[title]=Permutations\" style=\"font-size: 0px;width:48px;height:48px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"Facebook\" title=\"Share on Facebook\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"48\" height=\"48\" style=\"display: inline;width:48px;height:48px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"http:\/\/mostlymental.com\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/96x96\/facebook.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-48 synved-social-resolution-single synved-social-provider-twitter nolightbox\" data-provider=\"twitter\" target=\"_blank\" rel=\"nofollow\" title=\"Share on Twitter\" href=\"https:\/\/twitter.com\/intent\/tweet?url=http%3A%2F%2Fmostlymental.com&amp;text=Hey%20check%20this%20out\" style=\"font-size: 0px;width:48px;height:48px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"twitter\" title=\"Share on Twitter\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"48\" height=\"48\" style=\"display: inline;width:48px;height:48px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"http:\/\/mostlymental.com\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/96x96\/twitter.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-48 synved-social-resolution-single synved-social-provider-reddit nolightbox\" data-provider=\"reddit\" target=\"_blank\" rel=\"nofollow\" title=\"Share on Reddit\" href=\"https:\/\/www.reddit.com\/submit?url=http%3A%2F%2Fmostlymental.com&amp;title=Permutations\" style=\"font-size: 0px;width:48px;height:48px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"reddit\" title=\"Share on Reddit\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"48\" height=\"48\" style=\"display: inline;width:48px;height:48px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"http:\/\/mostlymental.com\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/96x96\/reddit.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-48 synved-social-resolution-single synved-social-provider-pinterest nolightbox\" data-provider=\"pinterest\" target=\"_blank\" rel=\"nofollow\" title=\"Pin it with Pinterest\" href=\"https:\/\/pinterest.com\/pin\/create\/button\/?url=http%3A%2F%2Fmostlymental.com&amp;media=http%3A%2F%2Fmostlymental.com%2Fwp-content%2Fuploads%2F2014%2F11%2Fperm_3-113x300.png&amp;description=Permutations\" style=\"font-size: 0px;width:48px;height:48px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"pinterest\" title=\"Pin it with Pinterest\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"48\" height=\"48\" style=\"display: inline;width:48px;height:48px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"http:\/\/mostlymental.com\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/96x96\/pinterest.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-48 synved-social-resolution-single synved-social-provider-linkedin nolightbox\" data-provider=\"linkedin\" target=\"_blank\" rel=\"nofollow\" title=\"Share on Linkedin\" href=\"https:\/\/www.linkedin.com\/shareArticle?mini=true&amp;url=http%3A%2F%2Fmostlymental.com&amp;title=Permutations\" style=\"font-size: 0px;width:48px;height:48px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"linkedin\" title=\"Share on Linkedin\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"48\" height=\"48\" style=\"display: inline;width:48px;height:48px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"http:\/\/mostlymental.com\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/96x96\/linkedin.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-48 synved-social-resolution-single synved-social-provider-mail nolightbox\" data-provider=\"mail\" rel=\"nofollow\" title=\"Share by email\" href=\"mailto:?subject=Permutations&amp;body=Hey%20check%20this%20out:%20http%3A%2F%2Fmostlymental.com\" style=\"font-size: 0px;width:48px;height:48px;margin:0;margin-bottom:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"mail\" title=\"Share by email\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"48\" height=\"48\" style=\"display: inline;width:48px;height:48px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"http:\/\/mostlymental.com\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/96x96\/mail.png\" \/><\/a><a class=\"synved-social-credit\" target=\"_blank\" rel=\"nofollow\" title=\"WordPress Social Media Feather\" href=\"http:\/\/synved.com\/wordpress-social-media-feather\/\" style=\"color:#444;text-decoration:none;font-size:8px;margin-left:5px;vertical-align:10px;white-space:nowrap\"><span>by <\/span><img loading=\"lazy\" decoding=\"async\" style=\"display: inline;margin:0;padding:0;width:16px;height:16px\" width=\"16\" height=\"16\" alt=\"feather\" src=\"http:\/\/mostlymental.com\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/icon.png\" \/><\/a>","protected":false},"excerpt":{"rendered":"<p>Hello everyone! This week, I'd like to talk about permutations.\u00a0 A permutation of a list is another list with the same elements in some order.\u00a0 For instance, imagine a deck of playing cards.\u00a0 Any way you shuffle the cards, you get the same cards, but you might get a different order.\u00a0 So the resulting ordering &hellip; <a href=\"http:\/\/mostlymental.com\/?p=316\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Permutations<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,2],"tags":[],"class_list":["post-316","post","type-post","status-publish","format-standard","hentry","category-combinatorics","category-math"],"_links":{"self":[{"href":"http:\/\/mostlymental.com\/index.php?rest_route=\/wp\/v2\/posts\/316","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/mostlymental.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/mostlymental.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/mostlymental.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/mostlymental.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=316"}],"version-history":[{"count":10,"href":"http:\/\/mostlymental.com\/index.php?rest_route=\/wp\/v2\/posts\/316\/revisions"}],"predecessor-version":[{"id":373,"href":"http:\/\/mostlymental.com\/index.php?rest_route=\/wp\/v2\/posts\/316\/revisions\/373"}],"wp:attachment":[{"href":"http:\/\/mostlymental.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/mostlymental.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=316"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/mostlymental.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}