1

I am wondering about this game for a while. Feel free to tell me whether this question is well-defined or not.

Say we have a binomial coefficient $\binom{5}{2}$. It is the number of ways to select two boxes (denoted with $X$) out of five (denoted with $O$). I want to define/construct a sequence $a_n$ of these possible combinations:

$$a_1=(X,X,O,O,O) \\a_2=(O,X,X,O,O) \\... \\a_\binom{5}{2}=(X,O,O,O,X).$$

The above example is easy to do manually because the coefficient is small so I can list the possibilities.

What if I have $\binom{n}{k}$? Is there a way we can define such sequence? I imagine it should be something like $a_i=(a_{i,1},a_{i,2},...,a_{i,n+k})$, and then we can recover each $a_{i,j}$. Of course, it should be without listing all the possibilities first.

I am thinking that we need conditional function at least, don't we? I mean, explicit formulation is great, but inductively or recursively it should be OK too if it exists.

Thanks for the guidance and suggestion.

EDIT: Some have suggested the lexicographic ordering. However, what I intend to find out is how to exactly know which letter is in some index. For example using the above notation, how do I find $a_{9,4}$ without listing them all?

10understanding
  • 717

2 Answers2

1

One natural way to order that sequence would be lexicographical, as hinted by the comment of drhab. In your example, ordering the elements lexicographically would give us;

$a_1 = (X,X,O,O,O)$, $a_2 = (X,O,X,O,O)$, $a_3 = (X,O,O,X,O)$, $a_4 = (X,O,O,O,X)$, $a_5 = (O,X,X,O,O)$, $a_6 = (O,X,O,X,O)$, $a_7 = (O,X,O,O,X)$, $a_8 = (O,O,X,X,O)$, $a_9 = (O,O,X,O,X)$, $a_{10} = (O,O,O,X,X)$

It is easy to generalize this to any binomial coefficient.

Uğur Cin
  • 121
  • Yes, thanks. I would actually love to find the exact method for large binomial coefficient without "searching the dictionary". Do you know any such method? That, I can calculate, for example, what letter is in a given index only. – 10understanding Jan 24 '20 at 15:26
1

assigning a number to every combination in n choose k Here n choose k is denoted by (n c k)

we have ( a1, a2, a3, ......,an) and ai would be denoted by x if there is a box kept at position ai, 0 < i < (n+1) and i is a natural no.

first of all divide them into groups, like group 1 has all the combinations where there is a box in 1st position

And group 2 has all the combinations where there is a box in 2nd position but not in 1st position

Similarly group k has all the combinations where there is a box placed placed ath rth position but not before any rth position for r<= n-k+1

we see that any combination of choosing k places for identical boxes out of n places will exactly fall into one of the above category...

now repeat the same process for every element in each group and you can assign a number..

Interestingly, this is also an explanation for the fact that (n c k) = (n-1 c k-1) + (n-2 c k-1) + ....+ (k-1 c k-1) each term on rhs is no of elements in each group we divided the problem into...

now, how do we obtain the combination given its assigned number? suppose a combination belongs to group2, then assigned number would be greater than (n-1 c k-1) but less than (n-1 c k-1) + (n-2 c k-1) and again repeat the process as defined above...and you obtain the combination

rishi5041
  • 11