Prev: The Muse of Musatov 'Mu'
Next: Musatov is using others' intelelctual property?. Come clean.
From: cbrown on 5 Oct 2009 12:38
On Oct 5, 6:41 am, The Qurqirish Dragon <qurqiri...(a)aol.com> wrote:
> On Oct 5, 9:18 am, dvholten <i...(a)dvholten.de> wrote:
>
>
>
> > hi folks,
>
> > here is a combinatorics question for the experts:
> > lets assume we have a set of objects
> >      a b c d  e f g h  i j k l
> > these shall be put in sets of equal size (3 sets of 4 for example) how
> > can i enumerate(generate) the combinations of sets?
> > that is
> >      abcd efgi hjkl
> >      abcd efgj hikl
> > and so on.
>
> >      'abcd' and 'dbca' are equal
> > and
> >      'abdc' 'efkl'
> > is the same as
> >      'klef' 'dbca'
>
> > how many enumerations are there? to see if the generator is correct..
>
> > i found a lot of examples giving answers to _similar_ questions, but
> > none is useful enough for me. unfortunately i cant put together the
> > pieces which are obviously in front of me.
>
> > any literature links are welcome.
>
> > many thanks
> > dvholten
>
> The easiest way to avoid duplicates, if you are enumerating the
> choices is this way:
> 1) to avoid abcd <=> bcad, be certain to always list entries in each
> group in alphabetical order.
>
> 2) to avoid abcd,efgh <=> efgh, abcd, be certain to always list the
> groups in alphabetical order.
>
> note that this means the first element of the first group will always
> be "a"
>

<snip>

Your approach suggests the following recurrence:

In the original problem, first consider all the patterns that have
(abcd) in the first group. The number of such patterns is the same as
the number of ways to similarly distribute 8 elements (efghijkl) into
2 groups of 4 (which of course is the same as the number of ways to
distribute (abcdefgh) into two groups of 4).

Now, progressively swapping b for any of the letters in the remaining
8 letters after d, note there are the same number of patterns having
abce in the first group, abcf, abcg, etc.; and similarly, the same
number having abde, abdf, abdg; or starting acfj and so on.

In fact, the only constraint is that "a" must be a member of the first
group; and there are 11 choose 3 such initial groups, each having the
same number of patterns: which turns out to be the same as number of
ways to distribute 2 groups of 4.

So if we define f(n) as the number of combinations for 4*n elements,
then f(1) = 1, and f(n+1) = C(4*n-1, 3)*f(n).

f(1) = 1
f(2) = 35
f(3) = 5775
f(4) = 2626260 (wow!)

etc.

Cheers - Chas


From: James Dow Allen on 5 Oct 2009 14:03
On Oct 5, 8:35 pm, dvholten <i...(a)dvholten.de> wrote:
> makes sense. unfortunatly there a more than those meager 12 elements...
> i have 256 in 64 groups of 4. the large numbers themselves dont scare me -

More generally suppose N groups of K.
The number you seek is
(KN)! / N!(K!)^N
.... I think! :-)

