Let's say in general you want "n" adjacent squares. Each one needs a top, so that's n toothpicks. Each one needs a bottom, so that's another n toothpicks, and we're up to 2n total. You need one on the far left, and one on the far right, which brings us up to 2n + 2 toothpicks. Now we need to worry about the middle ones. But notice that you don't need n toothpicks for the interior because adjacent squares share. It turns out that you only need n-1. That brings us up to a grand total of 3n + 1 toothpicks, which would be 3001 for n = 1000.
C r = (n!)/(r!(n-r)!) 9 C 3 = (9!)/(3!*(9-3)!) 9 C 3 = (9!)/(3!*6!) 9 C 3 = (9*8*7*6!)/(3!*6!) 9 C 3 = (9*8*7)/(3!) 9 C 3 = (9*8*7)/(3*2*1) 9 C 3 = (504)/(6) 9 C 3 = 84
