Let t<\/em>(n<\/em>) be the number of distinct unlabeled rooted trees with n<\/em> nodes. The diagram below shows that the first few terms of this sequence are 1, 1, 2, and 4.<\/p>\n In an earlier post<\/a> I showed that designing a 4-stage explicit Runge-Kutta method required solving a system of 8 equations in 10 unknowns, leaving two degrees of freedom in the solutions.<\/p>\n The number of constraints c<\/em>(s<\/em>) needed to design an s<\/em>-stage explicit RK method is equal to the number of rooted trees with up to s<\/em> nodes:<\/p>\n c<\/em>(s<\/em>) = t<\/em>(1) + t<\/em>(2) + t<\/em>(3) + \u2026 + t<\/em>(s<\/em>)<\/p>\n This is because there is a one-to-one correspondence between constrains on the\u00a0n<\/em>th derivative of an RK formula and rooted trees, and an\u00a0s<\/em> stage method has to satisfy the constraints of all stages up to\u00a0s<\/em>. In the example of the 4th order RK method, we have<\/p>\n c<\/em>(4) =\u00a0t<\/em>(1) +\u00a0t<\/em>(2)\u00a0 +\u00a0t<\/em>(3) +\u00a0t<\/em>(4) = 1 + 1 + 2 + 4 = 8.<\/p>\n The first few values [2] of t<\/em>(n<\/em>) are<\/p>\n 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, \u2026<\/p>\n and so you can see that\u00a0t<\/em>(n<\/em>) grows quickly. In fact, it grows exponentially [3].<\/p>\n However, the number of parameters in an\u00a0s<\/em> stage RK method is\u00a0s<\/em>(s<\/em> + 1)\/2. The number of equations grows exponentially and the number of variables grows only quadratically, so at some point you have more equations than variables. That’s already the case for s<\/em> = 5 because you have 17 constraints on 15 variables.\u00a0The system has a solution because symmetry considerations render some of the equations redundant.<\/p>\n A 10th order RK method requires 17 stages. (See the previous post<\/a> for why the number of stages exceeds the order when the order is greater than 4.) Designing such a method would require solving over a million equations in 153 variables, and yet it can be done. [4]<\/p>\n [1] This is a slightly contradictory term. Unlabeled means the we don’t distinguish the nodes. But we do distinguish one node, namely the root.<\/p>\n [2] See OEIS A000081<\/a>.<\/p>\n [2] Richard Otter proved in 1948 that the number of unlabeled rooted trees with\u00a0n<\/em> nodes is asymptotically C<\/em> \u03b1n<\/em><\/sup> \/ n<\/em>\u22123\/2<\/sup> where\u00a0C<\/em> = 0.4399\u2026 and \u03b1 = 2.9557\u2026. The cumulative sum is at least this large since Otter’s estimate gives the size of the last term in the sum.<\/p>\n [3] E. Hairer. A Runge-Kutta Method of Order 10. J. Inst. Maths Applics (1978) 21, 47-59<\/p>\n","protected":false},"excerpt":{"rendered":" Combinatorial problems can be interesting for their own sake, but they are more interesting when there is a connection to a problem outside combinatorics, and the more unexpected the connection the better. Counting the number of unlabeled rooted trees [1] with n nodes is a pure mathematics problem. Designing numerical methods for solving differential equations […]<\/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,47],"class_list":["post-247502","post","type-post","status-publish","format-standard","hentry","category-math","tag-combinatorics","tag-differential-equations"],"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 rooted trees","description":"The pure math problem of counting rooted trees is closely connected with the applied math problem of designing differential equation solvers.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/08\/01\/counting-rooted-trees\/","robots":"max-image-preview:large","keywords":"combinatorics,differential equations","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Counting rooted trees","og:description":"The pure math problem of counting rooted trees is closely connected with the applied math problem of designing differential equation solvers.","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/08\/01\/counting-rooted-trees\/","article:published_time":"2026-08-01T16:15:53+00:00","article:modified_time":"2026-08-01T16:17:13+00:00","twitter:card":"summary","twitter:title":"Counting rooted trees","twitter:description":"The pure math problem of counting rooted trees is closely connected with the applied math problem of designing differential equation solvers.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247502","title":null,"description":"The pure math problem of counting rooted trees is closely connected with the applied math problem of designing differential equation solvers.","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-08-01 14:08:24","updated":"2026-08-01 17:23:59","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":" The textbook version of the Runge-Kutta method for solving differential equations has 4 stages and has 4th order error. For lower order versions of RK the number of stages s<\/em> also matches the order of the error p<\/em>. But in order to achieve error on the order of\u00a0p<\/em> \u2265 5, you need more than p<\/em> stages. This is known as the Butcher barrier.<\/p>\n Before going any further, let’s back up and say what we mean by stages and by order.<\/p>\n The number of stages in an RK method to solve the equation<\/p>\n is the number of evaluations of the function\u00a0f<\/em> on the right-hand side. For example, the textbook RK4 method estimates the solution at each step by<\/p>\n where<\/p>\n which requires four stages, i.e. four evaluations of\u00a0f<\/em>.<\/p>\n A differential equation solver is said to have order p<\/em> if the local error, the error after one step of size h<\/em>, is O<\/em>(h<\/em>p<\/em> + 1<\/sup>). Then after solving an ODE over a period of time T<\/em> with N<\/em> = T<\/em>\/h<\/em> steps, the global error is O<\/em>(h<\/em>p<\/em><\/sup>). So, for example, if p<\/em> = 4, you would expect that cutting your step size h<\/em> in half would cut your error at T<\/em> by a factor of 16.<\/p>\n John C. Butcher proved that an explicit RK method of order p<\/em> requires\u00a0s<\/em> stages where\u00a0s<\/em> >\u00a0p<\/em> if\u00a0p<\/em> > 4.<\/p>\n An important example is the Dormand-Prince method. It is a version of RK that has order 5 and 7 stages. The clever thing about this method is that you can make a 4th order solver out of a subset of its function evaluations.<\/p>\n That means that after you’ve evaluated one step of the 5th order method, you can also evaluate a 4th order method essentially for free. And by comparing them, you can get a sense of the error. If the solutions given by the two methods are substantially different, you have probably taken too big a step and need to back up. If the two solutions essentially agree, you’re probably good to take the next step.<\/p>\n For an explict RK method to have order 5, 6, or 7 you need at least 6, 7, or 9 stages respectively.<\/p>\n","protected":false},"excerpt":{"rendered":" The textbook version of the Runge-Kutta method for solving differential equations has 4 stages and has 4th order error. For lower order versions of RK the number of stages s also matches the order of the error p. But in order to achieve error on the order of\u00a0p \u2265 5, you need more than p […]<\/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],"class_list":["post-247499","post","type-post","status-publish","format-standard","hentry","category-math","tag-differential-equations"],"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":"Runge-Kutta: over versus stages | Butcher barrier","description":"A Runge-Kutta method of order n has n stages only for n = 1, 2, 3, and 4. After that, the number of stages must exceed the order.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/08\/01\/butcher-barrier\/","robots":"max-image-preview:large","keywords":"differential equations","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Runge-Kutta: over versus stages | Butcher barrier","og:description":"A Runge-Kutta method of order n has n stages only for n = 1, 2, 3, and 4. After that, the number of stages must exceed the order.","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/08\/01\/butcher-barrier\/","article:published_time":"2026-08-01T15:58:15+00:00","article:modified_time":"2026-08-01T15:58:15+00:00","twitter:card":"summary","twitter:title":"Runge-Kutta: over versus stages | Butcher barrier","twitter:description":"A Runge-Kutta method of order n has n stages only for n = 1, 2, 3, and 4. After that, the number of stages must exceed the order.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247499","title":"Runge-Kutta: over versus stages | Butcher barrier","description":"A Runge-Kutta method of order n has n stages only for n = 1, 2, 3, and 4. After that, the number of stages must exceed the order.","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-08-01 11:53:29","updated":"2026-08-01 16:00:00","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":" I was digging into the Runge-Kutta method for solving differential equations and a line from [1] piqued my curiosity.<\/p>\n These calculations, which are not reproduced in Kutta’s paper (they are however in Huen (1900)), are very tedious.<\/p>\n The calculations are a set of eight constraints that the parameters of a fourth-order Runge-Kutta method must satisfy. I wondered how well Mathematica might have done at assisting Mr. Huen in his “very tedious” calculations if it had been available in 1900.<\/p>\n I go into Runge-Kutta methods in this post<\/a>. Here I’d like to concentrate on a step in the design of the methods, namely solving the set of equations alluded in the quote above.<\/p>\n The first thing to note is that there are 10 variables and only 8 equations, and so the solution is not fully determined. What we think of as\u00a0the<\/em> fourth order Runge-Kutta method is in fact\u00a0a<\/em> fourth order Runge-Kutta method.<\/p>\n One could argue that we should have b<\/em>2<\/sub> = b<\/em>3<\/sub> and c<\/em>2<\/sub> = c<\/em>3<\/sub>. With these additional equations, the system of equations has a unique solution, and Mathematic finds it easily.<\/p>\n This returns the parameters used for the version of Runge-Kutta presented in every textbook.<\/p>\n If you keep the requirement b<\/em>2<\/sub> = b<\/em>3<\/sub> but substitute the requirement 2c<\/em>2<\/sub> = c<\/em>3<\/sub> for c<\/em>‘s Mathematica will return the coefficients for the so-called Runge-Kutta 3\/8 rule. This method has some slight advantages by some criteria.<\/p>\n In 1951 Gill [2] discovered a fourth order Runge-Kutta rule optimized for running in extremely constrained computer hardware. It’s a strange method, with irrational parameters, but one that was a very clever response to the limitations of its time.<\/p>\n [1] Hairer, N\u00f8rsett, and Wanner. Solving Ordinary Differential Equations I: Nonstiff Problems. Springer-Verlag 1987.<\/p>\n [2] A. Gill. A process for the step-by-step integration of differential equations in an automatic digital computing machine. Proc. Cambridge Philos. Soc., vol 27, pp 95\u2013108.<\/p>\n","protected":false},"excerpt":{"rendered":" I was digging into the Runge-Kutta method for solving differential equations and a line from [1] piqued my curiosity. These calculations, which are not reproduced in Kutta’s paper (they are however in Huen (1900)), are very tedious. The calculations are a set of eight constraints that the parameters of a fourth-order Runge-Kutta method must satisfy. […]<\/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,87],"class_list":["post-247492","post","type-post","status-publish","format-standard","hentry","category-math","tag-differential-equations","tag-mathematica"],"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":"Solving the fourth order Runge-Kutta design equations","description":"The constraints on Runge-Kutta method parameters are complicated. How well could Mathematica do at solving them?","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/31\/runge-kutta-design\/","robots":"max-image-preview:large","keywords":"differential equations,mathematica","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Solving the fourth order Runge-Kutta design equations","og:description":"The constraints on Runge-Kutta method parameters are complicated. How well could Mathematica do at solving them?","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/31\/runge-kutta-design\/","article:published_time":"2026-07-31T18:59:02+00:00","article:modified_time":"2026-08-01T06:29:19+00:00","twitter:card":"summary","twitter:title":"Solving the fourth order Runge-Kutta design equations","twitter:description":"The constraints on Runge-Kutta method parameters are complicated. How well could Mathematica do at solving them?","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247492","title":"Solving the fourth order Runge-Kutta design equations","description":"The constraints on Runge-Kutta method parameters are complicated. How well could Mathematica do at solving them?","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-31 17:38:42","updated":"2026-08-01 06:30:02","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":" A couple years ago<\/a> I wrote about how to compute the inverse of factorial. I used that code in writing the previous post because the post required solving the equation<\/p>\n \u230alog2<\/sub>(n<\/em>!)\u230b \u2265 b<\/em><\/p>\n given b<\/em>. That is, given a number of bits b<\/em>, find the smallest value of n<\/em>\u00a0such that n<\/em>! \u2265 2b<\/em><\/sup>.<\/p>\n Looking back on the code in that post, there are a few changes I’d like to make. But first of all, I’d like to point out something the post does right: instead of trying to solve<\/p>\n \u0393(y<\/em>) = x<\/em><\/p>\n it solves<\/p>\n log \u0393(y<\/em>) = log x<\/em>.<\/p>\n That’s why the argument to The function The code in the previous post uses the bisection method. This method is very safe, and fast enough for my purposes, but it could be made faster. Newton’s method is faster, but it can be ill-behaved if you don’t start close enough to the solution.<\/p>\n It’s safe to use Newton’s method to invert log \u0393 for two reasons. First, you can get a good starting point based on Stirling’s approximation. Second, and more importantly, log \u0393 is convex. Newton’s method will converge from\u00a0any<\/em> starting point when applied to a convex function. A little caution is necessary because log \u0393 is not convex everywhere, but it is convex on the positive real axis.<\/p>\n Another difficulty with Newton’s method is that you need to supply the derivative of the function whose root you’re trying to find. But this isn’t an issue here because the derivative of log \u0393 is the digamma function, which is implemented in SciPy.<\/p>\n Finally, the previous code used the default tolerance for deciding when to stop refining the solution. The revised method lets the user specify tolerance. It provides a default value, but that default is visible in the function call, not hidden down in SciPy.<\/p>\n Here’s the revised code.<\/p>\n A couple years ago I wrote about how to compute the inverse of factorial. I used that code in writing the previous post because the post required solving the equation \u230alog2(n!)\u230b \u2265 b given b. That is, given a number of bits b, find the smallest value of n\u00a0such that n! \u2265 2b. What the […]<\/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":[129],"class_list":["post-247470","post","type-post","status-publish","format-standard","hentry","category-math","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":"Efficient code for inverting the (log) gamma function","description":"Improved code for solving x! = y or more generally \u0393(x) = y for x.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/28\/inverse-factorial-improved\/","robots":"max-image-preview:large","keywords":"special functions","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Efficient code for inverting the (log) gamma function","og:description":"Improved code for solving x! = y or more generally \u0393(x) = y for x.","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/28\/inverse-factorial-improved\/","article:published_time":"2026-07-28T14:11:30+00:00","article:modified_time":"2026-07-28T18:39:02+00:00","twitter:card":"summary","twitter:title":"Efficient code for inverting the (log) gamma function","twitter:description":"Improved code for solving x! = y or more generally \u0393(x) = y for x.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247470","title":"Efficient code for inverting the (log) gamma function","description":"Improved code for solving x! = y or more generally \u0393(x) = y for x.","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-28 13:38:46","updated":"2026-07-29 04:51:41","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":" The previous post<\/a> looked at the idea of storing a cryptographic key in the order of a deck of cards. A deck of 52 cards can store 225 bits of data because<\/p>\n \u230alog2<\/sub>(52!)\u230b = 225.<\/p>\n Here \u230ax<\/em>\u230b is\u00a0x<\/em> rounded down to the nearest integer.<\/p>\n If we want to store bigger keys, we’re going to need a bigger deck of cards.<\/p>\n A Bitcoin key has 256 bits, which would require a deck of 58 cards. There is a card game called Zwicker that uses a deck of 58 cards, the usual 52 cards plus six jokers. So you could store a Bitcoin key in the permutation of a Zwicker deck.<\/p>\n You could also use a deck of 52 cards, plus 2 jokers, if you also consider orientation. 30 cards are rotationally symmetric, 22 are not, and neither are jokers. So, including two asymmetric jokers, you could add 24 additional bits. Permutations of a 54 card deck can encode 237 bits, and with 24 orientation bits, this is a total of 261 bits.<\/p>\n RSA key sizes vary, but 2048 and 3072 are common. A 2048-bit key would require a deck of 301 cards. Casinos often use a shoe of 312 cards, combining six decks of 52 cards, to deal Baccarat or Blackjack. However, casinos combine identical decks. If you were to combine six unique decks, you could store a 2048-bit key.<\/p>\n Storing a 3072-bit key would require a deck of 422 cards. You could make a deck of 432 cards by combining 8 distinguishable packs of 54 cards (52 + 2 jokers).<\/p>\n ML-KEM is a proposed quantum-resistant replacement for RSA. As with RSA, key sizes for ML-KEM vary, the smallest being ML-KEM-512<\/strong> with a key size of 1632 bytes, which equals 13056 bits. This would require a deck of 1442 cards. You could combine 28 distinct packs of 52 cards, but that’s unwieldy.<\/p>\n This illustrates one of the difficult trade-offs with post-quantum cryptography: key sizes are much bigger. If you wanted to create a deck of 1442 cards, you’d probably want to make your “cards” something other than standard playing cards. You’d want to use permutations of something else.<\/p>\n The following Python code verifies the calculations above.<\/p>\n For more on how I came up with the deck sizes, see the next post<\/a> on computing the inverse factorial.<\/p>\n","protected":false},"excerpt":{"rendered":" The previous post looked at the idea of storing a cryptographic key in the order of a deck of cards. A deck of 52 cards can store 225 bits of data because \u230alog2(52!)\u230b = 225. Here \u230ax\u230b is\u00a0x rounded down to the nearest integer. If we want to store bigger keys, we’re going to need […]<\/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,43],"class_list":["post-247468","post","type-post","status-publish","format-standard","hentry","category-math","tag-combinatorics","tag-cryptography"],"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":"Cryptographic Keys and Decks of Cards","description":"You can store cryptographic keys in the order of a deck of cards. How big a deck would you need to store Bitcoin, RSA, or ML-KEM keys?","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/28\/keys-and-cards\/","robots":"max-image-preview:large","keywords":"combinatorics,cryptography","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Cryptographic Keys and Decks of Cards","og:description":"You can store cryptographic keys in the order of a deck of cards. How big a deck would you need to store Bitcoin, RSA, or ML-KEM keys?","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/07\/28\/keys-and-cards\/","article:published_time":"2026-07-28T12:13:17+00:00","article:modified_time":"2026-07-28T18:11:18+00:00","twitter:card":"summary","twitter:title":"Cryptographic Keys and Decks of Cards","twitter:description":"You can store cryptographic keys in the order of a deck of cards. How big a deck would you need to store Bitcoin, RSA, or ML-KEM keys?","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247468","title":null,"description":"You can store cryptographic keys in the order of a deck of cards. How big a deck would you need to store Bitcoin, RSA, or ML-KEM keys?","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-28 11:10:29","updated":"2026-07-29 04:51:41","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null},"aioseo_breadcrumb":"![](\"https:\/\/www.johndcook.com\/rooted_trees_order_1_to_4.svg\")
<\/p>\nRelated posts<\/h2>\n
\n
Stages<\/h2>\n
![\"y'](\"https:\/\/www.johndcook.com\/first_order_ode.svg\")
<\/p>\n![\"y_{n+1}](\"https:\/\/www.johndcook.com\/rk4.svg\")
<\/p>\n![\"k_{n1}](\"https:\/\/www.johndcook.com\/rk4k.svg\")
<\/p>\nOrder<\/h2>\n
More stages than the order<\/h2>\n
![\"\\begin{align*}](\"https:\/\/www.johndcook.com\/RK4.svg\")
<\/p>\neqs = {\r\n b1 + b2 + b3 + b4 == 1,\r\n b2*c2 + b3*c3 + b4*c4 == 1\/2,\r\n b2*c2^2 + b3*c3^2 + b4*c4^2 == 1\/3,\r\n b3*a32*c2 + b4*(a42*c2 + a43*c3) == 1\/6,\r\n b2*c2^3 + b3*c3^3 + b4*c4^3 == 1\/4,\r\n b3*c3*a32*c2 + b4*c4*(a42*c2 + a43*c3) == 1\/8,\r\n b3*a32*c2^2 + b4*(a42*c2^2 + a43*c3^2) == 1\/12,\r\n b4*a43*a32*c2 == 1\/24,\r\n b2 == b3,\r\n c2 == c3\r\n};\r\n\r\nvars = {b1, b2, b3, b4, c2, c3, c4, a32, a42, a43};\r\n\r\nsolution = Solve[eqs, vars]\r\n<\/pre>\nRelated posts<\/h2>\n
\n
What the code got right<\/h2>\n
inverse_log_gamma<\/code> is logarg<\/code>. That makes the code useful for values of\u00a0x<\/em> that would far exceed the maximum floating point value, such as in the calculations for the previous post.<\/p>\nWhat I’d change<\/h2>\n
Rounding<\/h3>\n
inverse_factorial<\/code> from the old post solves finds the closest integer solution. It would be better for it to return the solution without rounding and then let the user round result if they want to. In my calculations in the previous post, I wanted to take the floor, not round.<\/p>\nNewton’s method<\/h3>\n
Tolerance<\/h3>\n
Revised code<\/h2>\n
from scipy.special import gammaln, digamma\r\nfrom scipy.optimize import newton\r\n\r\ndef inverse_log_gamma(logarg, tol=1e-12):\r\n assert(logarg > 0) \r\n x0 = logarg \/ log(logarg + 1) + 1 if logarg > 1 else 2.0\r\n def f(z): return gammaln(z) - logarg\r\n return newton(f, x0, fprime=digamma, tol=tol)\r\n\r\ndef inverse_factorial(logarg):\r\n g = inverse_log_gamma(logarg)\r\n return g - 1 \r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Bitcoin<\/h2>\n
RSA<\/h2>\n
ML-KEM<\/h2>\n
Verification<\/h2>\n
from math import log2, factorial, floor\r\n\r\ndef capacity(cards):\r\n return floor(log2(factorial(cards)))\r\n\r\ndef verify(bits, cards):\r\n return capacity(cards) >= bits and capacity(cards-1) < bits\r\n\r\nprint(verify(237, 54))\r\nprint(verify(256, 58))\r\nprint(verify(2048, 301))\r\nprint(verify(3072, 422))\r\nprint(verify(1632*8, 1442))\r\n<\/pre>\n
![](\"https:\/\/www.johndcook.com\/shuffled_deck.png\")
<\/p>\n