9
$\begingroup$

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)?

$\endgroup$
  • 4
    $\begingroup$ So, are $x$ and $y$ variables in your optimization problem? I would like to learn more about problems where this kind of constraint would be required! Please share more context, if you can. $\endgroup$ – Robert Schwarz Oct 20 '19 at 4:53
  • $\begingroup$ The last link in the tag that I added (after the edit to the tag wiki is approved) points to Stanley's Enumerative Combinatorics (.PDF). $\endgroup$ – Rob Oct 21 '19 at 6:23
  • 2
    $\begingroup$ @Rob: Thanks for the reference. I'm already convinced of the usefulness of the choose function in general. My question was more about using it in constraints with variables. $\endgroup$ – Robert Schwarz Oct 21 '19 at 7:06
  • 1
    $\begingroup$ I can't think of an application either, I would appreciate an application/use case for such a function. $\endgroup$ – Marco Lübbecke Oct 22 '19 at 13:08
13
$\begingroup$

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}

| improve this answer | |
$\endgroup$
1
$\begingroup$

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 Gama or Beta might be applied and be interpreted using (in)equality constraints.

Reference: Factorial, Gamma and Beta Functions

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Probably these can only be used for parameters (inputs), not decision variables? I don't know GAMS well, but I'd be surprised if they can be used for decision variables. Or if they can, the model will certainly be very nonlinear. $\endgroup$ – LarrySnyder610 Oct 20 '19 at 0:33
  • 1
    $\begingroup$ @LarrySnyder610, thanks so much. you are right. it could be used for parameters, not variables. About GAMS, it has a fact(x) function to deal with it. $\endgroup$ – A.Omidi Oct 20 '19 at 5:08
0
$\begingroup$

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}.$$

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.