CALCULATING DROP PACKETS IN NS2,

BEGIN {

    packet_lost3 = 0;
    packet_lost1=0;
    packet_lost2=0;
    packet_lost_total=0;
    total_throughput = 0
    final = 0
    time_ini = 0.0
    count = 0
}
{
    ackn = $5
    event = $1
   
    time = $2
    node = 0
    flowid= $8
    from_node = $3
    to_node= $4 #from node should be 2
    source = $9
    dest= $10
    #I HAVE THREE SOURCES SO I USED THREE PACKET LOSTS       #print(time)
    #print(flowid)
    #print(from_node)
    if(event  == "d"  && source ="0.0" && dest == "11.0") {
       
        packet_lost3 = packet_lost3+1;
        }
    if(event  == "d"  && source ="2.0" && dest == "11.2") {
       
        packet_lost2 = packet_lost2+1;
        }
    if(event  == "d"  && source ="1.0" && dest == "11.1") {
       
        packet_lost1 = packet_lost1+1;
        }
   
}


END {
        print("*******************")
        print("packet drop on source 1 : " , packet_lost1)
        print("*******************")
        print("packet drop on source  2: " , packet_lost2)
        print("*******************")
        print("packet drop on source 3 : " , packet_lost3)
#TOTAL LOST COUNT
        packet_lost_total = packet_lost1+packet_lost2+packet_lost3;
        print("*******************")
        print("Total packet drop= : " , packet_lost_total)
        print("*******************")



}



#save this file as .awk file ex = packet_lost.awk then run for any trace file which is in output of any tcl file in ns2.
# then run the following command in terminal

awk -f "packet_lost.awk" out.tr  

#replace out.tr with your out put file name and change the source and dest in awk file according to your trace file.

TWO TCP ONE UDP CONNECTION IN NS2....

#Create a simulator object
set ns [new Simulator]

#Define different colors for data flows (for NAM)
$ns color 1 Blue
$ns color 2 Red
$ns color 3 black


#Open the NAM trace file
set nf [open out.nam w]
$ns namtrace-all $nf

set ne [open out.tr w]
$ns trace-all $ne

#Define a 'finish' procedure
proc finish {} {
        global ns nf ne
        $ns flush-trace
        #Close the NAM trace file
        close $nf
     close $ne
        #Execute NAM on the trace file
        exec nam out.nam
        exec xgraph out.tr -geometry 1300x768 &
        exit 0
}

#Create four nodes
set a1 [$ns node]
set a2 [$ns node]
set a3 [$ns node]
set r1 [$ns node]
set r2 [$ns node]
set r3 [$ns node]
set r4 [$ns node]
set r5 [$ns node]
set r6 [$ns node]
set r7 [$ns node]
set r8 [$ns node]
set v [$ns node]


#Create links between the nodes
$ns duplex-link $a1 $r1 4Mb 1ms DropTail
$ns duplex-link $a2 $r2 2Mb 1ms DropTail
$ns duplex-link $a3 $r3 2Mb 2ms DropTail
$ns duplex-link $r1 $r4 4Mb 1ms DropTail
$ns duplex-link $r2 $r5 2Mb 1ms DropTail
$ns duplex-link $r3 $r6 2Mb 2ms DropTail
$ns duplex-link $r4 $r7 4Mb 1ms DropTail
$ns duplex-link $r5 $r7 2Mb 15ms DropTail
$ns duplex-link $r6 $r8 2Mb 20ms DropTail
$ns duplex-link $r7 $v 0.7Mb 10ms SFQ
$ns duplex-link $r8 $v 0.7Mb 15ms SFQ

# --------------LABELLING -----------------------------#

$ns at 0.0 "$a1 label a1"
$ns at 0.0 "$a2 label a2"
$ns at 0.0 "$a3 label a3"
$ns at 0.0 "$r1 label r1"
$ns at 0.0 "$r2 label r2"
$ns at 0.0 "$r3 label r3"
$ns at 0.0 "$r4 label r4"
$ns at 0.0 "$r5 label r5"
$ns at 0.0 "$r6 label r6"
$ns at 0.0 "$r7 label r7"
$ns at 0.0 "$r8 label r8"
$ns at 0.0 "$v label v"

