# Number triangle

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 ?

-
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). –  GMB Oct 9 '12 at 20:58
i thought about that, but the middle part of the triangle gets more complex as you get further down... –  Pooky Oct 9 '12 at 21:25

It's a bit difficult to quantify this pattern, but I think I have more or less isolated it. Let us label the triangle with rows as you've indicated. For each row we will label the "columns" starting from $0$ to the left.

I will define a sequence of successive functions which fill up the triangle. $f_i(x,\ y)$ will denote the entry of row $x$ and column $y$.

Firstly, the triangle starts filling out with a copy of the Pascal's triangle $$f_1(2n,2k) = \binom{n}{k}$$ Then it repeats the triangle, instead now we have $$f_2(3n,\ 3k) = \binom{n}{k}$$ But the entries of $f_2$ must not override the entries of $f_1$. Therefore we require $2\nmid n$ or $2\nmid k$. We continue in this fashion with $$f_3(5n,\ 5k) = \binom{n}{k}$$ Again, the entries of $f_3$ cannot override those of $f_1$ or $f_2$. So we require $2\nmid n$ or $2\nmid k$ and $5\nmid n$ or $5\nmid k$.

This pattern continues through all the prime numbers. For the $i$th prime, we will have $$f_i(p_in,\ p_ik) = \binom{n}{k}$$ where for each $p_j$ with $j<i$ we must have $p_j\nmid n$ or $p_j\nmid k$.

I haven't had time to analyze this further. If there is a more eloquent way of expressing triangle (perhaps using modular arithmetic, I'm not too sure) then that would probably be simpler. Note that this already account for some of the behavior of the triangle. The fact that all the prime numbered rows are empty is because of this fact.

p.s. I hope the $24$ in the middle of row $12$ is actually a $20$. Otherwise there would be a problem.

Edit: Silly me. The following would characterize it much nicer.

Let $p$ be the smallest prime common to both $n$ and $k$. If there is no such prime, then the entry is $0$. Otherwise $$f(n,\ k) = \binom{\frac{n}{p}}{\frac{k}{p}}$$ I will leave the verbose explanation above. That's the steps I took to arrive at this answer, so it might be helpful to you.

-
it is meant to be 24, sorry XD –  Pooky Oct 10 '12 at 7:48
A(12) = B(6) + B(4) + B(3) + B(2) + B(1) = 76 = 1 + 6 + 4 + 15 + 25 + 15 + 4 + 6 + 1 –  Pooky Oct 10 '12 at 7:50
@Pooky Too bad I guess. The pattern does fit for every other number (I think. It worked for everything I checked anyways). Good luck then. –  EuYu Oct 10 '12 at 13:14