# Need help in determining where this pascal's triangle-like sequence comes from.

I have a very interesting problem in that a program that I am running has generated a sequence of numbers that act like the pascal's triangle but have somehow built more structure into it. I have been puzzling over this for a while now and cant figure out how the sequence works. I have put it half the triangle up to n = 14 so the whole thing should look like:

1

1 2 1

1 3 3 1

... etc... so notice that the numbers contained within the brackets add up to the right number for the triangle, for n = 4, (2 4) add to 6 and so on. I'm hoping that someone might know where this sequence comes from or how to generalize this solution so that I can calculate the numbers in the triangle for every n.

Thanks!

(1)

(2) (1)

(3) (1)

(2 4) (4) (1)

(5 5) (5) (1)

(2 6 12) (6 9) (6) (1)

(7 7 21) (7 14) (7) (1)

(2 8 24 36) (8 16 32) (8 20) (8) (1)

(9 9 54 54) (9 30 45) (9 27) (9) (1)

(2 10 40 80 120) (10 25 75 100) (10 50 60) (10 35) (10) (1)

(11 11 110 110 220) (11 55 99 165) (11 77 77) (11 44) (11) (1)

(2 12 60 150 300 400) (12 36 144 240 360) (12 105 126 252) (12 96 112) (12 54) (12) (1)

(13 13 195 195 650 650) (13 91 182 455 546) (13 156 364 182) (13 117 156) (13 65) (13) (1)

(2 14 84 252 630 1050 1400) (14 49 245 490 980 1225) (14 196 224 784 784) (14 189 294 504) (14 140 210) (14 77) (14) (1)

As per requested, the code written is clojure is:

(defn binary? [number]
(if (or (= number 0)
(= number 1))
true false))

(defn all-binary? [array]
(cond (empty? array)          true
(binary? (first array)) (all-binary? (rest array))
:else                   false ))

(defn select-bit [value position]
(bit-and 1 (bit-shift-right value position)))

(defn make-bits [length value]
(let [positions (reverse (range length) )]
(map select-bit (repeat value) positions)))

