3
$\begingroup$

Let's have 2 numbers, N and K, where K divides N. The number of K-combinations from a given set S of N elements is a well known formula. Let's concatenate N/K groups (resulting in N elements) such as the resulting set is N. How many possibilities are there, i.e. what's the formula?

For instance: N=4, K=2, C(4, 2) = 6 {1,2},{1,3},{1,4},{2,3},{2,4},{3,4} The 3 possibilities are:

  {1,2},{3,4}
  {1,3},{2,4}
  {1,4},{2,3}

I generated these combinations and I think the number goes like this:

(4, 2): 3
(6, 3): 10
(6, 2): 15
(10, 5): 126
(9, 3): 280
(10, 2): 945
(14, 7): 1716
(12, 4): 5775
(15, 5): 126126
(15, 3): 1401400

Apparently, the result always divides with (N-1).

$\endgroup$
  • $\begingroup$ The order of the groups doesn't matter, i.e. {3,4},{1,2} = {1,2},{3,4}, {2,4},{1,3} = {1,3},{2,4}, etc. $\endgroup$ – Liviu Jan 21 '14 at 16:27
  • $\begingroup$ In what context did you encounter this problem? Did you try anything / do you have any thoughts on a solution? $\endgroup$ – ShreevatsaR Jan 21 '14 at 17:05
  • $\begingroup$ The context for those interested: Stack Overflow $\endgroup$ – Liviu Jan 22 '14 at 9:29
  • $\begingroup$ Cool, I was just wondering myself about the problem of generating these partitions; have posted an answer there on Stack Overflow. $\endgroup$ – ShreevatsaR Jan 22 '14 at 13:22
4
+50
$\begingroup$

You want to count the number of set partitions of a set of $n$ elments, into $n/k$ parts each of size $k$. (It is assumed that $k$ divides $n$.)

Method 1.

We can generate such a partition by writing down the $n$ elements in a sequence, and then declaring that the first $k$ elements are the first part, the next $k$ elements are the second part, and so on. There are $n!$ ways of writing $n$ elements in a sequence, but each partition is generated multiple times: for each of the $n/k$ parts, there are $k!$ orderings of the $k$ elements in that part that would lead to the same partition, as you don't care about the order within each part. Further, there are $(n/k)!$ orderings of the parts themselves, for the same partition.

The number of partitions is therefore: $$\frac{n!}{(k!)^{n/k} (n/k)!}$$

Method 2.

You can choose the elements of the first part in $\binom{n}{k}$ ways, then choose the elements of the second part as $k$ out of the remaining $n-k$ in $\binom{n-k}{k}$ ways, and so on. But as different orderings of the $(n/k)$ parts don't change the partition, the number of partitions is

$$\frac{\binom{n\vphantom{k}}{k}\binom{n-k}{k}\cdots\binom{k}{k}}{(n/k)!} = \frac{n!}{(k!)^{n/k}(n/k)!}$$ as before.

You can verify that this accords with all your cases. For instance, for $n=15$ and $k=5$, you get $\frac{15!}{5!^3 3!} = 126126$. These numbers are tabulated in OEIS A060540, and no simpler formula is listed.

$\endgroup$
  • $\begingroup$ It also validates for (15, 3) = 1401400, just added. I'll have more time the next days. $\endgroup$ – Liviu Jan 21 '14 at 18:41
  • $\begingroup$ The prove seems correct and the formula is valid for the given numbers, but I still wait for a few days before accepting the answer. $\endgroup$ – Liviu Jan 22 '14 at 15:20
2
$\begingroup$

