0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Mar 19 '16 at 0:17
  • $\begingroup$ What was the original problem you were trying to solve? $\endgroup$ – N. F. Taussig Mar 19 '16 at 0:17
  • $\begingroup$ Should I change the question to reflect the original problem or add it to the existing problem? Sorry, I am new here. $\endgroup$ – Janmajay Mar 19 '16 at 0:19
  • $\begingroup$ 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. $\endgroup$ – N. F. Taussig Mar 19 '16 at 0:22
  • $\begingroup$ 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,... $\endgroup$ – JMoravitz Mar 19 '16 at 0:24
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Would this result be strictly greater than $(m.k)!$ or would their relationship depend on values of m and k? $\endgroup$ – Janmajay Mar 19 '16 at 1:52
  • $\begingroup$ 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. $\endgroup$ – N. F. Taussig Mar 19 '16 at 3:05
  • $\begingroup$ Yeah,that makes sense. Thank you! (I cannot upvote as of now because I am low on rep points). $\endgroup$ – Janmajay Mar 19 '16 at 3:13
  • $\begingroup$ You are welcome. $\endgroup$ – N. F. Taussig Mar 19 '16 at 5:10

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.