# Combinatorial number system

This online calculator represents given natural number as sequences of k-combinations, referred as the combinatorial number system of degree k (for some positive integer k), aka combinadics

### This page exists due to the efforts of the following people:

#### Anton

Created: 2020-02-14 09:32:57, Last updated: 2021-03-18 20:43:22

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8592/. Also, please do not modify any references to the original work (if any) contained in this content.

This online calculator converts natural number from decimal number system to so-called combinadics, or combinatorial number system of degree k. In this system, the number N is represented as sum of binomials:

$N={\binom {c_{k}}{k}}+\cdots +{\binom {c_{2}}{2}}+{\binom {c_{1}}{1}}$,

and sequence of strictly decreasing coefficients $c_k > \dots > c_2 > c_1 \geqslant 0$ is the combinatorial representaton of N in combinatorial number system of degree k.

This representation is actually a bijection between natural number N and k-combination taken from N, so you can generate the k-combination at index N, which has some useful applications.

### How to convert

You should enter a number to convert and desired combinatorial number system degree in the fields below, and the calculator shows you the representation and detail of conversion.

The conversion algorithm is described below the calculator.

Details

### Algorithm to find the k-combination for a given number

Finding the k-combination for a given number is called unranking and there is a simple greedy algorithm to do it:

1. Find maximum $c_k$ which holds ${\tbinom {c_{k}}{k}}\leq N$
2. Find maximum $c_{k-1}$ which holds ${\tbinom {c_{k-1}}{k-1}}\leq N - {\tbinom {c_{k}}{k}}$
3. ...
4. Find maximum $c_1$ which holds ${\tbinom {c_1}{1}}\leq N - {\tbinom {c_{k}}{k}} - {\tbinom {c_{k-1}}{k-1}} - \cdots - {\tbinom {c_2}{2}}$

Note that ${\tbinom {c_{i}}{i}} = 0$ if $c_i < i$. It is used to pad sum with zeroes, as you can see in the example above. In such cases, algorithm assigns $c_i$ the maximum possible value: $i-1$

URL copied to clipboard
PLANETCALC, Combinatorial number system