CareerCup

This is a bit too mathematical...
choosing 1 from n is nC1
choosing 2 from n is nC2
choosing 3 from n is nC3... till
choosing n from n is nCn
each combination should be added to get the total no of possible formations
nC1+nC2+...+nCn

(without going into the derivation its known that) nC0+nC1+...+nCn=2^n

nC0=1

therefore
nC1+nC2+...+nCn=(2^n)-nC0

so, nC1+nC2+...+nCn=(2^n)-1

using a program to solve this,
Note: it also prints out the combination

public class Com1ToN
{
    static int count;

    public static void main(String[] args)
    {

        count = 0;

        System.out.print("Enter N : ");
        int n = (new Scanner(System.in)).nextInt();

        for (int i = 0; i < n; i++)
            print(1, n, i, "");

        System.out.println("The count is : " + count);

    }

    private static void print(int s, int n, int lvl, String pre)
    {
        if (lvl == 0)
            for (int i = s; i <= n; i++) {
                System.out.println(pre + i);
                count++;
            }
        else
            for (int i = s; i <= n - lvl; i++)
                print(i + 1, n, lvl - 1, pre + i + " ");
    }

}

If we assume that every pearl is unique in their magnificence we can say that adding the nth pearl to our set will let us create all the necklaces that does not have it f(n-1) + all those combinations with the new pearl + one necklace that is just the new pearl. Thus we get f(n) = 2*f(n-1) + 1. And f(1) = 1.

If we assume that there are multiple pearls with the same magnificence value but are otherwise identical then we can break the problem down into progressively adding pearls of a new level of magnificence. If there are x[i] pearls of i magnificence then we can add between 0 and x[i] pearls to all the necklaces we had when only considering the necklaces with inferior quality. And all the new necklaces with just the pearls of magnificence i . So we get f(i) = f(i-1) * (x[i] + 1) + x[i]. where f(0) = x[0]

If all the pearls are unique but some have the same level of magnificence then we need to consider all the ways we can add each set of pearls of the same magnificence. Each sub necklace consists of from 1 to x[i] pearls and each of these can have m! was to be arranged where m is the length of the necklace. For this we get SUM(m = 1 to x[i], m!)
f(i) = f(i-1) * (SUM(m = 1 to x[i], m!)+ 1) + SUM(m = 1 to x[i], m!). where f(0) = SUM(m = 1 to x[0], m!)

very good program...... thank you