Re: Combinatorics question


Chris Patil wrote:
> Hi there.
>
> I'm a biologist who's stumbled into a (computational) problem for which
> I need to understand combinatorics a bit better than I do.
>
> I was wondering whether anyone could point me in the right direction
> (e.g., intro texts) to solve this sort of problem:
>
> Suppose that I have two bins of finite size N. Each bin contains a
> specific set of letters (N each). There is no order. Within a bin, a
> given letter can appear zero, 1, or many times (up to and including N)
> in its bin.

Your bin is modeled by a mathematical object called a multiset.

> E.g.:
> Bin 1 = "Q Q D D"
> Bin 2 = "N N E E"
>
> Pairs of letters are drawn by taking one letter from each bin, until
> all the letters are gone.

To make each pair, are you taking one letter from Bin 1 and one letter
from Bin 2? Or are you taking two letters out of Bin 1 and Bin 2
(collectively)? I suspect the former, since this looks like a model of
matching genes from two parents.

> E.g. for the bins above, there are three distinguishable sets of letter
> pairs:
>
> a. "QD QE ND NE"
> b. "QD QD NE NE"
> c, "QE QE ND ND"

As has been pointed out, the only pairs you can get are QN, QE, DN, and
DE. It looks like you're starting with the sets Q Q N N and D D E E
(and not Q Q D D and N N E E, like you stated).

Let's continue assuming that you're starting with QQNN and DDEE.

> I'm interested in the number of ways that each distinct set of pairs
> could be formed -- in general, for any letters in the bins. In the
> example, I know that there are four times as many ways to get (a) as
> (b) and (c), and that there are an equal number of ways to get (b) and
> (c) -- 36 ways total to pull out letters,

You shouldn't get a total of 36. This is because you can think of
assigning each of the letters in one multiset to one of the letters in
the second multiset. (You can change from multisets to sets by
numbering the Q's, N's, D's, and E's as Q1 Q2 N1 N2 D1 D2 E1 E2.) Such
an assignment is called a 1-to-1 function, which can be represented as
a permutation.

The number of permutations of n objects is denoted by n! ("n
factorial"), and is the product of the integers between 1 and n. Thus,
in your case, 4! = 4*3*2*1 = 24.

If you order the objects, you can deal with permutations of the set
{1,2,...,N}. So the elements of the first bin could be ordered as Q1 Q2
N1 N2, and the elements of bin 2 as D1 D2 E1 E2.

One permutation is 1234; i.e., element #1 of bin 1 is matched to
element #1 of bin 2, element #2 of bin 1 is matched to element #2 of
bin 2, etc. This gives you the pairing Q1-D1 Q2-D2 N1-E1 N2-E2, and
when we get rid of the labels, we see we have QD QD NE NE.

Another permutation is 1243; this is the same as 1234, except element
#3 of bin 1 is matched with element #4 of bin 2, and element #4 of bin
1 is matched with element #3 of bin 2. This gives us the matching Q1-D1
Q2-D2 N1-E2 N2-E1, which (after removing the numeric lables) is a
pairing of the type QD QD NE NE.

We can generate a complete list -- there are programs already encoded
which will give all possible permutations -- and then you can count how
many QD QD NE NE 's you have, etc. (I know you're looking for a formula
for this, but I don't know one right off, and the procedure I've listed
can be programmed to work with any set of bins.)

> 24 that give (a), 6 for (b), and 6 for (c).

I suspect it's actually 16, 4, and 4, for each of these sets.

> But I got that by working it out by hand, which is not
> useful for the real examples I'm going to be working with, in which N
> will be >10, and any of 21 letters can appear in any proportion.
>
> So I'm not sure how to generalize this for larger N, more complex sets
> of letters, etc.
>
> Is there a formula, or must it be solved algorithmically?

I suspect there is a formula. Probably involving determinants or
perminants of a certain matrix.

--- Christopher Heckman

> I can imagine an inefficient algorithmic way to do it, like so:
>
> 1. Determine all possible ways to draw letter pairs.
> 2. Determine all possible distinguishable sets of pairs, and then go
> through the list for of all possible ways and count.
>
> I could implement that, and it would solve my problem, but I suspect
> that if I were just a little better at combinatorics, I would know how
> to come up with a general formula. I've been reading up on this all day
> and most of the examples of combinations and permutations involve a
> single bin, and I'm stuck.
>
> Can anyone give advice?
>
> Thanks,
>
> Chris

.

Relevant Pages

  • Re: Combinatorics question
    ... >> specific set of letters. ... Within a bin, a ... > Your bin is modeled by a mathematical object called a multiset. ... > If you order the objects, you can deal with permutations of the set ...
    (sci.math)
  • Re: Combinatorics question
    ... >>> in its bin. ... >> Your bin is modeled by a mathematical object called a multiset. ... >>> all the letters are gone. ... >> If you order the objects, you can deal with permutations of the set ...
    (sci.math)
  • Re: A toilet expression
    ... deposit the post directly to the bin on 't'other side. ... Instead of cat wee, the box provides comfortable accommodation for several families of snails who love to eat letters - they are particularly partial to picture postcards, but at a pinch will eat your cheque from the Taxation Office or the Lotteries Commission. ... When the snails die, their bodies are eaten by ants, so when you pulling out your sodden mess of junk mail, bills, snail shells and IMPORTANT LETTERS, you also get covered in ants. ...
    (alt.usage.english)
  • Re: Combinatorics question
    ... > I need to understand combinatorics a bit better than I do. ... > specific set of letters. ... Within a bin, a ... Determine all possible distinguishable sets of pairs, ...
    (sci.math)
  • Re: Probability and Entropy of a book using matlab
    ... I want to calculate the probability of the letters coming up ... array element. ... 13th bin ...
    (comp.soft-sys.matlab)