# Arranging m distinct groups of k elements each?

There are n elements in total which is already divided into m groups of k elements each. Thus, n=m*k.

The question is, how many arrangements of these m groups are possible?

I came to a possible solution of n!/m! but am not sure if that covers all permutations possible among each group (i.e, k! ways of arranging each group).

The original problem is as follows:

There exists an array of n distinct numbers. This array is divided into m sub-sequences of k elements each.

All elements of a subsequence are either greater than or less than all elements of another subsequence.

I have to find the number of possible permutations of the indices in the array which may appear in the sorted array.

• It is unclear whether you are only trying to arrange the $m$ groups or something more complicated. Of course there are $m!$ ways to "arrange" (permute) the $m$ groups. Please make your Question clearer, perhaps by detailing a small example. Mar 19 '16 at 0:17
• What was the original problem you were trying to solve? Mar 19 '16 at 0:17
• Should I change the question to reflect the original problem or add it to the existing problem? Sorry, I am new here. Mar 19 '16 at 0:19
• Please state the original problem you were trying to solve and show the work you did on that problem. In short, we would like to see the context for your current question. Mar 19 '16 at 0:22
• You could also clarify what permutations are allowed. Take a small example for now, $m=n=2$ so there are $4$ elements. Suppose the first group are the capital letters and the second group are the lower case letters. Which of the following are considered the same or distinct or not allowed? ABcd, BAcd, cdAB, cdBA, AcBd,... I.e. must the groups themselves remain together, must the groups be in a specific order, is order within the groups relevant,... Mar 19 '16 at 0:24

The groups are completely determined by the requirement that all elements of a subsequence are either greater than or less than all elements of another subsequence. As you realized, the elements in each of the $m$ groups of $k$ elements can be arranged in $k!$ orders. The $m$ subsequences can be arranged in $m!$ orders. Thus, the number of possible permutations of the indices in the array is $m!(k!)^m$.
• Would this result be strictly greater than $(m.k)!$ or would their relationship depend on values of m and k? Mar 19 '16 at 1:52
• Equality holds when $m = k = 1$. However, in general, $m!(k!)^m \leq (mk)!$ since $(mk)!$ represents all permutations of $mk$ objects, while $m!(k!)^m$ represents all the permutations in which the first $k$ objects are grouped together, the second $k$ objects are grouped together, and so forth. For instance, if $m = 2$ and $k = 3$, the elements in the set $\{1, 2, 3, 4, 5, 6\}$ can be sequenced in $6!$ ways, while the two sets $\{1, 2, 3\}$ and $\{4, 5, 6\}$ can be arranged in $2!$ ways and each can be arranged internally in $3!$ ways for a total of $2!(3!)^2 = 72$ permissible arrangements. Mar 19 '16 at 3:05