//CIS 610-251: Recursion
// Assignment # 3 Question 5
//Due Oct 7,99
//common(n,k)
#include<iostream.h>
/*
Proof:
-----
common(n,k)=common(n-1,k) + common(n-1,k-1)

Lets start with common(4,3)=4
Thus we should get 4 for:
=common(3,3)+common(3,2)
=1+common(2,2)+common(2,1)
=1+1+2
=4
*/


int common(int n, int k)
{
	int i=0;
	if (k>n) return  0;
	if (n==k) return 1;
	if (k==1) return n;
	if (k>1) i=	common(n-1,k) + common(n-1,k-1);
	return i;
}

main()
{
	int commom(int ,int);
	int n, k;
	
	cout << "\nEnter # of people to choose from: " ;
	cin >> n;

	cout << "\nEnter # of persons in one group: ";
	cin >> k;

	cout << "\nPossible Groups= " << common(n,k) << '\n';

	return 0;
}