Modeling the Choose function

Question

In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose equality constraint

$${x \choose y} = C$$

without explicitly using the factorial-based formulation (if possible)?

Answer 1

I am going to assume that $x \in \mathbb{N}$ and $y \in \mathbb{N}$ are variables, and that $C \in \mathbb{N}$ is a constant. In this case, you can benefit from the fact that your equality constraint does not have that many possible solutions.

Case 1: $C = 1$

This only happens when $y=0$ or $y = x$. Assume that we have some upper bounds $\bar{x}$ and $\bar{y}$ on $x$ and $y$, respectively. You can then model the choose equality constraint as follows: \begin{eqnarray} 0 &\le& y & \le& \bar{y}z\\ -\bar{x}(1-z) &\le& y-x &\le& \bar{y}(1-z) \end{eqnarray} for a binary variable $z \in \mathbb{B}$. Note that $z=0$ corresponds to $y=0$, and $z=1$ corresponds to $y = x$.

Case 2: $C \neq 1$

It is conjectured that for $C \neq 1$, your equality constraint does not have many solutions, see Singmaster's conjecture on Wikipedia. In fact, for $C \le 2^{48} \approx 3 \times 10^{14}$, it has been shown that there are never more than 8 different solutions in terms of $x$ and $y$.

So for a given $C$ that is not too big, you can simply look up all $n$ solutions $a_i, b_i\in \mathbb{N}$ such that ${a_i \choose b_i} = C$, for $i = 1,\dots, n$. Next, introduce $n$ binary variables $z_i \in \mathbb{Z}$, such that $z_i = 1$ if and only if solution $i$ is chosen. That is \begin{eqnarray} x &=& \sum_{i=1}^n a_i z_i\\ y &=& \sum_{i=1}^n b_i z_i\\ \sum_{i=1}^n z_i &=& 1 \end{eqnarray}

Answer 2

AFAIK, some optimization software such as GAMS has some nice functions to deal with this. For example, function likes factorial (fact(x)).

Indeed, some estimations for the factorial function using the probability distribution functions like Gamma or Beta might be applied and be interpreted using (in)equality constraints.

Reference: Factorial, Gamma and Beta Functions

Answer 3

From Wikipedia's webpage on "binomial coefficients":

"The symbol $\tbinom {n}{k}$ is usually read as "$n$ choose $k$" because there are $\tbinom {n}{k}$ ways to choose an (unordered) subset of $k$ elements from a fixed set of $n$ elements.

Arranging the numbers $\tbinom {n}{0},\tbinom {n}{1},\ldots ,\tbinom {n}{n}$ in successive rows for $n=0,1,2,\ldots$ gives a triangular array called Pascal's triangle, satisfying the recurrence relation

$$\begin{align} \binom {n}{k} & ={\binom {n-1}{k}}+{\binom {n-1}{k-1}}. \\ \end{align}$$

Commonly, a binomial coefficient is indexed by a pair of integers $n ≥ k ≥ 0$ and is written $\tbinom {n}{k}$. It is the coefficient of the $x^k$ term in the polynomial expansion of the binomial power $(1 + x)^n$, and it is given by the formula

$$\begin{align} \binom {n}{k} & ={\frac {n!}{k!(n-k)!}}. \qquad\qquad \end{align}$$

For example, the fourth power of $1 + x$ is

$$\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}$$

and the binomial coefficient $\tbinom {4}{2} ={\tfrac {4!}{2!2!}}=6$ is the coefficient of the $x^2$ term.

The section titled: "computing the value of binomial coefficients" explains:

• Recursive formula

One method uses the recursive, purely additive, formula $$\binom {n}{k} = \binom {n-1}{k-1} + \binom {n-1}{k} \quad \text{for all integers } n,k:1\leq k\leq n-1, \qquad $$

with initial/boundary values

$${\binom {n}{0}}={\binom {n}{n}}=1\quad {\text{for all integers }}n\geq 0, \qquad \qquad \qquad \quad \qquad$$

• Multiplicative formula

A more efficient method to compute individual binomial coefficients is given by the formula

$$\binom {n}{k} ={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}},\qquad $$

where the numerator of the first fraction $n^{\underline {k}}$ is expressed as a falling factorial power. This formula is easiest to understand for the combinatorial interpretation of binomial coefficients. The numerator gives the number of ways to select a sequence of $k$ distinct objects, retaining the order of selection, from a set of $n$ objects. The denominator counts the number of distinct sequences that define the same $k$-combination when order is disregarded.

Due to the symmetry of the binomial coefficient with regard to $k$ and $n−k$, calculation may be optimised by setting the upper limit of the product above to the smaller of $k$ and $n−k$.

• Factorial formula

Finally, though computationally unsuitable, there is the compact form, often used in proofs and derivations, which makes repeated use of the familiar factorial function:

$${\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n, \qquad \qquad \qquad \qquad \qquad \qquad \qquad $$

where $n!$ denotes the factorial of $n$. This formula follows from the multiplicative formula above by multiplying numerator and denominator by $(n − k)!$; as a consequence it involves many factors common to numerator and denominator. It is less practical for explicit computation (in the case that $k$ is small and $n$ is large) unless common factors are first cancelled (in particular since factorial values grow very rapidly).

See also: "Injective functions from $\underline{N}$ to $\underline{X}$, up to a permutation of $\underline{N}$" and the "Twelvefold Way", or confirm this at the MathForum.

What is the algorithm for counting combinations?

// pseudo code
start count_combinations( k , n ) {
 if (k = n) return 1;
 if (k > n/2) k = n-k;
 res = n-k+1;
 for i = 2 by 1 while i < = k
  res = res * (n-k+i)/i;
 end for
 return res;
end

So for Catalan numbers, a sequence of positive integers, where the $n$th term in the sequence denoted $C_n$, is found in the following formula:

$$C_n = (2n)! / ((n + 1)!n!)$$

The $n$ factorial is equal to the product of all of the integers from $n$ down to $1$.

$$(n) ⋅ (n - 1) ⋅ (n - 2) ⋅ … ⋅ 2 ⋅ 1$$

Without using factorial that's:

$$C_{n}={2n \choose n}-{2n \choose n+1}={1 \over n+1}{2n \choose n}\quad {\text{ for }}n\geq 0,$$

and

$$C_{0}=1\quad {\text{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n}.$$