0
$\begingroup$

Can someone guide me as to how to go about working out a formula for this number triangle:

// ----------------------------------->>> k // n // 1                                                                    0     0 // 2                                                                 1     0     1 // 3                                                              1     0     0     1 // 4                                                           1     0     2     0     1 // 5                                                        1     0     0     0     0     1 // 6                                                     1     0     3     2     3     0     1 // 7                                                  1     0     0     0     0     0     0     1 // 8                                               1     0     4     0     6     0     4     0     1 // 9                                            1     0     0     3     0     0     3     0     0     1 //10                                         1     0     5     0    10     2    10     0     5     0     1 //11                                      1     0     0     0     0     0     0     0     0     0     0     1 //12                                   1     0     6     4    15     0    24     0    15     4     6     0     1 //13                                1     0     0     0     0     0     0     0     0     0     0     0     0     1 //14                             1     0     7     0    21     0    35     2    35     0    21     0     7     0     1 //15                          1     0     0     5     0     3    10     0     0    10     3     0     5     0     0     1 //16                       1     0     8     0    28     0    56     0    70     0    56     0    28     0     8     0     1 //17                    1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     1 //18                 1     0     9     6    36     0    96     0   126    20   126     0    96     0    36     6     9     0     1 //19              1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     1 

It's to do with a programming puzzle I have solved using brute force and am now investigating further. The number triangle was generated by my brute force algorithm, which relates to the number of periodic bitstreams in the possible permutations of a bitstream of length n when there are exactly k corrupt bits.

I know that the sum of the values in a row is given by the function A(n)

where:

A(x) = SUM( B(j) )

where:

j[] = positive divisors of x

where:

B(x) = 2^x - A(x)

where A(1) = 0 and B(1) = 2

What techniques I could use to work out a formula for this ?

  • 1
    At a glance: if you delete every other row and every other entry, you've got Pascal's Triangle. I'm not totally sure what's going on on odd-numbered rows and odd-numbered entries on even-numbered rows (starting numbering from 0).2012-10-09
  • 0
    i thought about that, but the middle part of the triangle gets more complex as you get further down...2012-10-09

1 Answers 1