Compute bionomial coefficients

Problem

Design an efficient algorithm for computing c(n, k) that has the property that it never overflows if c(n, k) can be represented as an integer assume n and k are both integers.

Solution

c(n, k) = c(n-1, k) + c(n-1, k-1)

#include <iostream>

#include <iomanip>

using namespace std;

int NChooseK(int n, int k)

{

if (n == k || k == 0)

{

return 1;

}

return NChooseK(n - 1, k) + NChooseK(n - 1, k - 1);

}

int main(int argc, char* argv[])

{

for(int i = 1; i < 30; ++i){

for(int j = 0; j <= i; ++j){

cout << "C(" << setw(2) << left << i << ",";

cout << setw(2) << left << j << ") = ";

cout << setw(10) << right << NChooseK(i, j) << endl;

}

cout << "------------------------------------------" << endl;

}

return 0;

}

Output

C(1 ,0 ) = 1

C(1 ,1 ) = 1

------------------------------------------

C(2 ,0 ) = 1

C(2 ,1 ) = 2

C(2 ,2 ) = 1

------------------------------------------

C(3 ,0 ) = 1

C(3 ,1 ) = 3

C(3 ,2 ) = 3

C(3 ,3 ) = 1

------------------------------------------

C(4 ,0 ) = 1

C(4 ,1 ) = 4

C(4 ,2 ) = 6

C(4 ,3 ) = 4

C(4 ,4 ) = 1

------------------------------------------

C(5 ,0 ) = 1

C(5 ,1 ) = 5

C(5 ,2 ) = 10

C(5 ,3 ) = 10

C(5 ,4 ) = 5

C(5 ,5 ) = 1

------------------------------------------

C(6 ,0 ) = 1

C(6 ,1 ) = 6

C(6 ,2 ) = 15

C(6 ,3 ) = 20

C(6 ,4 ) = 15

C(6 ,5 ) = 6

C(6 ,6 ) = 1

------------------------------------------

C(7 ,0 ) = 1

C(7 ,1 ) = 7

C(7 ,2 ) = 21

C(7 ,3 ) = 35

C(7 ,4 ) = 35

C(7 ,5 ) = 21

C(7 ,6 ) = 7

C(7 ,7 ) = 1

------------------------------------------

C(8 ,0 ) = 1

C(8 ,1 ) = 8

C(8 ,2 ) = 28

C(8 ,3 ) = 56

C(8 ,4 ) = 70

C(8 ,5 ) = 56

C(8 ,6 ) = 28

C(8 ,7 ) = 8

C(8 ,8 ) = 1

------------------------------------------

C(9 ,0 ) = 1

C(9 ,1 ) = 9

C(9 ,2 ) = 36

C(9 ,3 ) = 84

C(9 ,4 ) = 126

C(9 ,5 ) = 126

C(9 ,6 ) = 84

C(9 ,7 ) = 36

C(9 ,8 ) = 9

C(9 ,9 ) = 1

------------------------------------------

C(10,0 ) = 1

C(10,1 ) = 10

C(10,2 ) = 45

C(10,3 ) = 120

C(10,4 ) = 210

C(10,5 ) = 252

C(10,6 ) = 210

C(10,7 ) = 120

C(10,8 ) = 45

C(10,9 ) = 10

C(10,10) = 1

------------------------------------------

C(11,0 ) = 1

C(11,1 ) = 11

C(11,2 ) = 55

C(11,3 ) = 165

C(11,4 ) = 330

C(11,5 ) = 462

C(11,6 ) = 462

C(11,7 ) = 330

C(11,8 ) = 165

C(11,9 ) = 55

C(11,10) = 11

C(11,11) = 1

------------------------------------------

C(12,0 ) = 1

C(12,1 ) = 12

C(12,2 ) = 66

C(12,3 ) = 220

C(12,4 ) = 495

C(12,5 ) = 792

C(12,6 ) = 924

