[{"id":247457,"date":"2026-07-27T11:03:44","date_gmt":"2026-07-27T16:03:44","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=247457"},"modified":"2026-07-27T11:13:29","modified_gmt":"2026-07-27T16:13:29","slug":"counting-permutations-with-roots","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/counting-permutations-with-roots\/","title":{"rendered":"Counting permutations with roots"},"content":{"rendered":"

My post from yesterday<\/a> on permutation roots ends with a Mathematica code for finding the probability that a permutation of n<\/em> elements has a k<\/em>th root. This is done by finding the coefficient of x<\/em>n<\/em><\/sup> in the generating function<\/p>\n

\"\\prod_{m=1}^\\infty<\/p>\n

I wanted to say more about this, and look at implementing the same code in SymPy. I was curious how well SymPy would do because I’ve noticed that LLMs often generate SymPy code since it’s an open source CAS<\/abbr>.<\/p>\n

Wilf [1] describes the infinite product above as the exponential generating function (egf) of f<\/em>(n<\/em>, k<\/em>), the number of permutations of n<\/em> objects that have a k<\/em>th root. Since egfs have a n<\/em>! term in the denominator, this is also the ordinary generating function (ogf) of the probability<\/em> that a randomly chosen permutation on n<\/em> objects has a k<\/em>th root.<\/p>\n

My first attempt at using Mathematica to probe the generating function was<\/p>\n

expq[x_, q_] := MittagLefflerE[q, x^q]\t \r\np[n_, k_] :=  SeriesCoefficient[\t \r\n    Product[expq[x^m\/m, GCD[m, k]], {m, 1, Infinity}], {x, 0, n}]\r\n<\/pre>\n
This hung forever when I tried to use it on a small example. I realized, but apparently Mathematica did not, that Infinity<\/code> could be replaced by n<\/code> since terms higher than n<\/em> do not contribute to the coefficient of x<\/em>n<\/em><\/sup>. With that change, the code ran quickly.<\/p>\n
This morning I tried converting the Mathematica code to Sympy; Claude did this in one shot. I also reproduced the table of f<\/em>(n<\/em>, k<\/em>) values on page 150 of [1] to test the code. Since Wilf tabulated f<\/em>(n<\/em>, k<\/em>), not f<\/em>(n<\/em>, k<\/em>)\/n<\/em>!, I multiplied the results by n<\/em>!.<\/p>\n
Here is the output:<\/p>\n
k = 2 [1, 1, 3, 12, 60, 270, 1890, 14280, 128520, 1096200]\r\nk = 3 [1, 2, 4, 16, 80, 400, 2800, 22400, 181440, 1814400]\r\nk = 4 [1, 1, 3, 12, 60, 270, 1890, 13020, 117180, 1039500]\r\nk = 5 [1, 2, 6, 24, 96, 576, 4032, 32256, 290304, 2612736]\r\nk = 6 [1, 1, 1, 4, 40, 190, 1330, 8680, 52920, 340200]\r\nk = 7 [1, 2, 6, 24, 120, 720, 4320, 34560, 311040, 3110400]\r\n<\/pre>\n
and here is the SymPy code. I edited the main but the rest is verbatim from Claude.<\/p>\n
from sympy import symbols, gcd, factorial, Rational, S\r\n\r\nx = symbols('x')\r\n\r\ndef expq_coeffs(m, q, n):\r\n    \"\"\"\r\n    Truncated (degree <= n) series coefficients of\r\n        expq(x**m\/m, q) = MittagLefflerE(q, (x**m\/m)**q)\r\n    Since q is a positive integer:\r\n        E_q(y^q) = sum_j y^(q*j) \/ (q*j)!\r\n    with y = x**m\/m, so the term of degree m*q*j has coefficient\r\n        1 \/ ( m**(q*j) * (q*j)! ).\r\n    Returns a list c[0..n] of coefficients.\r\n    \"\"\"\r\n    c = [S.Zero] * (n + 1)\r\n    j = 0\r\n    while m * q * j <= n:\r\n        deg = m * q * j\r\n        c[deg] += Rational(1, m**(q * j) * factorial(q * j))\r\n        j += 1\r\n    return c\r\n\r\ndef poly_mult_trunc(a, b, n):\r\n    \"\"\"Multiply two series (lists of coeffs, index = degree) truncated to degree n.\"\"\"\r\n    c = [S.Zero] * (n + 1)\r\n    for i, ai in enumerate(a):\r\n        if ai == 0:\r\n            continue\r\n        max_j = n - i\r\n        for j2 in range(max_j + 1):\r\n            bj = b[j2]\r\n            if bj != 0:\r\n                c[i + j2] += ai * bj\r\n    return c\r\n\r\ndef p(n, k):\r\n    \"\"\"\r\n    SymPy equivalent of:\r\n        expq[x_, q_] := MittagLefflerE[q, x^q]\r\n        p[n_, k_] := SeriesCoefficient[\r\n            Product[expq[x^m\/m, GCD[m, k]], {m, 1, n}], {x, 0, n}]\r\n    \"\"\"\r\n    result = [S.Zero] * (n + 1)\r\n    result[0] = S.One\r\n    for m in range(1, n + 1):\r\n        q = gcd(m, k)\r\n        factor = expq_coeffs(m, q, n)\r\n        result = poly_mult_trunc(result, factor, n)\r\n    return result[n]\r\n\r\n# example\r\nif __name__ == \"__main__\":\r\n    for k in range(2, 8):\r\n        print(\"k =\", k, [factorial(n)*p(n, k) for n in range(1,11)])\r\n<\/pre>\n
[1] Herbert Wilf. Generatingfunctionology. Available online here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
My post from yesterday on permutation roots ends with a Mathematica code for finding the probability that a permutation of n elements has a kth root. This is done by finding the coefficient of xn in the generating function I wanted to say more about this, and look at implementing the same code in SymPy. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[197,87,142],"class_list":["post-247457","post","type-post","status-publish","format-standard","hentry","category-math","tag-combinatorics","tag-mathematica","tag-sympy"],"acf":[],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"Counting permutations with roots","description":"Counting permutations that have kth roots. A trick to make Mathematica work and porting the code to SymPy.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/counting-permutations-with-roots\/","robots":"max-image-preview:large","keywords":"combinatorics,mathematica,sympy","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Counting permutations with roots","og:description":"Counting permutations that have kth roots. A trick to make Mathematica work and porting the code to SymPy.","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/counting-permutations-with-roots\/","article:published_time":"2026-07-27T16:03:44+00:00","article:modified_time":"2026-07-27T16:13:29+00:00","twitter:card":"summary","twitter:title":"Counting permutations with roots","twitter:description":"Counting permutations that have kth roots. A trick to make Mathematica work and porting the code to SymPy.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247457","title":null,"description":"Counting permutations that have kth roots. A trick to make Mathematica work and porting the code to SymPy.","keywords":null,"keyphrases":{"focus":{"keyphrase":"","score":0,"analysis":{"keyphraseInTitle":{"score":0,"maxScore":9,"error":1}}},"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":"","og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":"default","schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":"-1","robots_max_videopreview":"-1","robots_max_imagepreview":"large","priority":null,"frequency":"default","location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"created":"2026-07-27 15:38:01","updated":"2026-07-27 16:13:29","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":"
\n\t\t\tHome<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tMath<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tCounting permutations with roots\n\t\t<\/span><\/div>","aioseo_breadcrumb_json":[{"label":"Home","link":"https:\/\/www.johndcook.com\/blog"},{"label":"Math","link":"https:\/\/www.johndcook.com\/blog\/category\/math\/"},{"label":"Counting permutations with roots","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/counting-permutations-with-roots\/"}],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247457","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=247457"}],"version-history":[{"count":2,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247457\/revisions"}],"predecessor-version":[{"id":247461,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247457\/revisions\/247461"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=247457"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=247457"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=247457"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":247449,"date":"2026-07-27T10:34:05","date_gmt":"2026-07-27T15:34:05","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=247449"},"modified":"2026-07-27T15:35:18","modified_gmt":"2026-07-27T20:35:18","slug":"float-binary","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/float-binary\/","title":{"rendered":"Printing floating point numbers in binary"},"content":{"rendered":"
It’s well known that you can convert the base 16 (hex) representation of an integer to the base 2 (binary) representation by simply converting each digit from hex to binary. For example,<\/p>\n
CAFEhex<\/sub> = 1100 1010 1111 1110two<\/sub><\/p>\n
I imagine it’s less well known that you can do the same thing with floating point numbers.<\/p>\n
I wanted to find the binary representation of a floating point number using Python, and discovered that it has no function to do this. However, there is a method on floats to show a hex representation. For example, here’s the hex representation of \u03c0.<\/p>\n
>>> import math\r\n>>> (math.pi).hex()\r\n'0x1.921fb54442d18p+1'\r\n<\/pre>\n
Curiously, the p+k<\/em> part at the end is an exponent of 2, not an exponent of 16. So after we convert 1.921fb54442d18 to binary, we’ll need to multiply by 2, i.e. move the fractional point one space to the right.<\/p>\n
So first we convert 1.921fb54442d18hex<\/sub> to binary by converting 1, 9, 2, etc. each to binary.<\/p>\n
1.1001 0010 0001 1111 1011 0101 0100 0100 0100 0010 1101 0001 1000two<\/sub><\/p>\n
Then after shifting the fraction point to account for the p+1<\/code> part we have<\/p>\n
\u03c0 = 11.001001000011111101101010100010001000010110100011000two<\/sub><\/p>\n
You could use Python’s bin() function to convert the fractional part, interpreted as an integer, to hex, though you may need to pad with 0 bits. For example,<\/p>\n
>>> (1.03).hex()\r\n'0x1.07ae147ae147bp+0\r\n\r\n>>> bin(0x7ae147ae147)\r\n'0b1111010111000010100011110101110000101000111'\r\n<\/pre>\n
The binary representation of 1.03ten<\/sub> is<\/p>\n
1.000001111010111000010100011110101110000101000111two<\/sub><\/p>\n
We added a total of five zero bits, four for the 0 after the fractional point and one for converting 7 to 0111two<\/sub>.<\/p>\n","protected":false},"excerpt":{"rendered":"
It’s well known that you can convert the base 16 (hex) representation of an integer to the base 2 (binary) representation by simply converting each digit from hex to binary. For example, CAFEhex = 1100 1010 1111 1110two I imagine it’s less well known that you can do the same thing with floating point numbers. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[5,9],"tags":[271],"class_list":["post-247449","post","type-post","status-publish","format-standard","hentry","category-computing","category-math","tag-number-systems"],"acf":[],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"Printing floating point numbers in binary","description":"Python has no method to show floating point numbers in binary, but it does have a method for showing them in hex. How to make the former out of the latter.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/float-binary\/","robots":"max-image-preview:large","keywords":"number systems","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Printing floating point numbers in binary","og:description":"Python has no method to show floating point numbers in binary, but it does have a method for showing them in hex. How to make the former out of the latter.","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/float-binary\/","article:published_time":"2026-07-27T15:34:05+00:00","article:modified_time":"2026-07-27T20:35:18+00:00","twitter:card":"summary","twitter:title":"Printing floating point numbers in binary","twitter:description":"Python has no method to show floating point numbers in binary, but it does have a method for showing them in hex. How to make the former out of the latter.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247449","title":null,"description":"Python has no method to show floating point numbers in binary, but it does have a method for showing them in hex. How to make the former out of the latter.","keywords":null,"keyphrases":{"focus":{"keyphrase":"","score":0,"analysis":{"keyphraseInTitle":{"score":0,"maxScore":9,"error":1}}},"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":"","og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":"default","schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":"-1","robots_max_videopreview":"-1","robots_max_imagepreview":"large","priority":null,"frequency":"default","location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"created":"2026-07-27 00:05:27","updated":"2026-07-27 20:35:18","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":"
\n\t\t\tHome<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tComputing<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tPrinting floating point numbers in binary\n\t\t<\/span><\/div>","aioseo_breadcrumb_json":[{"label":"Home","link":"https:\/\/www.johndcook.com\/blog"},{"label":"Computing","link":"https:\/\/www.johndcook.com\/blog\/category\/computing\/"},{"label":"Printing floating point numbers in binary","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/27\/float-binary\/"}],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247449","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=247449"}],"version-history":[{"count":7,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247449\/revisions"}],"predecessor-version":[{"id":247463,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247449\/revisions\/247463"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=247449"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=247449"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=247449"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":247440,"date":"2026-07-26T15:32:02","date_gmt":"2026-07-26T20:32:02","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=247440"},"modified":"2026-07-27T10:45:23","modified_gmt":"2026-07-27T15:45:23","slug":"permutation-roots","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/permutation-roots\/","title":{"rendered":"Permutation roots"},"content":{"rendered":"
Let \u03c3 be a permutation on n<\/em> elements. If there is a permutation \u03c4 such that applying \u03c4 twice has the same effect on the list of elements as applying \u03c3 once, we say \u03c3 = \u03c4\u00b2 and \u03c4 is a square root of \u03c3.<\/p>\n
If we let our n<\/em> elements be the integers 0 through n<\/em> \u2212 1, then we can represent permutations by what they do to this list of numbers. In Python as a tuple of length n<\/em> and compose permutations with the following function:<\/p>\n
import itertools\r\n\r\ndef compose(sigma, tau):\r\n    \"Return the composition \u03c3 \u2218 \u03c4 (apply \u03c4 first, then \u03c3).\"\r\n    return tuple(sigma[j] for j in tau)\r\n<\/pre>\n
We can always construct permutations that have square roots by squaring a permutation. If we run the following code<\/p>\n
tau = (3, 1, 4, 5, 2, 0)\r\nsigma = compose(tau, tau)\r\n<\/pre>\n
we find \u03c3 = (5, 1, 2, 0, 4, 3), and by construction (3, 1, 4, 5, 2, 0) is a square root of &sigma, though it’s not the only one.<\/p>\n
The following code shows that \u03c3 has four roots.<\/p>\n
import itertools\r\n\r\ndef numroots(sigma):\r\n    n = len(sigma)\r\n    c = 0\r\n    for tau in itertools.permutations(range(n)):\r\n        if sigma == compose(tau, tau):\r\n            c += 1\r\n    return c\r\n\r\nprint( numroots(sigma) )\r\nprint( numroots( (1, 2, 3, 4, 5, 0) ) )\r\n<\/pre>\n
It also shows that the rotation (1, 2, 3, 4, 5. 0) has no roots.<\/p>\n
The function numroots<\/code> has runtime proportional to n<\/em>! and so it’s not practical for large permutations. There is a theorem that says a permutation \u03c3 has a square root if and only if the number of cycles it has of every even length is even. See [1].<\/p>\n
We can also define cubes and cube roots of permutations, and higher powers and roots.<\/p>\n
How common is it for permutations to have square roots, or cube roots, etc.? If you pick a random permutation on n<\/em> elements, what is the probability that it has a k<\/em>th root?<\/p>\n
This is a hard question in general, but it is equivalent to finding the coefficient of x<\/em>k<\/em><\/sup> in the infinite product<\/p>\n
\"\\prod_{m=1}^\\infty<\/p>\n
This is theorem 4.8.3 in [1]. This theorem was the motivation for writing about expq<\/em><\/sub> in the previous post<\/a>.<\/p>\n
Although the product is infinite, there’s no need to compute terms in the product that only contribute powers of x<\/em> higher than you’re interested in. The following Mathematica code will compute the probability that a permutation on n<\/em> elements has a k<\/em>th root.<\/p>\n
expq[x_, q_] := MittagLefflerE[q, x^q]\t \r\np[n_, k_] :=  SeriesCoefficient[\t \r\n    Product[expq[x^m\/m, GCD[m, k]], {m, 1, n}], {x, 0, n}]\r\n<\/pre>\n
So, for example, the probability that a permutation of 10 elements has a square root is 29\/96.<\/p>\n
[1] Herbert Wilf. Generatingfunctionology. Available online here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Let \u03c3 be a permutation on n elements. If there is a permutation \u03c4 such that applying \u03c4 twice has the same effect on the list of elements as applying \u03c3 once, we say \u03c3 = \u03c4\u00b2 and \u03c4 is a square root of \u03c3. If we let our n elements be the integers 0 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-247440","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"acf":[],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"Permutation roots","description":"Let \u03c3 be a permutation on n elements. If there is a permutation \u03c4 such that applying \u03c4 twice has the same effect on the list of elements as applying \u03c3 once, we say \u03c3 = \u03c4\u00b2 and \u03c4 is a square root of \u03c3. If we let our n elements be the integers 0","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/permutation-roots\/","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Permutation roots","og:description":"Let \u03c3 be a permutation on n elements. If there is a permutation \u03c4 such that applying \u03c4 twice has the same effect on the list of elements as applying \u03c3 once, we say \u03c3 = \u03c4\u00b2 and \u03c4 is a square root of \u03c3. If we let our n elements be the integers 0","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/permutation-roots\/","article:published_time":"2026-07-26T20:32:02+00:00","article:modified_time":"2026-07-27T15:45:23+00:00","twitter:card":"summary","twitter:title":"Permutation roots","twitter:description":"Let \u03c3 be a permutation on n elements. If there is a permutation \u03c4 such that applying \u03c4 twice has the same effect on the list of elements as applying \u03c3 once, we say \u03c3 = \u03c4\u00b2 and \u03c4 is a square root of \u03c3. If we let our n elements be the integers 0","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247440","title":null,"description":null,"keywords":null,"keyphrases":{"focus":{"keyphrase":"","score":0,"analysis":{"keyphraseInTitle":{"score":0,"maxScore":9,"error":1}}},"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":"","og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":"default","schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":"-1","robots_max_videopreview":"-1","robots_max_imagepreview":"large","priority":null,"frequency":"default","location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"created":"2026-07-26 19:13:37","updated":"2026-07-27 15:45:23","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":"
\n\t\t\tHome<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tUncategorized<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tPermutation roots\n\t\t<\/span><\/div>","aioseo_breadcrumb_json":[{"label":"Home","link":"https:\/\/www.johndcook.com\/blog"},{"label":"Uncategorized","link":"https:\/\/www.johndcook.com\/blog\/category\/uncategorized\/"},{"label":"Permutation roots","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/permutation-roots\/"}],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247440","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=247440"}],"version-history":[{"count":8,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247440\/revisions"}],"predecessor-version":[{"id":247459,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247440\/revisions\/247459"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=247440"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=247440"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=247440"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":247432,"date":"2026-07-26T13:20:36","date_gmt":"2026-07-26T18:20:36","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=247432"},"modified":"2026-07-26T15:32:54","modified_gmt":"2026-07-26T20:32:54","slug":"exp-q","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/exp-q\/","title":{"rendered":"exp_q"},"content":{"rendered":"
The function expq<\/em><\/sub>(x<\/em>) is defined by taking the power series for exp(x<\/em>) and keeping only the terms whose index is a multiple of q<\/em>. For example, exp2<\/sub>(x<\/em>) keeps only the even-numbered terms in the exponential power series and so equals cosh(x<\/em>).<\/p>\n
\"\\exp_2(x)<\/p>\n
In general,<\/p>\n
\"\\exp_q(x)<\/p>\n
The first sum uses Iverson’s bracket notation<\/a>: a Boolean expression in brackets denotes the function that returns 1 when the expression is true and zero when it is false. Here the bracket equals 1 when q<\/em> divides n<\/em> and is zero otherwise.<\/p>\n
Closed forms<\/h2>\n
Let \u03c9 = exp(2\u03c0i<\/em> \/ q<\/em>). Then<\/p>\n
\"\\exp_q(x)<\/p>\n
This lets us find closed-form expressions for expq<\/em><\/sub>(x<\/em>). For example, when q<\/em> = 4, \u03c9 = i<\/em> and<\/p>\n
\"\\exp_4(x)<\/p>\n
Here’s a proof of the identity above:<\/p>\n
\"\\begin{align*}<\/p>\n
In the proof we used the identity<\/p>\n
\"\\frac{1}{q}<\/p>\n
which is important in deriving the properties of the discrete Fourier transform.<\/p>\n
Differential equations<\/h2>\n
The first time I saw the function expq<\/em><\/sub>(x<\/em>) was in differential equations, though I didn’t know at the time the function had a name.<\/p>\n
When a course in differential equations gets to power series solutions, a common example or homework problem is to solve<\/p>\n
\"y^{(k)}(x)<\/p>\n
for k<\/em> = 3 or 4, i.e. to find a function that equals its third or fourth derivative.<\/p>\n
If the initial conditions are<\/p>\n
\"y(0)<\/p>\n
and<\/p>\n
\"y^\\prime(0)<\/p>\n
the unique solution to<\/p>\n
\"y^{(k)}(x)<\/p>\n
is y<\/em>(x<\/em>) = expk<\/em><\/sub>(x<\/em>).<\/p>\n
Mathematica and Mittag-Leffler<\/h2>\n
Mathematica does not have a built-in function implementing expq<\/em><\/sub>(x<\/em>), but it does have an implementation of the Mittag-Leffler function<\/a>, and so thanks to a relation between this function and expq<\/em><\/sub>(x<\/em>) you can implement the latter as<\/p>\n
expq[x_, q_] := MittagLefflerE[q, x^q]<\/pre>\n
Combinatorics<\/h2>\n
The first time I saw the notation<\/em> expq<\/em><\/sub>(x<\/em>) was in combinatorics. I had intended to include an application from that book here, but I make that the topic for the next post<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
The function expq(x) is defined by taking the power series for exp(x) and keeping only the terms whose index is a multiple of q. For example, exp2(x) keeps only the even-numbered terms in the exponential power series and so equals cosh(x). In general, The first sum uses Iverson’s bracket notation: a Boolean expression in brackets […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[47,129],"class_list":["post-247432","post","type-post","status-publish","format-standard","hentry","category-math","tag-differential-equations","tag-special-functions"],"acf":[],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"exp_q(x) keeps every qth term in the power series for exp(x)","description":"The function exp_q(x) is a generalization of the exponential function. It comes up in numerous applications, such as differential equations and combinatorics.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/exp-q\/","robots":"max-image-preview:large","keywords":"differential equations,special functions","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"exp_q(x) keeps every qth term in the power series for exp(x)","og:description":"The function exp_q(x) is a generalization of the exponential function. It comes up in numerous applications, such as differential equations and combinatorics.","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/exp-q\/","article:published_time":"2026-07-26T18:20:36+00:00","article:modified_time":"2026-07-26T20:32:54+00:00","twitter:card":"summary","twitter:title":"exp_q(x) keeps every qth term in the power series for exp(x)","twitter:description":"The function exp_q(x) is a generalization of the exponential function. It comes up in numerous applications, such as differential equations and combinatorics.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247432","title":"exp_q(x) keeps every qth term in the power series for exp(x)","description":"The function exp_q(x) is a generalization of the exponential function. It comes up in numerous applications, such as differential equations and combinatorics.","keywords":null,"keyphrases":{"focus":{"keyphrase":"","score":0,"analysis":{"keyphraseInTitle":{"score":0,"maxScore":9,"error":1}}},"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":"","og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":"default","schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":"-1","robots_max_videopreview":"-1","robots_max_imagepreview":"large","priority":null,"frequency":"default","location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"created":"2026-07-26 16:38:25","updated":"2026-07-26 20:32:54","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":"
\n\t\t\tHome<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tMath<\/a>\n\t\t<\/span>»<\/span>\n\t\t\texp_q\n\t\t<\/span><\/div>","aioseo_breadcrumb_json":[{"label":"Home","link":"https:\/\/www.johndcook.com\/blog"},{"label":"Math","link":"https:\/\/www.johndcook.com\/blog\/category\/math\/"},{"label":"exp_q","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/26\/exp-q\/"}],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247432","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=247432"}],"version-history":[{"count":9,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247432\/revisions"}],"predecessor-version":[{"id":247446,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247432\/revisions\/247446"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=247432"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=247432"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=247432"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":247423,"date":"2026-07-25T08:37:30","date_gmt":"2026-07-25T13:37:30","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=247423"},"modified":"2026-07-26T08:05:57","modified_gmt":"2026-07-26T13:05:57","slug":"excel-column-numbering","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/07\/25\/excel-column-numbering\/","title":{"rendered":"Excel column numbering"},"content":{"rendered":"
I was working with a wide spreadsheet from a client the other day and I had to convert between Excel column labels and column numbers. I had never paid attention to how Excel labels columns and implicitly thought it was base 26 using letters rather than digits. But then I realized that’s not right.<\/p>\n
Excel labels columns A through Z, then AA through AZ, then BA through BZ, etc. If this is base 26, then does A correspond to 0? That could work for A through Z, but then what about AA? Then you’d have to say the first A corresponds to 26 but the second A corresponds to 0.<\/p>\n
Does Z correspond to 0? If so then the column numbers would be 1 through 25, followed by 0, then 27. And it would mean that columns ZA through ZZ are the same as A through Z.<\/p>\n
In fact nothing in Excel column labeling corresponds to 0. The labels cannot be interpreted as a positional number system.<\/p>\n
There’s a name for this kind of number system: bijective base 26<\/strong>. The concept extends generally to bijective base\u00a0b<\/em> for any positive integer\u00a0b<\/em>. The idea is ancient, but the name was coined recently. It has also been called k<\/em>-adic numbering. For most of history it didn’t have a name.<\/p>\n
The motivation behind the name bijective base\u00a0b<\/em> is that there is a bijection (a one-to-one correspondence) between these symbols and positive integers; there’s no possibility of leading zeros that would keep the mapping from being a bijection, unlike say 7 and 07 representing the same number.<\/p>\n
Excel limits<\/h2>\n
Before 2007, an Excel file could have a maximum of 28<\/sup> = 256 columns, and so the largest column label was IV.<\/p>\n
Then in 2007 the column limit was increased to 214<\/sup> = 16,384 and the largest column label is XFD.<\/p>\n
Conversion code<\/h2>\n
Converting from column labels to integers is easy; going the other way is a little more complicated.<\/p>\n
letter_to_ordinal = lambda c: ord(c) - ord('A') + 1\r\nordinal_to_letter = lambda n: chr(ord('A') + n - 1)\r\n\r\ndef label_to_num(label):\r\n    label = label.upper()\r\n    n = 0\r\n    for c in label:\r\n        n = n*26 + letter_to_ordinal(c)\r\n    return n\r\n\r\ndef num_to_label(n):\r\n    letters = []\r\n    while n > 0:\r\n        n, remainder = divmod(n - 1, 26)\r\n        letters.append(ordinal_to_letter(remainder + 1))\r\n    return ''.join(reversed(letters))\r\n<\/pre>\n
Here’s an online calculator<\/a> based on the code above.<\/p>\n
Tests<\/h2>\n
The following code verifies the assertions above about the maximum number of Excel columns over time.<\/p>\n
assert(num_to_label(256) == \"IV\")\r\nassert(label_to_num(\"IV\") == 256)\r\n\r\nassert(num_to_label(2**14) == \"XFD\")\r\nassert(label_to_num(\"XFD\") == 2**14)\r\n<\/pre>\n
The conversion routines are not limited to actual Excel labels but work for arbitrarily large integers and bijective base 26 representations. For example, the following code shows that the bijective base 26 representation of Avogadro’s number is MUAEKAUDYDXEWOSDD.<\/p>\n
avogadro = 602_214_076_000_000_000_000_000\r\nassert(label_to_num(num_to_label(avogadro)) == avogadro)\r\nprint(num_to_label(avogadro))\r\n<\/pre>\n
Related posts<\/h2>\n