{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigkz6pun7u2wqyfftvqfgwnxhg37t2euw74nsv3g2qtd6bx6nf3rm",
    "uri": "at://did:plc:qv6izabdl4q4cxzbrdypib2x/app.bsky.feed.post/3meqmhqvynsn2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreid5uboq5c22xy7wj74fic455zpnddxyefgfxcs6jf4hliet5owt5y"
    },
    "mimeType": "image/png",
    "size": 4093
  },
  "path": "/2026/02/11/sums-of-the-choose-function-and-the-binomial-formula",
  "publishedAt": "2026-02-10T23:00:00.000Z",
  "site": "https://thomashodson.com",
  "tags": [
    "binomial formula"
  ],
  "textContent": "\n\n\n\nHere’s a nice maths thing. I was thinking about this game called Kniffel, which is a German game played with 5 dice. The internet says it has similar rules to Yahtzee though both seem to have many variants.\n\nThe aspect that is important here is that you roll your 5 dice and then you may choose to re-roll any subset of them (up to twice). You choose which subset to re-roll in order to maximise your chances of achieving certain goals, like getting 5 of the same value (and shouting Kniffel!) or a consecutive run etc.\n\nI was thinking about how one might compute the optimum choice of subset to re-roll given a starting point. Let’s say you were going to just brute force it. How hard would that be?\n\nWell you have 5 dice and you want to choose a good subset to roll, there are $2^5 = 32$ possible subsets. How many of each subset are there? That’s actually easy, it’s the choose function:\n\n\\\\[{n \\choose r} = \\frac{n!}{r! \\; (n - r)!}\\\\]\n\nwhich tells you how many ways there are to choose a subset of size r from a set of size n if you don’t care how it’s ordered.\n\nLet’s quickly look at how many choices there are if we choose to re-roll $r$ dice:\n\n\n    def fact(n): return n*fact(n-1) if n != 0 else 1\n    def ncr(n, r): return fact(n) // (fact(r) * fact(n - r))\n\n    for r in range(6):\n        print(f\"{r = }, ncr(5,{r}) = {ncr(5,r)}\")\n\n\n\n    r = 0, ncr(5,0) = 1\n    r = 1, ncr(5,1) = 5\n    r = 2, ncr(5,2) = 10\n    r = 3, ncr(5,3) = 10\n    r = 4, ncr(5,4) = 5\n    r = 5, ncr(5,5) = 1\n\n\nThat checks out, there’s only one way to choose all or none of the dice, are there are more ways when you choose about half of them.\n\nThis is actually the origin of that nice identity about rows in Pascals triangle adding to powers of 2:\n\n\\\\[2^5 = 32 = {5 \\choose 0} + {5 \\choose 1} + {5 \\choose 2} + {5 \\choose 3} + {5 \\choose 4} + {5 \\choose 5} =\\\\] \\\\[= 1 + 5 + 10 + 10 + 5 + 1\\\\]\n\nWhat I want to know though, is how many outcomes do we need to consider? Because for each of those ways of choosing $r$ dice, we will have to evaluate every possible outcome of rolling those $r$ dice. Since a die has 6 values there are $6^r$ possible outcomes.\n\nIf we loop over every subset of size $r$ and perform $6^r$ computations, how big is that number? It’s:\n\n\\\\[N = \\sum_{r = 0}^5 {5 \\choose r} 6^r\\\\]\n\nThis is the bit that surprised me, it turns out we can evaluate that sum in closed form! I’ve hidden the answer below just in case you want to try yourself.\n\nHint\n\nRecall or look up the binomial formula.\n\nAnswer\n\nBy noticing that it looks a bit like the binomial formula:\n\n\\\\[(p + q)^m = \\sum_{r = 0}^m {m \\choose r} p^r q^{m-r}\\\\]\n\nBy setting $m=5, p=6, q=1$ we get:\n\n\\\\[\\sum_{r = 0}^5 {5 \\choose r} 6^r = (6 + 1)^5 = 16807\\\\]\n\nWe can check this number quickly with some python, `itertools` has a handy function `it.product((0,1), repeat = 5)` that will give us all 32 possible subsets in the form `(1,1,0,0,0)` where a 1 means ‘roll that die’.\n\nWith that representation, `sum(subset)` is how many dice we have to roll and `6 ** sum(subset)` is how many outcomes we have to consider.\n\n\n    import itertools as it\n    sum(6 ** sum(subset) for subset in it.product((0,1), repeat = 5))\n\n\n\n    16807\n\n\nYay!\n\n\n    7**5\n\n\n\n    16807\n",
  "title": "Sums of the choose function and the Binomial Formula"
}