#Set Queue Size of link (n2-n3) to 10
$ns queue-limit $r1 $r4 20
$ns queue-limit $r2 $r5 20
$ns queue-limit $r3 $r6 20
$ns queue-limit $r4 $r7 20
$ns queue-limit $r5 $r7 20
$ns queue-limit $r6 $r8 20
$ns queue-limit $v $r7 10
$ns queue-limit $v $r8 20

#Give node position (for NAM)
$ns duplex-link-op $v $r7 orient left-up
$ns duplex-link-op $v $r8 orient left-down
$ns duplex-link-op $r7 $r4 orient left-up
$ns duplex-link-op $r7 $r5 orient left-down
$ns duplex-link-op $r4 $r1 orient left
$ns duplex-link-op $r5 $r2 orient left
$ns duplex-link-op $r1 $a1 orient left-up
$ns duplex-link-op $r2 $a2 orient left
$ns duplex-link-op $r8 $r6 orient left-down
$ns duplex-link-op $r6 $r3 orient left
$ns duplex-link-op $r3 $a3 orient left

#Monitor the queue for link (n2-n3). (for NAM)
$ns duplex-link-op $r4 $r7 queuePos 0.5
$ns duplex-link-op $r5 $r7 queuePos 0.5
$ns duplex-link-op $r7 $v  queuePos 0.5
$ns duplex-link-op $r8 $v  queuePos 0.5


#Setup a TCP connection 1
set tcp [new Agent/TCP]
$tcp set class_ 2
$ns attach-agent $a1 $tcp
set sink [new Agent/TCPSink]
$ns attach-agent $v $sink
$ns connect $tcp $sink
$tcp set fid_ 1

#Setup a FTP over TCP connection
set ftp1 [new Application/FTP]
$ftp1 attach-agent $tcp
$ftp1 set type_ FTP

#Setup a TCP connection 1
set tcp [new Agent/TCP]
$tcp set class_ 2
$ns attach-agent $a2 $tcp
set sink [new Agent/TCPSink]
$ns attach-agent $v $sink
$ns connect $tcp $sink
$tcp set fid_ 2

#Setup a FTP over TCP connection
set ftp2 [new Application/FTP]
$ftp2 attach-agent $tcp
$ftp2 set type_ FTP


#Setup a UDP connection
set udp [new Agent/UDP]
$ns attach-agent $a3 $udp
set null [new Agent/Null]
$ns attach-agent $v $null
$ns connect $udp $null
$udp set fid_ 3

#Setup a CBR over UDP connection
set cbr [new Application/Traffic/CBR]
$cbr attach-agent $udp
$cbr set type_ CBR
$cbr set packet_size_ 1000
$cbr set rate_ 1mb
$cbr set random_ false


proc record {} {
        global sink0 sink1 sink2 f0 f1 f2
    #Get an instance of the simulator
    set ns [Simulator instance]
    #Set the time after which the procedure should be called again
        set time 0.5
    #How many bytes have been received by the traffic sinks?
        set bw0 [$sink0 set bytes_]
        set bw1 [$sink1 set bytes_]
        set bw2 [$sink2 set bytes_]
    #Get the current time
        set now [$ns now]
    #Calculate the bandwidth (in MBit/s) and write it to the files
        puts $f0 "$now [expr $bw0/$time*8/1000000]"
        puts $f1 "$now [expr $bw1/$time*8/1000000]"
        puts $f2 "$now [expr $bw2/$time*8/1000000]"
    #Reset the bytes_ values on the traffic sinks
        $sink0 set bytes_ 0
        $sink1 set bytes_ 0
        $sink2 set bytes_ 0
    #Re-schedule the procedure
        $ns at [expr $now+$time] "record"
}


#Schedule events for the CBR and FTP agents
$ns at 0.1 "$cbr start"
$ns at 1.0 "$ftp2 start"
$ns at 0.5 "$ftp1 start"
$ns at 4.0 "$ftp2 stop"
$ns at 4.0 "$ftp1 stop"
$ns at 4.5 "$cbr stop"

#Detach tcp and sink agents (not really necessary)
$ns at 4.5 "$ns detach-agent $a1 $tcp ; $ns detach-agent $v $sink"
$ns at 4.5 "$ns detach-agent $a2 $tcp ; $ns detach-agent $v $sink"