James D. Allen
From: cbrown on 5 Oct 2009 13:35
On Oct 5, 9:38 am, "cbr...(a)cbrownsystems.com"
<cbr...(a)cbrownsystems.com> wrote:
> On Oct 5, 6:41 am, The Qurqirish Dragon <qurqiri...(a)aol.com> wrote:
>
>
>
> > On Oct 5, 9:18 am, dvholten <i...(a)dvholten.de> wrote:
>
> > > hi folks,
>
> > > here is a combinatorics question for the experts:
> > > lets assume we have a set of objects
> > >      a b c d  e f g h  i j k l
> > > these shall be put in sets of equal size (3 sets of 4 for example) how
> > > can i enumerate(generate) the combinations of sets?
> > > that is
> > >      abcd efgi hjkl
> > >      abcd efgj hikl
> > > and so on.
>
> > >      'abcd' and 'dbca' are equal
> > > and
> > >      'abdc' 'efkl'
> > > is the same as
> > >      'klef' 'dbca'
>
> > > how many enumerations are there? to see if the generator is correct..
>
> > > i found a lot of examples giving answers to _similar_ questions, but
> > > none is useful enough for me. unfortunately i cant put together the
> > > pieces which are obviously in front of me.
>
> > > any literature links are welcome.
>
> > > many thanks
> > > dvholten
>
> > The easiest way to avoid duplicates, if you are enumerating the
> > choices is this way:
> > 1) to avoid abcd <=> bcad, be certain to always list entries in each
> > group in alphabetical order.
>
> > 2) to avoid abcd,efgh <=> efgh, abcd, be certain to always list the
> > groups in alphabetical order.
>
> > note that this means the first element of the first group will always
> > be "a"
>
> <snip>
>
> Your approach suggests the following recurrence:
>
> In the original problem, first consider all the patterns that have
> (abcd) in the first group. The number of such patterns is the same as
> the number of ways to similarly distribute 8 elements (efghijkl) into
> 2 groups of 4 (which of course is the same as the number of ways to
> distribute (abcdefgh) into two groups of 4).
>
> Now, progressively swapping b for any of the letters in the remaining
> 8 letters after d, note there are the same number of patterns having
> abce in the first group, abcf, abcg, etc.; and similarly, the same
> number having abde, abdf, abdg; or starting acfj and so on.
>
> In fact, the only constraint is that "a" must be a member of the first
> group; and there are 11 choose 3 such initial groups, each having the
> same number of patterns: which turns out to be the same as number of
> ways to distribute 2 groups of 4.
>
> So if we define f(n) as the number of combinations for 4*n elements,
> then f(1) = 1, and f(n+1) = C(4*n-1, 3)*f(n).
>
> f(1) = 1
> f(2) = 35
> f(3) = 5775
> f(4) = 2626260    (wow!)
>
> etc.
>

Which boils down to:

f(n) = (4n)!/(n!*24^n)

Cheers - Chas


From: Jim Ferry on 5 Oct 2009 17:03
On Oct 5, 2:03 pm, James Dow Allen <jdallen2...(a)yahoo.com> wrote:
> On Oct 5, 8:35 pm, dvholten <i...(a)dvholten.de> wrote:
>
> > makes sense. unfortunatly there a more than those meager 12 elements...
> > i have 256 in 64 groups of 4. the large numbers themselves dont scare me -
>
> More generally suppose N groups of K.
> The number you seek is
>   (KN)! / N!(K!)^N
> ... I think!  :-)
>
> James D. Allen

More generally still, suppose you have n1 groups with k1 elements, n2
groups
with k2 elements, ..., and nr groups with kr elements, with none of
the kj's
equal.

We ask for the number of ways to fill these groups by selecting
without
replacement from M elements, where order is irrelevant both between
groups
and for elements within a group. There are
C(M,n1*k1) = M! / ((M-n1*k1)! (n1*k1)!) ways to select the elements
which
go into the first n1 groups (i.e., those with k1 elements), and, using
the result James Allen gave, (n1*k1)!/(n1! k1!^n1) ways to put these
into
groups. Thus, the total number of ways to fill the groups is

C(M,n1*k1) (n1*k1)!/(n1! k1!^n1) * C(M-n1*k1,n2*k2) (n2*k2)!/(n2! k2!
^n2) *
... * C(M-n1*k1-n2*k2-...-n[r-1]*k[r-1],nr*kr) (nr*kr)!/(nr! kr!
^nr).

This simplifies to

M!/((n1!n2!...nr!)(k1!^n1 k2!^n2 ... kr!^nr)(M-n1*k1-n2*k2-...-
nr*kr)!).
From: Steve C on 5 Oct 2009 18:18
James Dow Allen wrote:
> On Oct 5, 8:35 pm, dvholten <i...(a)dvholten.de> wrote:
>> makes sense. unfortunatly there a more than those meager 12 elements...
>> i have 256 in 64 groups of 4. the large numbers themselves dont scare me -
>
> More generally suppose N groups of K.
> The number you seek is
> (KN)! / N!(K!)^N
> ... I think! :-)
>
> James D. Allen


Yes. A similar formulation is to choose N subsets of size K
from a set of M, where M >= N K.

M! / N! (K!)^N
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: The Muse of Musatov 'Mu'
Next: Musatov is using others' intelelctual property?. Come clean.