(defn make-random-bits [length]
(cond (< length 32)
(let [random-value (rand-int (bit-shift-left 1 length))]
(make-bits length random-value))
:else
(->> #(rand-int 2) repeatedly (take length))))

(defn x! [n j] (make-bits n j))

(defn x->j [x]
(let [to-dec (fn [position value]
(* value (bit-shift-left 1 position)))
positions (reverse (range (count x)))]
(reduce + (map to-dec positions x))))

(defn f! [n m]
(let   [table (-> (bit-shift-left 1 n) (make-bits m) vec)]
(fn [x] (nth table (x->j x)))))

((f! 2 4) (x! 2 1))

(defn T! [n m]
(let [cyc (fn [X position]
(nth X (mod position (count X))))
idx (fn [position n]
(range (- (inc position) n)
(inc position)))
sub (fn [X position n]
(map #(cyc X %) (idx position n)))
f   (f! n m)]
(fn [X]
(let [sub-arrs (map #(sub X % n)
(range (count X)))]
(vec (map f sub-arrs))))))

((T! 2 10) [0 1 0 1 0 1 1 1]) ;;Works

(def q-keys #{:0->0 :0->1 :1->0 :1->1})

(defn- qode-bit [in out]
(let [pair [in out]]
(cond (= pair [0 0]) :0->0
(= pair [0 1]) :0->1
(= pair [1 0]) :1->0
(= pair [1 1]) :1->1)))

(defn- patch-q [q]
(let [missing?    #(not (contains? q %))
all-missing (filter missing? q-keys)
filler (zipmap all-missing (repeat 0))]
(merge q filler)))

(defn q!
([T X-in]
(let [X-out (T X-in)
q-arr (map qode-bit X-in X-out)]
(-> q-arr frequencies patch-q)))
([T N j] (q! T (x! N j))))

(q! (T! 2 9) [0 1 1 0 0 1 0])

(defn Q!
[T N & {track? :track?}]
(let [q-fn    #(q! T N %)]
(loop [key-set #{}
count-map {}
inputs-map {}
js (range (bit-shift-left 1 N))]
(cond
(nil? (seq js))
(zipmap key-set (map #(hash-map :counts (count-map %)
:inputs (if track? (inputs-map %) [])) key-set))
:else
(let [j (first js)
q (q-fn j)
entry? (not (nil? (key-set q)))]
(cond entry?
(recur key-set
(assoc count-map q (inc (count-map q)))
(if track? (assoc inputs-map q (conj (inputs-map q) j)))
(rest js))
:else
(recur (conj key-set q)
(assoc count-map q 1)
(assoc inputs-map q (if track? [j] [ ]))
(rest js))))))))


So:

The system is a variant of the cellular automaton... just to explain the code little better:

(x! n v) => creates a binary sequence of length N, having a decimal value of v
(x! 9 7) => (0 0 0 0 0 0 1 1 1)

(f! n m) => constructs a function that takes a sequence
=> of length n and looks up the bit value of m
=> which specifies the type of values that are
=> given to the output. (more clearly shown in
=> the example below)
(map (f! 2 0) [[0 0] [0 1] [1 0] [1 1]]) => (0 0 0 0)
(map (f! 2 1) [[0 0] [0 1] [1 0] [1 1]]) => (0 0 0 1)
(map (f! 2 15)[[0 0] [0 1] [1 0] [1 1]]) => (1 1 1 1)

(T! n m) => generates a cellular automata type transform
=> that takes an input sequence X and maps (f! n m)
=> across every element of X
((T! 2 7) [1 0 1 0 1 0 1]) => [1 1 1 1 1 1 1]
((T! 2 10) [1 0 1 0 1 0 1]) => [0 1 0 1 0 1 0]

(q! T X-in) => Takes a transform and a sequence and looks at
=> changes between the input and the output bits
(q! (T! 2 7) [0 1 1 0 0 1 0]) => {:1->0 0, :0->0 2, :1->1 3, :0->1 2}
(q! (T! 2 10) [1 0 1 0 1 0 1]) => {:0->0 0, :1->1 0, :0->1 4, :1->0 3}


Now:

(Q! T N) => does a summary of mapping T to possible values of an N length
=> sequence (from 0 to 2^N-1)

(Q! (T! 2 3) 5) =>

    {{:0->0 0, :0->1 1, :1->0 1, :1->1 3} {:counts 5, :inputs [15 23 27 29 30]},
{:0->1 1, :0->0 1, :1->0 1, :1->1 2} {:counts 5, :inputs [7 14 19 25 28]},
{:0->1 1, :0->0 2, :1->0 1, :1->1 1} {:counts 5, :inputs [3 6 12 17 24]},
{:1->1 0, :0->1 1, :0->0 3, :1->0 1} {:counts 5, :inputs [1 2 4 8 16]},
{:0->0 0, :1->0 0, :0->1 0, :1->1 5} {:counts 1, :inputs [31]},
{:0->0 0, :0->1 2, :1->0 2, :1->1 1} {:counts 5, :inputs [11 13 21 22 26]},
{:1->1 0, :0->1 2, :0->0 1, :1->0 2} {:counts 5, :inputs [5 9 10 18 20]},
{:1->0 0, :1->1 0, :0->1 0, :0->0 5} {:counts 1, :inputs [0]}}

(Q! (T! 2 3) 6) =>

    {{:0->0 0, :0->1 1, :1->0 1, :1->1 4} {:counts 6, :inputs [31 47 55 59 61 62]},
{:0->0 0, :1->1 0, :0->1 3, :1->0 3} {:counts 2, :inputs [21 42]},
{:1->1 0, :0->1 1, :0->0 4, :1->0 1} {:counts 6, :inputs [1 2 4 8 16 32]},
{:0->0 0, :1->0 0, :0->1 0, :1->1 6} {:counts 1, :inputs [63]},
{:0->0 0, :0->1 2, :1->0 2, :1->1 2} {:counts 9, :inputs [23 27 29 43 45 46 53 54 58]},
{:0->1 2, :0->0 1, :1->0 2, :1->1 1} {:counts 12, :inputs [11 13 19 22 25 26 37 38 41 44 50 52]},
{:1->1 0, :0->1 2, :0->0 2, :1->0 2} {:counts 9, :inputs [5 9 10 17 18 20 34 36 40]},
{:1->0 0, :1->1 0, :0->1 0, :0->0 6} {:counts 1, :inputs [0]},
{:0->1 1, :0->0 3, :1->0 1, :1->1 1} {:counts 6, :inputs [3 6 12 24 33 48]},
{:0->1 1, :0->0 2, :1->0 1, :1->1 2} {:counts 6, :inputs [7 14 28 35 49 56]},
{:0->1 1, :0->0 1, :1->0 1, :1->1 3} {:counts 6, :inputs [15 30 39 51 57 60]}}


And so on.

I have grouped the inputs together into different counts using a pattern I discovered about the inputs and came up with a triangle. I'm hoping someone can cast a bit of light on what is happening!

When I turn the inputs into a binary string, I get these groupings that correspond to elements in the triangle. It seems that these groups grow a certain way, but I'm not a mathematician and so are not good and generalising patterns.

For N=5
id  count      indices
0      1       [ 00000 ]
1      5       [ 00001 00010 00100 01000 10000 ]
2      5       [ 00011 00110 01100 10001 11000 ]
3      5       [ 00101 01001 01010 10010 10100 ]
4      5       [ 00111 01110 10011 11001 11100 ]
5      5       [ 01011 01101 10101 10110 11010 ]
6      5       [ 01111 10111 11011 11101 11110 ]
7      1       [ 11111 ]

For N=6
id  count      input
0      1       [ 000000 ]
1      6       [ 000001 000010 000100 001000 010000 100000 ]
2      6       [ 000011 000110 001100 011000 100001 110000 ]
3      9       [ 000101 001001 001010 010001 010010 010100 100010 100100 101000 ]
4      6       [ 000111 001110 011100 100011 110001 111000 ]
5      12      [ 001011 001101 010011 010110 011001 011010 100101 100110 101001 101100 110010 110100 ]
6      6       [ 001111 011110 100111 110011 111001 111100 ]
7      2       [ 010101 101010 ]
8      9       [ 010111 011011 011101 101011 101101 101110 110101 110110 111010 ]
9      6       [ 011111 101111 110111 111011 111101 111110 ]
10     1       [ 111111 ]

For N=7
id  count      input
0      1       [ 0000000 ]
1      7       [ 0000001 0000010 0000100 0001000 0010000 0100000 1000000 ]
2      7       [ 0000011 0000110 0001100 0011000 0110000 1000001 1100000 ]
3      14      [ 0000101 0001001 0001010 0010001 0010010 0010100 0100001 0100010 0100100 0101000 1000010 1000100 1001000 1010000 ]
4      7       [ 0000111 0001110 0011100 0111000 1000011 1100001 1110000 ]
5      21      [ 0001011 0001101 0010011 0010110 0011001 0011010 0100011 0100110 0101100 0110001 0110010 0110100 1000101 1000110 1001001 1001100 1010001 1011000 1100010 1100100 1101000 ]
6      7       [ 0001111 0011110 0111100 1000111 1100011 1110001 1111000 ]
7      7       [ 0010101 0100101 0101001 0101010 1001010 1010010 1010100 ]
8      21      [ 0010111 0011011 0011101 0100111 0101110 0110011 0110110 0111001 0111010 1001011 1001101 1001110 1010011 1011001 1011100 1100101 1100110 1101001 1101100 1110010 1110100 ]
9      7       [ 0011111 0111110 1001111 1100111 1110011 1111001 1111100 ]
10     7       [ 0101011 0101101 0110101 1010101 1010110 1011010 1101010 ]
11     14      [ 0101111 0110111 0111011 0111101 1010111 1011011 1011101 1011110 1101011 1101101 1101110 1110101 1110110 1111010 ]
12     7       [ 0111111 1011111 1101111 1110111 1111011 1111101 1111110 ]
13     1       [ 1111111 ]

-
What's the rule for generating this sequence of numbers? – Michael Joyce Jun 7 '12 at 20:46
The rule is a little bit complicated but involves categorising inputs and sorting them. I'll put the code up -> its written in clojure. – zcaudate Jun 7 '12 at 21:05
Nice question! I have no comments on the code but here are some comments on the numbers. You can think of the elements of Pascal's triangle ${n \choose k}$ as counting the number of binary strings of length $n$ with $k$ ones. These numbers are some refinement of that count that takes into account the value of some third parameter; moreover it looks like the number of possible values of that parameter is equal to $k$ (for $k > 0$). – Qiaochu Yuan Jun 7 '12 at 22:18

Here's a formula that is based on @QiaochuYuan's combinatorial description.

Let $f(n,k,c)$ be the number of binary strings with $n$ bits, $k$ ones and $c$ circular clusters. Let $f_{00}(n,k,c)$ be the number of such strings that start and end with 0, and define $f_{01}$,$f_{10}$,$f_{11}$ analogously, so $f=f_{00}+f_{01}+f_{10}+f_{11}$.

By considering what happens when we append a 0 or 1 bit to the left end of each string (e.g. for strings counted by $f_{00}$ a 1 on the end adds one 1 and one cluster), we have the following: \begin{align} f_{00}(n,k,c) & = f_{00}(n-1,k,c)+f_{10}(n-1,k,c) \\ f_{01}(n,k,c) & = f_{01}(n-1,k,c)+f_{11}(n-1,k,c-1) \\ f_{10}(n,k,c) & = f_{00}(n-1,k-1,c-1)+f_{10}(n-1,k-1,c) \\ f_{11}(n,k,c) & = f_{01}(n-1,k-1,c)+f_{11}(n-1,k-1,c) \\ f_{10}(n,k,c) & = f_{01}(n,k,c) \end{align} where the last identity comes from considering the reversal of each binary string.

By inspection I propose \begin{align} f_{00}(n,k,c) & = \binom{n-k-1}{c}\binom{k-1}{c-1} \\ f_{01}(n,k,c) & = \binom{n-k-1}{c-1}\binom{k-1}{c-1} \\ f_{11}(n,k,c) & = \binom{n-k-1}{c-1}\binom{k-1}{c} \end{align} and we can prove them correct by induction using the identities above.

Hence \begin{align} f(n,k,c) & = f_{00}(n,k,c)+2f_{01}(n,k,c)+f_{11}(n,k,c) \\ & = \binom{n-k}{c}\binom{k-1}{c-1}\left[1+\frac{k}{n-k}\right] \end{align}

Thus, for example, let $n=13,k=5$. For $c=1,2,3,4,5$ we get $f=13,182,546,455,91$, which is one of your sets (rearranged).

-
Very nice! These come out much cleaner than I anticipated. – Qiaochu Yuan Jun 10 '12 at 4:20
Wow =) I'm so impressed. Will be trying out this solution in the next few days. I wanted to generate the entire sequence space for N=1000 and the brute force solution took more than an hour on N=20. So you and @qiaochu-yuan and saved me lifetimes of computation =) – zcaudate Jun 11 '12 at 0:14

As I said in my comment, these numbers count binary strings of length $n$ with $k$ ones by some other numerical parameter which I believe I now know: it is the number $c$ of circular clusters that the ones form, i.e. attach the beginning and end of the string together, count the number of clusters of ones you get. For example:

• When $k = 0$ there are always no such clusters. This gives the rightmost diagonal of your numbers.
• When $k = 1$ there is always one such cluster. This gives the second rightmost diagonal of your numbers.
• When $k = 2$ there are $n$ strings with one cluster and the rest of them, ${n \choose 2} - n$, have two clusters. This gives the third rightmost diagonal of your numbers.
• When $k = 3$ there are again $n$ strings with one cluster (this is true for all $k$). A string with two clusters must have a cluster of $2$ ones and a cluster of $1$ one. There are $n$ possible positions of the $2$-cluster and $n-4$ possible positions of the $1$-cluster relative to the two-cluster for a total of $n(n-4)$ strings with two clusters. There are ${n \choose 3} - n - n(n-4)$ remaining strings and they have three clusters.

As for a general formula, I'm still thinking about it.

-
Thanks for your input and that jogs my memory. I've looked at that already... Let me put up some more results... its the way that the binary sequences are classified by the arrangement of 1's and 0's within. – zcaudate Jun 7 '12 at 22:42
Counting the clusters will simply mean to take all such binary strings with a certain period and cut them and then do inclusion-exclusion on them. – Phira Jun 7 '12 at 23:06
thank for your help! its a very clear description. – zcaudate Jun 11 '12 at 0:15