C(12,7 ) = 792

C(12,8 ) = 495

C(12,9 ) = 220

C(12,10) = 66

C(12,11) = 12

C(12,12) = 1

------------------------------------------

C(13,0 ) = 1

C(13,1 ) = 13

C(13,2 ) = 78

C(13,3 ) = 286

C(13,4 ) = 715

C(13,5 ) = 1287

C(13,6 ) = 1716

C(13,7 ) = 1716

C(13,8 ) = 1287

C(13,9 ) = 715

C(13,10) = 286

C(13,11) = 78

C(13,12) = 13

C(13,13) = 1

------------------------------------------

C(14,0 ) = 1

C(14,1 ) = 14

C(14,2 ) = 91

C(14,3 ) = 364

C(14,4 ) = 1001

C(14,5 ) = 2002

C(14,6 ) = 3003

C(14,7 ) = 3432

C(14,8 ) = 3003

C(14,9 ) = 2002

C(14,10) = 1001

C(14,11) = 364

C(14,12) = 91

C(14,13) = 14

C(14,14) = 1

------------------------------------------

C(15,0 ) = 1

C(15,1 ) = 15

C(15,2 ) = 105

C(15,3 ) = 455

C(15,4 ) = 1365

C(15,5 ) = 3003

C(15,6 ) = 5005

C(15,7 ) = 6435

C(15,8 ) = 6435

C(15,9 ) = 5005

C(15,10) = 3003

C(15,11) = 1365

C(15,12) = 455

C(15,13) = 105

C(15,14) = 15

C(15,15) = 1

------------------------------------------

C(16,0 ) = 1

C(16,1 ) = 16

C(16,2 ) = 120

C(16,3 ) = 560

C(16,4 ) = 1820

C(16,5 ) = 4368

C(16,6 ) = 8008

C(16,7 ) = 11440

C(16,8 ) = 12870

C(16,9 ) = 11440

C(16,10) = 8008

C(16,11) = 4368

C(16,12) = 1820

C(16,13) = 560

C(16,14) = 120

C(16,15) = 16

C(16,16) = 1

------------------------------------------

C(17,0 ) = 1

C(17,1 ) = 17

C(17,2 ) = 136

C(17,3 ) = 680

C(17,4 ) = 2380

C(17,5 ) = 6188

C(17,6 ) = 12376

C(17,7 ) = 19448

C(17,8 ) = 24310

C(17,9 ) = 24310

C(17,10) = 19448

C(17,11) = 12376

C(17,12) = 6188

C(17,13) = 2380

C(17,14) = 680

C(17,15) = 136

C(17,16) = 17

C(17,17) = 1

------------------------------------------

C(18,0 ) = 1

C(18,1 ) = 18

C(18,2 ) = 153

C(18,3 ) = 816

C(18,4 ) = 3060

C(18,5 ) = 8568

C(18,6 ) = 18564

C(18,7 ) = 31824

C(18,8 ) = 43758

C(18,9 ) = 48620

C(18,10) = 43758

C(18,11) = 31824

C(18,12) = 18564

C(18,13) = 8568

C(18,14) = 3060

C(18,15) = 816

C(18,16) = 153

C(18,17) = 18

C(18,18) = 1

------------------------------------------

C(19,0 ) = 1

C(19,1 ) = 19

C(19,2 ) = 171

C(19,3 ) = 969

C(19,4 ) = 3876

C(19,5 ) = 11628

C(19,6 ) = 27132

C(19,7 ) = 50388

C(19,8 ) = 75582

C(19,9 ) = 92378

C(19,10) = 92378

C(19,11) = 75582

C(19,12) = 50388

C(19,13) = 27132

C(19,14) = 11628

C(19,15) = 3876

C(19,16) = 969

C(19,17) = 171

C(19,18) = 19

C(19,19) = 1

------------------------------------------

C(20,0 ) = 1

C(20,1 ) = 20