#Call the finish procedure after 5 seconds of simulation time
$ns at 5.0 "finish"

#Print CBR packet size and interval
puts "CBR packet size = [$cbr set packet_size_]"
puts "CBR interval = [$cbr set interval_]"

#Run the simulation
$ns run

EXPONENTIAL BURST TRAFFIC USING NS2

#Create a simulator object
set ns [new Simulator]

#Define different colors for data flows (for NAM)
$ns color 1 Blue
$ns color 2 Red
$ns color 3 black

#Open the output files
set f0 [open out0.tr w]
set f1 [open out1.tr w]
set f2 [open out2.tr w]


#Define different colors for data flows (for NAM)
$ns color 1 Blue
$ns color 2 Red
$ns color 3 black

#Open the NAM trace file
set nf [open out.nam w]
$ns namtrace-all $nf

set ne [open out.tr w]
$ns trace-all $ne

#Define a 'finish' procedure
proc finish {} {
        global ns nf ne f0 f1 f2
        $ns flush-trace
        #Close the NAM trace file
        close $nf
     close $ne
    close $f0
    close $f1
    close $f2
        #Execute NAM on the trace file
        exec nam out.nam
        exec xgraph out0.tr out1.tr out2.tr -geometry 800x400 &
        exit 0
}

#Create four nodes
set a1 [$ns node]
set a2 [$ns node]
set a3 [$ns node]
set r1 [$ns node]
set r2 [$ns node]
set r3 [$ns node]
set r4 [$ns node]
set r5 [$ns node]
set r6 [$ns node]
set r7 [$ns node]
set r8 [$ns node]
set v [$ns node]


#Create links between the nodes
$ns duplex-link $a1 $r1 4Mb 1ms DropTail
$ns duplex-link $a2 $r2 2Mb 1ms DropTail
$ns duplex-link $a3 $r3 2Mb 2ms DropTail
$ns duplex-link $r1 $r4 4Mb 1ms DropTail
$ns duplex-link $r2 $r5 2Mb 1ms DropTail
$ns duplex-link $r3 $r6 2Mb 2ms DropTail
$ns duplex-link $r4 $r7 4Mb 1ms DropTail
$ns duplex-link $r5 $r7 2Mb 15ms DropTail
$ns duplex-link $r6 $r8 2Mb 20ms DropTail
$ns duplex-link $r7 $v 0.7Mb 10ms SFQ
$ns duplex-link $r8 $v 0.7Mb 15ms SFQ

# --------------LABELLING -----------------------------#

$ns at 0.0 "$a1 label a1"
$ns at 0.0 "$a2 label a2"
$ns at 0.0 "$a3 label a3"
$ns at 0.0 "$r1 label r1"
$ns at 0.0 "$r2 label r2"
$ns at 0.0 "$r3 label r3"
$ns at 0.0 "$r4 label r4"
$ns at 0.0 "$r5 label r5"
$ns at 0.0 "$r6 label r6"
$ns at 0.0 "$r7 label r7"
$ns at 0.0 "$r8 label r8"
$ns at 0.0 "$v label v"

#Set Queue Size of link (n2-n3) to 10
$ns queue-limit $r1 $r4 20
$ns queue-limit $r2 $r5 20
$ns queue-limit $r3 $r6 20
$ns queue-limit $r4 $r7 20
$ns queue-limit $r5 $r7 20
$ns queue-limit $r6 $r8 20
$ns queue-limit $v $r7 10
$ns queue-limit $v $r8 20

#Give node position (for NAM)
$ns duplex-link-op $v $r7 orient left-up
$ns duplex-link-op $v $r8 orient left-down
$ns duplex-link-op $r7 $r4 orient left-up
$ns duplex-link-op $r7 $r5 orient left-down
$ns duplex-link-op $r4 $r1 orient left
$ns duplex-link-op $r5 $r2 orient left
$ns duplex-link-op $r1 $a1 orient left-up
$ns duplex-link-op $r2 $a2 orient left
$ns duplex-link-op $r8 $r6 orient left-down
$ns duplex-link-op $r6 $r3 orient left
$ns duplex-link-op $r3 $a3 orient left

#Monitor the queue for link (n2-n3). (for NAM)
$ns duplex-link-op $r4 $r7 queuePos 0.5
$ns duplex-link-op $r5 $r7 queuePos 0.5
$ns duplex-link-op $r7 $v  queuePos 0.5
$ns duplex-link-op $r8 $v  queuePos 0.5


