{"history":[],"article":{"id":"2a1daa76-c203-479e-9ea0-64306d612c46","title":"Combinatorial number system","slug":"combinatorial-number-system","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), and in particular in [combinatorics](https://bliptext.com/articles/combinatorics), the **combinatorial number system** of degree k (for some positive [integer](https://bliptext.com/articles/integer) k), also referred to as **combinadics**, or the **Macaulay representation of an [integer](https://bliptext.com/articles/integer)**, is a correspondence between [natural numbers](https://bliptext.com/articles/natural-number) (taken to include 0) N and k-[combinations](https://bliptext.com/articles/combination).\nThe combinations are represented as [strictly decreasing](https://bliptext.com/articles/sequence) [sequences](https://bliptext.com/articles/integer-sequence) ck > ... > c2 > c1 ≥ 0 where each ci corresponds to the index of a chosen element in a given k-combination.\nDistinct numbers correspond to distinct k-combinations, and produce them in [lexicographic order](https://bliptext.com/articles/lexicographic-order).\nThe numbers less than \\tbinom nk correspond to all k-combinations of {0, 1, ..., n − 1}.\nThe correspondence does not depend on the size n of the set that the k-combinations are taken from, so it can be interpreted as a map from ****N**** to the k-combinations taken from ****N****; in this view the correspondence is a [bijection](https://bliptext.com/articles/bijective-map).\nThe number N corresponding to (ck, ..., c2, c1) is given by\nThe fact that a unique sequence corresponds to any non-negative number N was first observed by [D. H. Lehmer](https://bliptext.com/articles/derrick-henry-lehmer).\nIndeed, a [greedy algorithm](https://bliptext.com/articles/greedy-algorithm) finds the k-combination corresponding to N: take ck maximal with, then take ck−1 maximal with , and so forth.\nFinding the number N, using the formula above, from the k-combination (ck, ..., c2, c1) is also known as \"ranking\", and the opposite operation (given by the greedy algorithm) as \"unranking\"; the operations are known by these names in most [computer algebra systems](https://bliptext.com/articles/computer-algebra-system), and in [computational mathematics](https://bliptext.com/articles/computational-mathematics).\nThe originally used term \"combinatorial representation of integers\" was shortened to \"combinatorial number system\" by [Knuth](https://bliptext.com/articles/donald-ervin-knuth),\nwho also gives a much older reference;\nthe term \"combinadic\" is introduced by James McCaffrey (without reference to previous terminology or work).\nUnlike the [factorial number system](https://bliptext.com/articles/factorial-number-system), the combinatorial number system of degree k is not a [mixed radix](https://bliptext.com/articles/mixed-radix) system: the part of the number N represented by a \"digit\" ci is not obtained from it by simply multiplying by a place value.\nThe main application of the combinatorial number system is that it allows rapid computation of the k-combination that is at a given position in the lexicographic ordering, without having to explicitly list the k-combinations preceding it; this allows for instance random generation of k-combinations of a given set.\nEnumeration of k-combinations has many applications, among which are [software testing](https://bliptext.com/articles/software-testing), [sampling](https://bliptext.com/articles/sampling-statistics), [quality control](https://bliptext.com/articles/quality-control), and the analysis of [lottery](https://bliptext.com/articles/lottery) games.\n\n# Ordering combinations\nA k-combination of a set S is a [subset](https://bliptext.com/articles/subset) of S with k (distinct) elements.\nThe main purpose of the combinatorial number system is to provide a representation, each by a single number, of all \\tbinom nk possible k-combinations of a set S of n elements.\nChoosing, for any n, {0, 1, ..., n − 1} as such a set, it can be arranged that the representation of a given k-combination C is independent of the value of n (although n must of course be sufficiently large); in other words considering C as a subset of a larger set by increasing n will not change the number that represents C.\nThus for the combinatorial number system one just considers C as a k-combination of the set **N** of all natural numbers, without explicitly mentioning n.\nIn order to ensure that the numbers representing the k-combinations of {0, 1, ..., n − 1} are less than those representing k-combinations not contained in {0, 1, ..., n − 1}, the k-combinations must be ordered in such a way that their largest elements are compared first.\nThe most natural ordering that has this property is [lexicographic ordering](https://bliptext.com/articles/lexicographic-order) of the decreasing sequence of their elements.\nSo comparing the 5-combinations C = {0,3,4,6,9} and C′ = {0,1,3,7,9}, one has that C comes before C′, since they have the same largest part 9, but the next largest part 6 of C is less than the next largest part 7 of C′; the sequences compared lexicographically are (9,6,4,3,0) and (9,7,3,1,0).\nAnother way to describe this ordering is view combinations as describing the k raised bits in the [binary representation](https://bliptext.com/articles/binary-representation) of a number, so that C = {c1, ..., ck} describes the number\n(this associates distinct numbers to all finite sets of natural numbers); then comparison of k-combinations can be done by comparing the associated binary numbers.\nIn the example C and C′ correspond to numbers 10010110012 = 60110 and 10100010112 = 65110, which again shows that C comes before C′.\nThis number is not however the one one wants to represent the k-combination with, since many binary numbers have a number of raised bits different from k; one wants to find the relative position of C in the ordered list of (only) k-combinations.\n\n# Place of a combination in the ordering\nThe number associated in the combinatorial number system of degree k to a k-combination C is the number of k-combinations strictly less than C in the given ordering.\nThis number can be computed from C = {ck, ..., c2, c1} with ck > ... > c2 > c1 as follows.\nFrom the definition of the ordering it follows that for each k-combination S strictly less than C, there is a unique index i such that ci is absent from S, while ck, ..., ci+1 are present in S, and no other value larger than ci is.\nOne can therefore group those k-combinations S according to the possible values 1, 2, ..., k of i, and count each group separately.\nFor a given value of i one must include\nck, ..., ci+1 in S, and the remaining i elements of S must be chosen from the ci non-negative integers strictly less than ci; moreover any such choice will result in a k-combinations S strictly less than C.\nThe number of possible choices is, which is therefore the number of combinations in group i; the total number of k-combinations strictly less than C then is and this is the index (starting from 0) of C in the ordered list of k-combinations.\nObviously there is for every **N** ∈ **N** exactly one k-combination at index **N** in the list (supposing k ≥ 1, since the list is then infinite), so the above argument proves that every **N** can be written in exactly one way as a sum of k binomial coefficients of the given form.\n\n# Finding the k-combination for a given number\nThe given formula allows finding the place in the lexicographic ordering of a given k-combination immediately.\nThe reverse process of finding the k-combination at a given place N requires somewhat more work, but is straightforward nonetheless.\nBy the definition of the lexicographic ordering, two k-combinations that differ in their largest element ck will be ordered according to the comparison of those largest elements, from which it follows that all combinations with a fixed value of their largest element are contiguous in the list.\nMoreover the smallest combination with ck as the largest element is, and it has ci = i − 1 for all i < k (for this combination all terms in the expression except are zero).\nTherefore ck is the largest number such that.\nIf k > 1 the remaining elements of the k-combination form the k − 1-combination corresponding to the number in the combinatorial number system of degree k − 1, and can therefore be found by continuing in the same way for and k − 1 instead of N and k.\n\n## Example\nSuppose one wants to determine the 5-combination at position 72.\nThe successive values of \\tbinom n5 for n = 4, 5, 6, ... are 0, 1, 6, 21, 56, 126, 252, ..., of which the largest one not exceeding 72 is 56, for n = 8.\nTherefore c5 = 8, and the remaining elements form the 4-combination at position 72 − 56 = 16.\nThe successive values of \\tbinom n4 for n = 3, 4, 5, ... are 0, 1, 5, 15, 35, ..., of which the largest one not exceeding 16 is 15, for n = 6, so c4 = 6.\nContinuing similarly to search for a 3-combination at position 16 − 15 = 1 one finds c3 = 3, which uses up the final unit; this establishes, and the remaining values ci will be the maximal ones with , namely.\nThus we have found the 5-combination {8, 6, 3, 1, 0}.\n\n# National Lottery example\nFor each of the \\binom{49}6 lottery combinations c1 < c2 < c3 < c4 < c5 < c6, there is a list number N between 0 and which can be found by adding","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:13:06.156Z","updated_at":"2025-01-25T21:13:06.156Z","search_vector":"'combinatori':1 'number':2 'system':3","search_content":" \n \n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), and in particular in [combinatorics](https://bliptext.com/articles/combinatorics), the **combinatorial number system** of degree k (for some positive [integer](https://bliptext.com/articles/integer) k), also referred to as **combinadics**, or the **Macaulay representation of an [integer](https://bliptext.com/articles/integer)**, is a correspondence between [natural numbers](https://bliptext.com/articles/natural-number) (taken to include 0) N and k-[combinations](https://bliptext.com/articles/combination).\nThe combinations are represented as [strictly decreasing](https://bliptext.com/articles/sequence) [sequences](https://bliptext.com/articles/integer-sequence) ck > ... > c2 > c1 ≥ 0 where each ci corresponds to the index of a chosen element in a given k-combination.\nDistinct numbers correspond to distinct k-combinations, and produce them in [lexicographic order](https://bliptext.com/articles/lexicographic-order).\nThe numbers less than \\tbinom nk correspond to all k-combinations of {0, 1, ..., n − 1}.\nThe correspondence does not depend on the size n of the set that the k-combinations are taken from, so it can be interpreted as a map from ****N**** to the k-combinations taken from ****N****; in this view the correspondence is a [bijection](https://bliptext.com/articles/bijective-map).\nThe number N corresponding to (ck, ..., c2, c1) is given by\nThe fact that a unique sequence corresponds to any non-negative number N was first observed by [D. H. Lehmer](https://bliptext.com/articles/derrick-henry-lehmer).\nIndeed, a [greedy algorithm](https://bliptext.com/articles/greedy-algorithm) finds the k-combination corresponding to N: take ck maximal with, then take ck−1 maximal with , and so forth.\nFinding the number N, using the formula above, from the k-combination (ck, ..., c2, c1) is also known as \"ranking\", and the opposite operation (given by the greedy algorithm) as \"unranking\"; the operations are known by these names in most [computer algebra systems](https://bliptext.com/articles/computer-algebra-system), and in [computational mathematics](https://bliptext.com/articles/computational-mathematics).\nThe originally used term \"combinatorial representation of integers\" was shortened to \"combinatorial number system\" by [Knuth](https://bliptext.com/articles/donald-ervin-knuth),\nwho also gives a much older reference;\nthe term \"combinadic\" is introduced by James McCaffrey (without reference to previous terminology or work).\nUnlike the [factorial number system](https://bliptext.com/articles/factorial-number-system), the combinatorial number system of degree k is not a [mixed radix](https://bliptext.com/articles/mixed-radix) system: the part of the number N represented by a \"digit\" ci is not obtained from it by simply multiplying by a place value.\nThe main application of the combinatorial number system is that it allows rapid computation of the k-combination that is at a given position in the lexicographic ordering, without having to explicitly list the k-combinations preceding it; this allows for instance random generation of k-combinations of a given set.\nEnumeration of k-combinations has many applications, among which are [software testing](https://bliptext.com/articles/software-testing), [sampling](https://bliptext.com/articles/sampling-statistics), [quality control](https://bliptext.com/articles/quality-control), and the analysis of [lottery](https://bliptext.com/articles/lottery) games.\n\n# Ordering combinations\nA k-combination of a set S is a [subset](https://bliptext.com/articles/subset) of S with k (distinct) elements.\nThe main purpose of the combinatorial number system is to provide a representation, each by a single number, of all \\tbinom nk possible k-combinations of a set S of n elements.\nChoosing, for any n, {0, 1, ..., n − 1} as such a set, it can be arranged that the representation of a given k-combination C is independent of the value of n (although n must of course be sufficiently large); in other words considering C as a subset of a larger set by increasing n will not change the number that represents C.\nThus for the combinatorial number system one just considers C as a k-combination of the set **N** of all natural numbers, without explicitly mentioning n.\nIn order to ensure that the numbers representing the k-combinations of {0, 1, ..., n − 1} are less than those representing k-combinations not contained in {0, 1, ..., n − 1}, the k-combinations must be ordered in such a way that their largest elements are compared first.\nThe most natural ordering that has this property is [lexicographic ordering](https://bliptext.com/articles/lexicographic-order) of the decreasing sequence of their elements.\nSo comparing the 5-combinations C = {0,3,4,6,9} and C′ = {0,1,3,7,9}, one has that C comes before C′, since they have the same largest part 9, but the next largest part 6 of C is less than the next largest part 7 of C′; the sequences compared lexicographically are (9,6,4,3,0) and (9,7,3,1,0).\nAnother way to describe this ordering is view combinations as describing the k raised bits in the [binary representation](https://bliptext.com/articles/binary-representation) of a number, so that C = {c1, ..., ck} describes the number\n(this associates distinct numbers to all finite sets of natural numbers); then comparison of k-combinations can be done by comparing the associated binary numbers.\nIn the example C and C′ correspond to numbers 10010110012 = 60110 and 10100010112 = 65110, which again shows that C comes before C′.\nThis number is not however the one one wants to represent the k-combination with, since many binary numbers have a number of raised bits different from k; one wants to find the relative position of C in the ordered list of (only) k-combinations.\n\n# Place of a combination in the ordering\nThe number associated in the combinatorial number system of degree k to a k-combination C is the number of k-combinations strictly less than C in the given ordering.\nThis number can be computed from C = {ck, ..., c2, c1} with ck > ... > c2 > c1 as follows.\nFrom the definition of the ordering it follows that for each k-combination S strictly less than C, there is a unique index i such that ci is absent from S, while ck, ..., ci+1 are present in S, and no other value larger than ci is.\nOne can therefore group those k-combinations S according to the possible values 1, 2, ..., k of i, and count each group separately.\nFor a given value of i one must include\nck, ..., ci+1 in S, and the remaining i elements of S must be chosen from the ci non-negative integers strictly less than ci; moreover any such choice will result in a k-combinations S strictly less than C.\nThe number of possible choices is, which is therefore the number of combinations in group i; the total number of k-combinations strictly less than C then is and this is the index (starting from 0) of C in the ordered list of k-combinations.\nObviously there is for every **N** ∈ **N** exactly one k-combination at index **N** in the list (supposing k ≥ 1, since the list is then infinite), so the above argument proves that every **N** can be written in exactly one way as a sum of k binomial coefficients of the given form.\n\n# Finding the k-combination for a given number\nThe given formula allows finding the place in the lexicographic ordering of a given k-combination immediately.\nThe reverse process of finding the k-combination at a given place N requires somewhat more work, but is straightforward nonetheless.\nBy the definition of the lexicographic ordering, two k-combinations that differ in their largest element ck will be ordered according to the comparison of those largest elements, from which it follows that all combinations with a fixed value of their largest element are contiguous in the list.\nMoreover the smallest combination with ck as the largest element is, and it has ci = i − 1 for all i < k (for this combination all terms in the expression except are zero).\nTherefore ck is the largest number such that.\nIf k > 1 the remaining elements of the k-combination form the k − 1-combination corresponding to the number in the combinatorial number system of degree k − 1, and can therefore be found by continuing in the same way for and k − 1 instead of N and k.\n\n## Example\nSuppose one wants to determine the 5-combination at position 72.\nThe successive values of \\tbinom n5 for n = 4, 5, 6, ... are 0, 1, 6, 21, 56, 126, 252, ..., of which the largest one not exceeding 72 is 56, for n = 8.\nTherefore c5 = 8, and the remaining elements form the 4-combination at position 72 − 56 = 16.\nThe successive values of \\tbinom n4 for n = 3, 4, 5, ... are 0, 1, 5, 15, 35, ..., of which the largest one not exceeding 16 is 15, for n = 6, so c4 = 6.\nContinuing similarly to search for a 3-combination at position 16 − 15 = 1 one finds c3 = 3, which uses up the final unit; this establishes, and the remaining values ci will be the maximal ones with , namely.\nThus we have found the 5-combination {8, 6, 3, 1, 0}.\n\n# National Lottery example\nFor each of the \\binom{49}6 lottery combinations c1 < c2 < c3 < c4 < c5 < c6, there is a list number N between 0 and which can be found by adding","revisionCount":0},"hasMore":false,"nextCursor":null}

History