2

I have four indices $\{a,b,c,d\}$ that I need to reduce to a single index. They take values from $1$ to $8$ and have $a<b<c<d$ since for my purposes only combinations, not permutations, matter.

There are ${8 \choose 4}=70$ possible combinations, and I need the single index to run from $1$ to $70$ without skipping any numbers.

This question asks how to do the reverse, but I had trouble following how to get to the single index in the first place.

I've been trying to derive a simple formula for the single index in terms of $a,b,c,d$ but have been having trouble tracking down my errors. The end result always involves sums over binomial coefficients.

BGreen
  • 850
  • I can count by increasing the indices from right to left (e.g. $1,2,3,4\rightarrow1$, then $1,2,3,5\rightarrow2$, ... $1,2,3,8\rightarrow5$, $1,2,4,5\rightarrow6$, ...) and incrementing an index to the left only when the indices to the right can grow no larger. It's clear that the last index can be accounted for by adding $d-c-1$ to whatever comes from the first three indices. By "what comes from the first three", I mean that if for example we set $a=2$, then we've already passed by the ${7 \choose 3}$ combinations that have $a=1$ - so we should add ${7 \choose 3}$ to find the single index. – BGreen Jul 05 '19 at 21:22
  • 1
    $$1+\binom{a-1}{1}+\binom{b-1}{2}+\binom{c-1}{3}+\binom{d-1}{4}$$ is the index of the "squashed order" in the set of such tuples. – Thomas Andrews Jul 05 '19 at 21:26
  • That answer doesn't make mathematical sense whenever $a=1,b=2,c=3$ or $d=4$. – BGreen Jul 05 '19 at 21:31
  • 1
    @BGreen This uses the convention $\binom{n}{k} = 0$ for $k > n$. – Theo Bendit Jul 05 '19 at 21:38
  • That answer gives $1$ for $(a,b,c,d)=(1,2,3,4),$ if you were referring to my comment. @BGreen – Thomas Andrews Jul 05 '19 at 21:39
  • Thank you both - this is a different ordering than I had been thinking of, but it's given by a much cleaner formula. That works for me. – BGreen Jul 05 '19 at 21:47

1 Answers1

2

There's a handy wiki link in the dupe target of the linked question. According to the wiki article, we can map a specific $(d, c, b, a)$, a decreasing list of positive numbers, to the number $$\binom{d-1}{4} + \binom{c-1}{3} + \binom{b-1}{2} + \binom{a-1}{1}+1.$$ (Note that, in the wiki article, the numbers have a lower bound of $0$ instead of $1$, and the numbering system also starts at $0$, hence the $-1$s and the $+1$, so that you can get your numbering system from $1$ to $70$. Also, note that this assumes $\binom{n}{k} = 0$ for $k > n$, which is necessary to assume when $c = 1$.)

As an example, $(6, 5, 2, 1)$ corresponds to the number $$\binom{5}{4} + \binom{4}{3} + \binom{1}{2} + \binom{0}{1}+1 = 5 + 4 + 0 + 0 = 9,$$ making it the $9$th combination out of $70$.

Of course, you want the inverse operation to this. Specifically, you want the combination corresponding to the $i$th index, in order to enumerate all combinations with a single variable. This section from the wiki link tells you how to go about doing this. Given an index $N$ between $1$ and $70$,

  • Find the largest $k$ so that $\binom{k}{4} \le N - 1$. Let $d = k + 1$. (Don't forget to allow for the possibility for $\binom{k}{4} = 0$. In fact, if $N = 0$, then $(d, c, b, a) = (4, 3, 2, 1)$)
  • Find the largest $k$ so that $\binom{k}{3} \le N - 1 - \binom{d-1}{4}$. Let $c = k + 1$. (If $N - 1 - \binom{d-1}{4} = 0$, then $(d, c, b, a) = (d, 3, 2, 1)$.)
  • Find the largest $k$ so that $\binom{k}{2} \le N - 1 - \binom{d-1}{4} - \binom{c-1}{4}$. Let $b = k + 1$. (If the right hand side is $0$, then $b = 2$ and $a = 1$.)
  • The remainder should be a number less than or equal to $b - 1$. Let it be $a$.
Theo Bendit
  • 50,900