Permutations & Combinations

[proff.hacker]

I have 4 questions and i would be indebted to anyone can help me


1. Find the value of each of the following quantities:
a) C(5,1)
b) C(8,8)
c) C(8,0)
C means Combination

2. How many bit strings of length 10 have:
a) exactly three 0s?
b) the same number of 0s as 1a?
c) at least seven 1s?
d) at least three 1s?

3. Find the cofficient of x^5 y^8 in (x+y)^13.

4. Show that if n is a positive integer, then C(2n,2)=2C(n,2)+n^2
a) by using a combinatorial argument.
b) by algebraic mainpulation.


thanks in advace.

[Guv]

Caveat emptor: I did the following in a hurry.

C(5, 1) = 5
C(8,0) = 1
C(8,8) = 1

You are in trouble if you do not know the above.

C(10, 3) = 120
C(10, 5) = 252
C(10, 7) + C(10, 8) + C(10, 9) + C(10, 10) = 176
2^10 - 176 = 848 (Not 100% sure of this one)

C(13, 5) = C(13, 8) = 1287

via algebraic manipulation..

C(2n, 2) =? 2C(n, 2) + n^2
(2n)!/(2n-2)!2! =? 2n!/(n-2)!2! + n^2
2n(2n-1)/2 =? 2n(n-1)/2 + n^2
n(2n-1) =? n(n-1) + n^2
2n^2 - n =? n^2 - n + n^2
2n^2 - n = 2n^2 - n

?? Via a combinatorial argument.

[thinktank2]

Originally posted by Guv
2. How many bit strings of length 10 have:
d) at least three 1s?

2^10 - 176 = 848 (Not 100% sure of this one)

d)

= C[10,3] + C[10,4] + C[10,5] + .......+ C[10,10]

However there is a simple way to avoid the lengthier calculation.

We know there are 2^10 combinations of Bit strings in total.

So the sum of

C[10,0] + C[10,1] + C[10,2] + C[10,3] + ............+ C[10,10] = 2^10

therefore
C[10,3] + C[10,4] + C[10,5] + ....+ C[10,10]

= 2^10 - ( C[10,2] + C[10,1] + C[10,0] )

= 2^10 - 56 = 968

[Guv]

ThinkTank2: Your answer looks good to me.

[sail3005]

here is a program i made for permutations and combinations.

[proff.hacker]

Thanks very very much everybody

[pablomacri]

Does anyone know or has a code in vb to generate all posible subsets (permutations of n, n-1, n-2 ... 0 items) of a given array?
The number of subsets generated would be 2^n, but what I need to know is the sets generated.
Thanks, Pablo

[kedaman]

actually you get different count of subsets depending on homogenity in the array. for instance 1337 gives 1C4 2C3 1C1=24