I might be wrongly interpreting your question (forgive me if this is the case). But based on certain phrases (i.e., "number of $k$-combinations of a given set" and "The order of the groups doesn't matter [from comments]) in addition to the numbers you put forth in your question, it seems to me that you are looking for the formula for:

The number of ways to choose $k$ items at a time from a set of $n$ items.

It turns out that this idea of combinatorics has very deep and interesting applications to nearly every branch of mathematics. The terminology for the number you seek is called a Binomial Coefficient and the notation for the statement above is $$ \binom{n}{k} = \text{number of ways to choose $k$ items from a set of $n$ items}$$ That is why the notation $\binom{n}{k}$ is also pronounced "$n$-choose-$k$". There are other notations including $C(n,k$), $C_k^n$, $_nC_k$, $C^k_n$, but I will continue to use the notation $\binom{n}{k}$ in this answer. For those of you wondering how to type it in a math-environment like TeX,LaTeX,etc. (because eventually I'm sure you will encounter the occasion to use the notation in an answer - that's how prolific binomial coefficients are), you want to use $\$\text{\binom{n}{k}}$\$.

There are many different formulas for binomial coefficients and it is a shame that I can't list them all. However, before we jump into some formulas, it is worth our time to introduce some useful notation is that presented by the Factorial. Incidentally, the number of ways to arrange (order matters) $k$ objects from a set of $n$ objects is related to Permutations which uses the factorial extensively.

Define $n! = \prod\limits_{k=1}^n k = 1\cdot2\cdot3\cdots(n-1)\cdot n$. The convention for "vacuous products" lets us define $0!=1$ but this can also be verified using the definition of the Gamma Function where the notion of a factorial can be extended to all real numbers (except negative integers). Since $n! = n\cdot(n-1)\cdots2\cdot1$, we can condense this into $n!=n(n-1)!$ and immediately see a recursive relation defined by the factorial. Some values that are worth memorizing include: $$0!=1 (\text{by defintion})\\ 1!=1 \\ 2!=2=2*1 \\ 3!=6=3*2*1 \\ 4!=24=4*3*2*1 \\ 5!=120=5*4*3*2*1$$.

Back to combinations, one of the most fundamental formulas for a binomial coefficient is:

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)(n-k)!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots(1)} \\ \binom{n}{k} = \frac{n^{\underline{k}}}{k!} = \prod\limits_{j=1}^{k} \frac{n+1-j}{j} \quad \text{integer $k \geq 0$}$$

In particular, it is straightforward to verify that $$\binom{n}{0} = \binom{n}{n} = 1 \qquad \binom{n}{1} = n \qquad \binom{n}{2} = \frac{n(n-1)}{2}$$

Also, the following identity is one reason why high symmetry exists in Pascal's Triangle:

$$ \binom{n}{k} = \binom{n}{n-k}$$


So now you have your formula(s) for $\binom{n}{k}$ and a little crash course on factorials. I have computed the same numbers below that you input originally and computed there corresponding binomial coffecients.

$$\binom{4}{2} = 6, \quad \binom{6}{3} = 20, \quad \binom{6}{2} = 15, \\ \binom{10}{5} = 252, \quad \binom{9}{3} = 84, \quad \binom{10}{2} = 45, \\ \binom{14}{7} = 3432, \quad \binom{12}{4} = 495, \quad \binom{15}{5} = 3003 $$ Some of your numbers are either correct or halved (if combinations are what you're after). Given the definitions above, it wouldn't be hard to write a new program with inputs $n$ and $k$ to output $\binom{n}{k}$.

Here's an answer for your bounty message: "...I'm not a mathematician. Are they on this site?"

Yes. Yes we are.

$\endgroup$
  • $\begingroup$ I don't have the time right now, but the formula from the answer of ShreevatsaR works for the next 3 tests: (15,5), (15,3), (10,2). $\endgroup$ – Liviu Jan 21 '14 at 18:44
  • $\begingroup$ Thank you for the generous answer, but I'm not looking for the k-combinations in n, but for the sequences of such combinations that cover the entire set (given that k divides n). For exemple, for (6,3): {1 2 3} {4 5 6}, {1 2 4} {3 5 6}, {1 2 5} {3 4 6}, {1 2 6} {3 4 5}, {1 3 4} {2 5 6}, {1 3 5} {2 4 6}, {1 3 6} {2 4 5}, {1 4 5} {2 3 6}, {1 4 6} {2 3 5}, {1 5 6} {2 3 4} (10 solutions) $\endgroup$ – Liviu Jan 22 '14 at 13:07

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.