# Combinatory Counting help

• February 12th 2009, 03:09 PM
Kim Nu
Combinatory Counting help
A protein may contain several cysteins, which my pair together to form disulfide bonds as shown in the figure. If there is an even number n of cysteins, n/2 disulfide bonds can form. How many different disulfide pairing arrangements are possible?

For clarity, see attached for the question with the figure.

So I think the number of arrangements, N, would be equal to:

N=(n/2)!

Is this correct, and if not, could someone explain it to me? Thanks,

Kim
• February 13th 2009, 02:58 PM
awkward
Quote:

Originally Posted by Kim Nu
A protein may contain several cysteins, which my pair together to form disulfide bonds as shown in the figure. If there is an even number n of cysteins, n/2 disulfide bonds can form. How many different disulfide pairing arrangements are possible?

For clarity, see attached for the question with the figure.

So I think the number of arrangements, N, would be equal to:

N=(n/2)!

Is this correct, and if not, could someone explain it to me? Thanks,

Kim

Hi Kim,

I am not sure I understand the problem correctly, but the statement seems to say there are n/2 possible bonds, each of which may or may not form-- so there are 2 possibilities for each possible bond.

If this is so, then the total possible number of arrangements is $2^{n/2}$.
• February 14th 2009, 04:41 AM
Laurent
The problem is not very clearly defined, and I have a different interpretation from awkward's.

Based on the drawing, it seems to me that a configuration is given by a choice of "non-crossing pairings".

In other words, a configuration is a $2p$-uplet $(i_1,\ldots,i_p,j_1,\ldots,j_p)$ such that $0\leq p\leq n/2$ and:

$1\leq i_1< \cdots < i_{p-1}< i_p < j_p < j_{p-1} <\cdots < j_1 \leq n$

(The bonds are between the cysteins at positions $i_q$ and $j_q$ for $q=1,\ldots,p$, cf. the attached drawing).

As a consequence, the number of configurations is the number of subsets of $\{1,\ldots,n\}$ with an even number of elements (say, $2p$).

Thus the number of configurations is:

$N=\sum_{0\leq 2p\leq n}{n\choose 2p}$.

In fact, there are as many subsets of $\{1,\ldots,n\}$ with an even or an odd number of elements. This is a consequence of the following equality (using the binomial formula):

$\sum_{0\leq 2p\leq n}{n\choose 2p}-\sum_{0\leq 2p+1\leq n}{n\choose 2p+1}$ $=\sum_{0\leq k\leq n}(-1)^k {n\choose k} = (1-1)^n =0$.

We deduce that the number of even-sized subsets of $\{1,\ldots,n\}$ is half the number of subsets of $\{1,\ldots,n\}$.

As a conclusion, $N=\frac{1}{2}2^n = 2^{n-1}$.
• February 14th 2009, 06:52 AM
Kim Nu
Laurent,

With your formula, N=2^(n-1), for 4 molecules the total number of different pairing options would be 2^3 = 8. I don't see how 8 different pairing options could be possible, could you explain it to me? Thanks,

Kim
• February 14th 2009, 10:07 AM
Laurent
Quote:

Originally Posted by Kim Nu
Laurent,

With your formula, N=2^(n-1), for 4 molecules the total number of different pairing options would be 2^3 = 8. I don't see how 8 different pairing options could be possible, could you explain it to me? Thanks,

Kim

My interpretation allows one bond between adjacent molecules; this may provide the configurations you're missing (there are 6 configs with 1 bond, 1 config with 2 bonds, and 1 with 0 bond). I admit this kind of pairings is a bit weird, relative to the chemistry problem... After all, perhaps awkward got it right, I don't know.