Chakpak - The destination for bollywood movies, celebrities, wallpapers, videos, news and more...

Friday, January 5, 2007

Problem0006: Odd Combinations

Given a positive integer n, find the number of C(n,r) which are odd, r takes values between 0 and n, inclusive.

If the answer is Odd(n), post the value of Odd(999888777666555444333222111000).

Eg: Odd(1)=2, Odd(2)=2, Odd(3)=4, Odd(4)=2.

Wednesday, December 27, 2006

Problem0005: Swapless Permutations

A permutation of the integers from 1 to n contains a swap if there exist distinct integers i and j between 1 and n such that i appears at the jth position and j appears in the ith postion (the positions in the permutation are numbered from 1 to n). Find the number of permutations of 1 to n which do not contain a swap.

If the solution is SW(n), post the value of SW(17).

Eg: SW(1)=1, SW(2)=1, SW(3)=3, SW(4)=15, SW(5)=75.

Tuesday, December 26, 2006

Problem0004: Sub Permutations

A permutation of the integers 1 to n contains a sub-permutation if there exists a k less than n such that the first k numbers form a permutation of the integers 1 to k. Find the number of permutations of 1 to n which do not contain a sub-permutation.

If the solution is SP(n), post the value of SP(17).

Eg: SP(1)=1, SP(2)=1, SP(3)=3, SP(4)=14, SP(5)=80.

Wednesday, December 20, 2006

Problem0003: Universities

There are n universities(number them from 1 to n) in a country. To help their students, the universities make a pact to exchange thier best professors for a semester. Each university nominates a professor to be exchanged. The constraints are:

a. No professor can stay in his own university.
b. If the university i goes to the university j, the professor from university j cannot go to university i.

The second constraint has been introduced to prevent the universities from forming pairs.

If the solution is U(n), post the value of U(13).

Eg: U(1)=0, U(2)=0, U(3)=2, U(4)=6.

Problem0002: Color the cube

In how many ways can a cube be colored using six colors? All the six faces must have distinct colors( i.e. all the six colors must be used). Two colorings are distint if one configuration cannot be obtained from the other using a rotation of the cube.

Problem0001: Binary Search Trees

What is the number of distinct binary search trees that can be formed using the integers between 1 and n, for a natural number n? The answer should of the form C(p,q) for some integers p and q. Just to make the answer concrete, post the value for n=11.

Binary Search Tree(BST) is a binary tree with the constraint that for every node, all the elements to its left are lesser than the node and all the elements to its right are greater than the node.

Eg: If the answer is BST(n), then BST(1)=1, BST(2)=2, BST(3)=5

Its all about your counting ability!

Hi! This is a blog where I would be posting counting problems. You can rest assured they will be really good. Lets see if you can solve them!