C(20,2 ) = 190

C(20,3 ) = 1140

C(20,4 ) = 4845

C(20,5 ) = 15504

C(20,6 ) = 38760

C(20,7 ) = 77520

C(20,8 ) = 125970

C(20,9 ) = 167960

C(20,10) = 184756

C(20,11) = 167960

C(20,12) = 125970

C(20,13) = 77520

C(20,14) = 38760

C(20,15) = 15504

C(20,16) = 4845

C(20,17) = 1140

C(20,18) = 190

C(20,19) = 20

C(20,20) = 1

------------------------------------------

C(21,0 ) = 1

C(21,1 ) = 21

C(21,2 ) = 210

C(21,3 ) = 1330

C(21,4 ) = 5985

C(21,5 ) = 20349

C(21,6 ) = 54264

C(21,7 ) = 116280

C(21,8 ) = 203490

C(21,9 ) = 293930

C(21,10) = 352716

C(21,11) = 352716

C(21,12) = 293930

C(21,13) = 203490

C(21,14) = 116280

C(21,15) = 54264

C(21,16) = 20349

C(21,17) = 5985

C(21,18) = 1330

C(21,19) = 210

C(21,20) = 21

C(21,21) = 1

------------------------------------------

C(22,0 ) = 1

C(22,1 ) = 22

C(22,2 ) = 231

C(22,3 ) = 1540

C(22,4 ) = 7315

C(22,5 ) = 26334

C(22,6 ) = 74613

C(22,7 ) = 170544

C(22,8 ) = 319770

C(22,9 ) = 497420

C(22,10) = 646646

C(22,11) = 705432

C(22,12) = 646646

C(22,13) = 497420

C(22,14) = 319770

C(22,15) = 170544

C(22,16) = 74613

C(22,17) = 26334

C(22,18) = 7315

C(22,19) = 1540

C(22,20) = 231

C(22,21) = 22

C(22,22) = 1

------------------------------------------

C(23,0 ) = 1

C(23,1 ) = 23

C(23,2 ) = 253

C(23,3 ) = 1771

C(23,4 ) = 8855

C(23,5 ) = 33649

C(23,6 ) = 100947

C(23,7 ) = 245157

C(23,8 ) = 490314

C(23,9 ) = 817190

C(23,10) = 1144066

C(23,11) = 1352078

C(23,12) = 1352078

C(23,13) = 1144066

C(23,14) = 817190

C(23,15) = 490314

C(23,16) = 245157

C(23,17) = 100947

C(23,18) = 33649

C(23,19) = 8855

C(23,20) = 1771

C(23,21) = 253

C(23,22) = 23

C(23,23) = 1

------------------------------------------

C(24,0 ) = 1

C(24,1 ) = 24

C(24,2 ) = 276

C(24,3 ) = 2024

C(24,4 ) = 10626

C(24,5 ) = 42504

C(24,6 ) = 134596

C(24,7 ) = 346104

C(24,8 ) = 735471

C(24,9 ) = 1307504

C(24,10) = 1961256

C(24,11) = 2496144

C(24,12) = 2704156

C(24,13) = 2496144

C(24,14) = 1961256

C(24,15) = 1307504

C(24,16) = 735471

C(24,17) = 346104

C(24,18) = 134596

C(24,19) = 42504

C(24,20) = 10626

C(24,21) = 2024

C(24,22) = 276

C(24,23) = 24

C(24,24) = 1

------------------------------------------

C(25,0 ) = 1

C(25,1 ) = 25

C(25,2 ) = 300

C(25,3 ) = 2300

C(25,4 ) = 12650

C(25,5 ) = 53130

C(25,6 ) = 177100

C(25,7 ) = 480700

C(25,8 ) = 1081575

C(25,9 ) = 2042975

C(25,10) = 3268760

C(25,11) = 4457400

C(25,12) = 5200300

C(25,13) = 5200300

