Re: Combinatorics question

On Apr 5, 3:52 pm, Ketakop...@xxxxxxxxx wrote:
Hi all, I have a problem regarding combinatorics. Let's see if I'm
capable of explaining myself correctly:

I have S distinct elements, from which I will pick four. So far, the
number of groups I can make up this way is C(S,4) or S! / {4!*(S -
4)!}.

Now, from those C(S,4) posibilities, I want to discard those which
share 3 elements, well just one of the two. Let's better put an
example:

I have the letters a,b,c,d,e,f (6 elements), and I can group them
together in groups of four in C(6,4)=15 ways:

abcd
abce
abcf
abde
abdf
abef
acde
acdf
acef
adef
bcde
bcdf
bcef
bdef
cdef

Now, I have to start to discard: "abce" is the first one to discard,
since "abc" already appeared on the first combination, and same with
"abcf". I also reject "abde" as "abd" appeared on the first
combination, "abdf" too. I'll mantain "abef" since it has only two
elements repeated with the first combination. Doing this for all
combinations, I end up with only three: "abcd", "abef" and "cdef".

So, I'd like to know if there's an easy way to know how many valid
combinations there are, and which ones they are. I'm aware that
depending on which one I start to compare from, I will end up with
different solutions, but I don't care about that. Any formula,
algorithm or help is much appreciated. Thanks in advance,

Let X be a finite set with n elements, and let T be the set
of all 4-element subsets of T, so that T has C(n,4) elements.
Construct a graph G with vertex set T and such that two
vertices v and w are connected with an edge iff they share
exactly 3 elements. This is a well-know graph, called the
Johnson graph J(n, 4), which appears when one studies what
is known as the Johnson association schemes.

What you are dealing with, if I understand you correctly,
is with subsets Z of T such that no pair of vertices in Z
are connected by and edge. In other words, you are considering
stable sets in the graph G.

In particular, you seem to want to know what's called
the independence number of J(n, 4), which is the
maximal cardinality of an independent subset. This is
a problem relevant to coding theory, as that number
is precisely the same thing as the largest size of
a binary code of words of length n, weight 4, and
minimal distance 4.

Therefore, I would look in a text on coding theory
in order to find information about your problem.

HTH,

-- m


.

Relevant Pages

  • Re: Wait for SetPositions
    ... graph has started to play. ... discard would have 4 seconds removed form the time stamp). ... YOu could also do this AFTER the decoder but you will have incurred the ... Iain Downs ...
    (microsoft.public.win32.programmer.directx.video)
  • Re: GMFBridge compressed streams in suspend mode?
    ... Discard the rest. ... -set the source graph to discard mode ... -pause the capture graph on the EndOfSegment Event ...
    (microsoft.public.win32.programmer.directx.video)