How many ways can N elements be partitioned into subsets of size K?

Question

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 that the resulting set is $N$. How many possibilities are there, i.e. what's the formula?

For instance: $N=4$, and $K=2$, gives $\binom{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:

$$ \begin{align} (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 \end{align} $$

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

Answer 1

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.

Answer 2

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.