proc attach-expoo-traffic { node sink size burst idle rate } {
    #Get an instance of the simulator
    set ns [Simulator instance]

    #Create a UDP agent and attach it to the node
    set source [new Agent/UDP]
    $ns attach-agent $node $source

    #Create an Expoo traffic agent and set its configuration parameters
    set traffic [new Application/Traffic/Exponential]
    $traffic set packetSize_ $size
    $traffic set burst_time_ $burst
    $traffic set idle_time_ $idle
    $traffic set rate_ $rate
       
        # Attach traffic source to the traffic generator
        $traffic attach-agent $source
    #Connect the source and the sink
    $ns connect $source $sink
    return $traffic
}


proc record {} {
        global sink0 sink1 sink2 f0 f1 f2
    #Get an instance of the simulator
    set ns [Simulator instance]
    #Set the time after which the procedure should be called again
        set time 0.5
    #How many bytes have been received by the traffic sinks?
        set bw0 [$sink0 set bytes_]
        set bw1 [$sink1 set bytes_]
        set bw2 [$sink2 set bytes_]
    #Get the current time
        set now [$ns now]
    #Calculate the bandwidth (in MBit/s) and write it to the files
        puts $f0 "$now [expr $bw0/$time*8/1000000]"
        puts $f1 "$now [expr $bw1/$time*8/1000000]"
        puts $f2 "$now [expr $bw2/$time*8/1000000]"
    #Reset the bytes_ values on the traffic sinks
        $sink0 set bytes_ 0
        $sink1 set bytes_ 0
        $sink2 set bytes_ 0
    #Re-schedule the procedure
        $ns at [expr $now+$time] "record"
}

#Create three traffic sinks and attach them to the node n4
set sink0 [new Agent/LossMonitor]
set sink1 [new Agent/LossMonitor]
set sink2 [new Agent/LossMonitor]
$ns attach-agent $v $sink0
$ns attach-agent $v $sink1
$ns attach-agent $v $sink2

#Create three traffic sources
set source0 [attach-expoo-traffic $a1 $sink0 2000 2s 1s 1000k]
set source1 [attach-expoo-traffic $a2 $sink1 2000 2s 1s 2000k]
set source2 [attach-expoo-traffic $a3 $sink2 2000 2s 1s 3000k]


#Start logging the received bandwidth
$ns at 0.0 "record"
#Start the traffic sources
$ns at 10.0 "$source0 start"
$ns at 10.0 "$source1 start"
$ns at 10.0 "$source2 start"
#Stop the traffic sources
$ns at 50.0 "$source0 stop"
$ns at 50.0 "$source1 stop"
$ns at 50.0 "$source2 stop"
#Call the finish procedure after 60 seconds simulation time
$ns at 60.0 "finish"




#Run the simulation
$ns run

Reading Input using BufferReader and Readline classes.

import java.io.*;
public class Main
{
 public static void main(String [] args)
{
try
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int testCount = Integer.parseInt(in.readLine());
for (int test = 0; test < testCount; test++)
{
int m,n;
String[] str = in.readLine().split("");
m = Integer.parseInt(str[0]);
n = Integer.parseInt(str[1]);
}

}
}
catch (IOException e)
{}
System.out.println("hi bhupi");
}
}

installing ns2 in ubuntu 11.10...

hi all this is i found when installing ns2 and its really helpful so i am sharing with you guys..

1. Install ubuntu

2. Download the Ns-2.35 from this website http://isi.edu/nsnam/ns/

3. Assuming that your ns-2.35 source is in the /home/loginname/ , execute the commands one by one

sudo apt-get update

sudo apt-get install automake autoconf libxmu-dev build-essential

tar zxvf ns-allinone-2.35.tar.gz

cd ns-allinone-2.35

./install

4. Once the process is over, it will give the set of paths to be set.

5. Go to terminal and open .bashrc by giving this command

gedit .bashrc

and copy the following lines ( my login name for linux is pradeep, you can change yours accordingly)

