Counting

> 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 - PLUG-discuss@lists.plug.phoenix.az.us
To subscribe, unsubscribe, or to change you mail settings:
http://lists.PLUG.phoenix.az.us/mailman/listinfo/plug-discuss