10.26.2009

Combinatorics Difficulties (redux)

Thanks to Don's comment, I was able to continue investigating this interesting problem.

Don pointed out that the series I was working on matched the diagonal numbers in Pascal's triangle. These can be obtained as binomial coefficients using the following choose function.

$\bg_white \120dpi \binom{n+k}{k} = \frac{(n+k)!}{k! \cdot n!}$

Adapting this function to produce the diagonal series in Pascal's triangle was trivial. The following code was written using PERL.

#!/usr/bin/perl -s
#
# FILENAME: k-1s_n-0s.pl
# DESCRIPTION: Produces binomial coefficients from the diagonal series of
# Pascal's triangle.
#
# LAST UPDATE: 20091026 - First version.
#

if (@ARGV == 0) {
print "Usage: ts_combos.pl <nth_term> <row>\n\n";
exit;
}

sub factorial {
my $n = 1; my$max = shift;
for my $i (2..$max) {
$n *=$i;
}
return $n; } sub n_choose_k { my$n = shift;
my $k = shift; return &factorial($n) / ( &factorial($k) * &factorial($n - $k) ); } my$max_n = $ARGV[0]; my$k = $ARGV[1] - 1; my$sum_nCr = 1;

print "1";
for (my $n = 1;$n < $max_n;$n++) {
my $nCr = &n_choose_k($n + $k,$k);
$sum_nCr +=$nCr;
print " +\n$nCr"; } print " =$sum_nCr\n";
exit

Unfortunately, this script doesn't do the one thing it was originally meant to, and that's determining the number of steps required to isolate a physical issue. The output only makes sense when all available "cables" are of the same type. Assuming each cable is unique, the number of steps is simply $\bg_white \120dpi \inline 2^{u-1}$, where u is the number of cables.

Incorporating this into $\bg_white \80dpi \inline \binom{n+k}{k}$, we find that, given any number of unique cables, u, and any number of non-unique cables, n,

$\bg_white \120dpi C = \frac{(2n)!}{2n!} + 2^{u-1}$

where C represents the total number of combinations.

While looking for images of Pascal's triangle, I stumbled upon Phil Haack's blog post on triangular numbers. Though Phil's post only discusses one of the diagonal series, I always find it fascinating how such a specific problem can be independently "discovered," investigated, solved and adapted in so many different ways with equal rigor. Truly the method of science and the language of mathematics are universal in every sense.

AFTERTHOUGHT - In case you hadn't noticed that the LaTeX equations were clickable, they come from the CodeCogs.com Online LaTeX Equation Editor.