export PATH=$PATH:/home/ns-allinone-2.35/bin:/home/pradeep/ns-allinone-2.35/tcl8.5.10/unix:/home/ns-allinone-2.35/tk8.5.10/unix
export LD_LIBRARY_PATH=/home/ns-allinone-2.35/otcl-1.14:/home/pradeep/ns-allinone-2.35/lib

6. run the command “source .bashrc” (without quotes)

and then type ns (a % symbol indicates the successful installation of ns2) or nam (you can see a network animation windows popped out)

TWO STACKS IN ONE ARRAY IN C CODE

#include<stdio.h>
#define MAX 10
int top1 = -1;
int top2 = MAX;
int a[MAX];
void push(int e,int s);
int pop(int s);

int main()
{
    int n ,e,s;
    do
    {
        printf("\n enter choice \n 1 for push \n 2 for pop \n 3 for exit \n  ");
        scanf("%d",&n);
        switch(n)
        {
            case 1:
            {
                printf("\n choose the stack 1 or 2 \n");
                scanf("%d",&s);
                printf("\n enter the element \n");
                scanf("%d",&e);
                push(e,s);
                break;
            }
            case 2:
            {
             int e;
             printf("\n enter your stack preffrence 1 or 2 ");
             scanf("%d",&s);
             e = pop(s);
             if(e != -1)
             {
                 printf("\n the pop element = %d \n",e);
             }
             break;
            }
            default:
            printf("\n enter the correct choice \n");
        }
    }while(n!=3);
}
int pop(int s)
{
    int temp;
    if(s==1)
    {
        if(top1==-1)
        {
            printf("stack 1 is empty \n");
            return -1;
        }
        else
        {
            temp = a[top1];
            top1--;
           return temp;
        }
   }
else
{
    if(top1==MAX)
        {
            printf("stack 2 is empty \n");
            return -1;
        }
        else
        {
            temp = a[top2];
            top2++;
           return temp;
        }
}
}
void push(int e,int s)
{
    if(top1==top2)
        {
            printf("\n the queue is full");
            return;
        }
    else
  {
    if(s==1)
    {
        top1++;
        a[top1]=e;
        printf("\n element inserted in stack 1 \n");
    }
  else
 {
     top2--;
     a[top2]==e;
     printf("\n element inserted into stack 2 \n ");

  }
    }

}

CIRCULAR QUEUE IN C USING ARRAY

#include<stdio.h>

#define MAX 10
int front=-1;
int rear = 0;
int a[MAX];
void enqueue(int e);
int dequeue();

int main()
{
    int n,m,e;
    do
{
  printf(" \n press a key \n 1 for enque \n 2 for dequeue \n 3 to exit \n ");
  scanf("%d",&n);
  switch(n)
  {

  case 1 :
  {
      printf("\n enter no to be entered");
      scanf("%d",&e);
      enqueue(e);
      break;
  }
  case 2:
  {
      int e;
      e = dequeue();
      if(e!= -1)
      {
      printf("the dequed no is = %d",e);
      }
      break;
  }
  default :
  printf("\n you made the wrong choice");
  }
}while(n!=3);

}
void enqueue(int e)
{

    if(front == rear+1)
    printf("\n the queue is full sorry ");

    else
    {
        a[rear]= e;
        rear = (rear+1)%MAX;
        if(front== -1)
         front++;
    }
}
int dequeue()
{
    int temp;
    if(front == rear)
    {
    printf("\n queue is empty");
    return -1;
    }
    else
    {
        temp = a[front];
        front = (front+1)%MAX;
        return temp;
    }
}

SHELL SORT IN C

#include<stdio.h>
#include<math.h>
void shell_sort(int n, int a[n]);
int n;
int main()
{
    int i , j;
    printf("\n enter no of elements \n ");
    scanf("%d",&n);
    int a[n];
    printf("\n enter elements");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    shell_sort(n,a);


    return 0;
}
void shell_sort(int n,int a[])
{
    int i,j,x,count,gap,temp;
    gap = ceil(n/2);
    while(gap)
    {
        for(i=gap;i<n;i++)
        {
            x = a[i];
            for(j=i-gap;j>=0 ; j=j-gap)
            {
                if(a[j]>x)
                {
                temp = a[j];
                a[j]= a[j+gap];
                a[j+gap]= temp;
                }
                else
                break;
            }
        }
        gap = ceil(gap/2);
    }
     for(i=0;i<n;i++)
    {
        printf("\n %d",a[i]);
    }
}

