Subject: Counting

From: Alex LeDonne <[email-masked]>
Date: Fri, 4 Mar 2005 13:47:47 -0800 (PST)

> Question:
> 
> For a given item n in the sequence N, how many parity number
> combinations will 
> occur in the resulting set of all modulo 2^(2n) binary
> representations?  (How 
> many parity combinations for a given item N?)

Trent-

Another way to ask the question: Given 2k slots, how many distinct ways
can they be filled with exactly k 0s and k 1s?

The answer is: 2k choose k (The number of ways to select k items out of
2k). You choose k to be 0, the rest must be 1. I don't have OOo in
front of me... I can tell you that in MS Excel, the formula is
=COMBIN(n,k) .

The general formula for n choose k is

                            n!
                        -----------
                         k! (n-k)!

In your case, it's 

                           (2k)!
                         ----------
                               2
                           (k!) 
which reduces to 

                 2k (2k-1) (2k-2) ... (k+2) (k+1)
                ---------------------------------
                               k!

For example, for your k=4 case, the number is 8*7*6*5 / 4*3*2*1 = 70.

> Is number of binary parities bounded underneath by 2^(2[n-1]) for all
> N?
> 
No. For k=5, 2k choose k = 252, 2^(2*4) = 256; similarly for k>5 the
exponential term grows faster.

Thanks - it had been a while since I actually used some combinatorics.

-Alex

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
---------------------------------------------------
PLUG-discuss mailing list - [email-masked]
To subscribe, unsubscribe, or to change  you mail settings:
http://lists.PLUG.phoenix.az.us/mailman/listinfo/plug-discuss