C(25,14) = 4457400

C(25,15) = 3268760

C(25,16) = 2042975

C(25,17) = 1081575

C(25,18) = 480700

C(25,19) = 177100

C(25,20) = 53130

C(25,21) = 12650

C(25,22) = 2300

C(25,23) = 300

C(25,24) = 25

C(25,25) = 1

------------------------------------------

C(26,0 ) = 1

C(26,1 ) = 26

C(26,2 ) = 325

C(26,3 ) = 2600

C(26,4 ) = 14950

C(26,5 ) = 65780

C(26,6 ) = 230230

C(26,7 ) = 657800

C(26,8 ) = 1562275

C(26,9 ) = 3124550

C(26,10) = 5311735

C(26,11) = 7726160

C(26,12) = 9657700

C(26,13) = 10400600

C(26,14) = 9657700

C(26,15) = 7726160

C(26,16) = 5311735

C(26,17) = 3124550

C(26,18) = 1562275

C(26,19) = 657800

C(26,20) = 230230

C(26,21) = 65780

C(26,22) = 14950

C(26,23) = 2600

C(26,24) = 325

C(26,25) = 26

C(26,26) = 1

------------------------------------------

C(27,0 ) = 1

C(27,1 ) = 27

C(27,2 ) = 351

C(27,3 ) = 2925

C(27,4 ) = 17550

C(27,5 ) = 80730

C(27,6 ) = 296010

C(27,7 ) = 888030

C(27,8 ) = 2220075

C(27,9 ) = 4686825

C(27,10) = 8436285

C(27,11) = 13037895

C(27,12) = 17383860

C(27,13) = 20058300

C(27,14) = 20058300

C(27,15) = 17383860

C(27,16) = 13037895

C(27,17) = 8436285

C(27,18) = 4686825

C(27,19) = 2220075

C(27,20) = 888030

C(27,21) = 296010

C(27,22) = 80730

C(27,23) = 17550

C(27,24) = 2925

C(27,25) = 351

C(27,26) = 27

C(27,27) = 1

------------------------------------------

C(28,0 ) = 1

C(28,1 ) = 28

C(28,2 ) = 378

C(28,3 ) = 3276

C(28,4 ) = 20475

C(28,5 ) = 98280

C(28,6 ) = 376740

C(28,7 ) = 1184040

C(28,8 ) = 3108105

C(28,9 ) = 6906900

C(28,10) = 13123110

C(28,11) = 21474180

C(28,12) = 30421755

C(28,13) = 37442160

C(28,14) = 40116600

C(28,15) = 37442160

C(28,16) = 30421755

C(28,17) = 21474180

C(28,18) = 13123110

C(28,19) = 6906900

C(28,20) = 3108105

C(28,21) = 1184040

C(28,22) = 376740

C(28,23) = 98280

C(28,24) = 20475

C(28,25) = 3276

C(28,26) = 378

C(28,27) = 28

C(28,28) = 1

------------------------------------------

C(29,0 ) = 1

C(29,1 ) = 29

C(29,2 ) = 406

C(29,3 ) = 3654

C(29,4 ) = 23751

C(29,5 ) = 118755

C(29,6 ) = 475020

C(29,7 ) = 1560780

C(29,8 ) = 4292145

C(29,9 ) = 10015005

C(29,10) = 20030010

C(29,11) = 34597290

C(29,12) = 51895935

C(29,13) = 67863915

C(29,14) = 77558760

C(29,15) = 77558760

C(29,16) = 67863915

C(29,17) = 51895935

C(29,18) = 34597290

C(29,19) = 20030010

C(29,20) = 10015005

C(29,21) = 4292145

C(29,22) = 1560780

C(29,23) = 475020

C(29,24) = 118755

C(29,25) = 23751

C(29,26) = 3654

C(29,27) = 406

C(29,28) = 29

C(29,29) = 1

------------------------------------------

Press any key to continue . . .