NO OF BINARY SEARCH TREE POSSIBLE ON NODES IN C

/* following prog. takes no of elements as input and return no of possible BST on that number */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

 long int bst(long int a);
 long int BST[100];
 //array to store solutions of subproblems.assume that n should less the 100 here.
 //you can increase this value.
 long int n;

 int main()
{
int i;
long int total;
printf("\n enter no. of elements = \n");//take the no for which u want to calculate no of BST.
scanf("%ld",&n);
//initial set all subproblems sol. to 0.
 for (i=2;i<=n-1;i++)
 BST[i]=0;

BST[0]= 1;//set no of BST for nodes 1,0, equal 1.
BST[1] = 1;

//pass the value to function bst.
total = bst(n);
//total holds the final result

printf("\n the possible no of binary search tree on %ld elements is %ld",n,total);
return 0;
}

long int bst(long int a)
{
    int i;long int count;
//if no_of elements 0 or 1 return 1.
    if(a == 0 || a == 1 )
    return 1;
//if solution of subproblem is there return the value.
   else if(BST[a] != 0)
   return BST[a];

  else
 {
      count=0;
  for (i=1;i<=a;i++)
 {
     //choose 1 to n roots at one time then call for both subtrees left and right recursivley.
  count= count+ bst(i-1)*bst(a-i);
  printf(" \n the count is  on nodes is = %ld \n",count);
 }
 BST[a]=count;
 return count;


  }
}

MINIMUM QUEENS ON CHESS BOARD

       HOW TO COVER 8*8 GRID WITH MINIMUM QUEENS

hash collition

Calculating the Probability of a Hash Collision

There are many choices of hash function, and the creation of a good hash function is still an active area of research. Some hash functions are fast; others are slow. Some distribute hash values evenly across the available range; others don’t. If you’re interested in the real-world performance of a few known hash functions, Charles Bloom and strchr.com offer some comparisons. For our purposes, let’s assume the hash function is pretty good — it distributes hash values evenly across the available range.
In this case, generating hash values for a collection of inputs is a lot like generating a collection of random numbers. Our question, then, translates into the following:

Given randomly generated values, where each value is a non-negative integer less than , what is the probability that at least two of them are equal?

It turns out it’s actually a bit simpler to start with the reverse question: What is the probability that they are all unique? Whatever the answer to the reverse question, we can just subtract it from one, and we’ll have the answer to our original question.
Given a space of possible hash values, suppose you’ve already picked a single value. After that, there are remaining values (out of a possible ) that are unique from the first. Therefore, the probability of randomly generating two integers that are unique from each other is .
After that, there are remaining values (out of a possible ) that are unique from the first two, which means that the probability of randomly generating three integers that are all unique is . (We can multiply the probabilities together because each random number generation is an independent event.)
In general, the probability of randomly generating integers that are all unique is:

On a computer, this can be quite slow to evaluate for large k. Luckily, the above expression is approximately equal to:

which is a lot faster to compute. How do we know this is a good approximation? Well, it can be shown analytically, using the Taylor expansion of and an epsilon-delta proof, that the approximation error tends to zero as increases. Or, you can just compute both values and compare them. Run the following Python script with different , and you’ll get a feeling for just how accurate the approximation is:

import math
N = 1000000
probUnique = 1.0
for k in xrange(1, 2000):
    probUnique = probUnique * (N - (k - 1)) / N
    print k, 1 - probUnique, 1 - math.exp(-0.5 * k * (k - 1) / N)

Great, so this magic expression serves as our probability that all values are unique. Subtract it from one, and you have the probability of a hash collision:

Here is a graph for . This illustrates the probability of collision when using 32-bit hash values. It’s worth noting that a 50% chance of collision occurs when the number of hashes is 77163. Also note that the graph takes the same S-curved shape for any value of .

NO OF BST POSSIBLE ON N NUMBERS??

THIS MAY HELP!!!

the number of binary search trees with n nodes, C(n), is the nth Catalan number. Here's why:

Consider the integers 1, 2, ..., n. The number of trees with root k is C(k-1)C(n-k), because there are k-1 integers below k and n-k above k. Then the total is found by adding these up for k from 1 to n:

C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0)

with the trivial cases given by C(0)=1 and C(1)=1.