Member Avatar for sobam15

This triangle shape full of numbers is the reference I have to use for the first part of a homework problem, but I haven't the slightest clue as to why the rows and columns are indexed starting at zero and what that means in terms of all the other rows.

That being said:

How does P(4,2)=6?

It doesn't make any sense to me.

Note: I used parentheses to make up for the fact that I couldn't type in a small '4' and a small '2'.

Thanks.

-sobam15

  • 2 Contributors
  • 2 Replies
  • 272 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by sobam15

Dani AI

Generated

In standard math notation Pascal's triangle is zero-indexed: P(n,k) means the entry in row n and column k when both are counted from 0. That matches the binomial coefficient definition P(n,k) = C(n,k). Row n therefore has n+1 entries with k running 0..n (see Pascal's triangle and Binomial coefficient).

Why P(4,2) = 6: interpret P(4,2) as "4 choose 2." Combinatorially it counts unordered pairs from a 4-element set; the six pairs are AB, AC, AD, BC, BD, CD. Algebraically C(4,2) = 4!/(2!2!) = 24/(22) = 6, or more simply (43)/(21) = 6. So P(4,2) is 6 because that is the value of the binomial coefficient for n=4, k=2.

How the posted program works (plain language): start with row 0 = [1]. To make the next row, place 1 at each edge and for each interior position add the two numbers that sit above it in the previous row. That rule (C(n,k) = C(n-1,k-1) + C(n-1,k)) is why the code builds row after row and why zero-based indexing is natural. This directly answers and explains what was hinting at about implementing the triangle.

If a single entry is needed without building the whole triangle, an iterative binomial function is simplest and numerically safe:

def comb(n, k):
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)
    res = 1
    for i in range(1, k + 1):
        res = res * (n - k + i) // i
    return res

# comb(4,2) -> 6

Note: if inputs are 1-based, subtract 1 from both row and column before calling the function. For very large n use big-integer support or a library to avoid overflow.

Recommended Answers

All 2 Replies

Member Avatar for KevinADC

Do you have some perl code you need help with?

Member Avatar for sobam15

I've figured out the answer to my previous question, but now have an even bigger problem. The assignment was to create and run a program that can take any column and row then print the corresponding number.

I found this code online. I thinks it's the answer. I don't want the answer. I want to know why and how to do it:

#!/usr/bin/perl

for ($k=0;$k<10;$k++) {
     $pascal[$k] = [];
     push @{$pascal[$k]},1;
     for ($l=1;$l<=$k;$l++) {
        push @{$pascal[$k]},$pascal[$k-1][$l-1]+$pascal[$k-1][$l];
        }
     }

foreach (@pascal) {
        $n_els = @{$_};
        $nsp = 20 - 2 * $n_els;
        $form = (" " x $nsp).("%4d" x $n_els)."\n";
        printf $form, @{$_};
        }

I really need it explained... in absolute layman's terms if it is at all possible.

-sobam15

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.