Necesito ayuda para determinar de dónde viene esta secuencia parecida a un triángulo de Pascal.

Question

Tengo un problema muy interesante en el sentido de que un programa que estoy ejecutando ha generado una secuencia de números que se comportan como el triángulo de pascal pero que de alguna manera ha incorporado más estructura. Llevo un rato dándole vueltas a esto y no puedo entender cómo funciona la secuencia. Lo he puesto en la mitad del triángulo hasta n = 14 por lo que el conjunto debería ser así:

1

1 2 1

1 3 3 1

... etc... así que fíjate que los números contenidos dentro de los paréntesis suman el número correcto para el triángulo, para n = 4, (2 4) suman 6 y así sucesivamente. Espero que alguien sepa de dónde sale esta secuencia o cómo generalizar esta solución para poder calcular los números del triángulo para cada n.

Gracias.

(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)

---

Según lo solicitado, el código escrito es clojure es:

(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))))))))

Así que:

El sistema es una variante del autómata celular... para explicar un poco mejor el código:

(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}

Ahora:

(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\]}}

Y así sucesivamente.

He agrupado las entradas en diferentes recuentos utilizando un patrón que descubrí sobre las entradas y me salió un triángulo. ¡Espero que alguien pueda arrojar un poco de luz sobre lo que está sucediendo!

---

Cuando convierto las entradas en una cadena binaria, obtengo estas agrupaciones que corresponden a elementos del triángulo. Parece que estos grupos crecen de una manera determinada, pero no soy un matemático y por lo tanto no son buenos y generalizar los patrones.

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 \]

Answer 1

Como dije en mi comentario, estos números cuentan cadenas binarias de longitud $n$ con $k$ por algún otro parámetro numérico que creo conocer ahora: es el número $c$ de grupos circulares que forman los unos, es decir, une el principio y el final de la cadena, cuenta el número de grupos de unos que obtienes. Por ejemplo:

• Cuando $k = 0$ siempre no hay tales grupos. Esto da la diagonal más a la derecha de sus números.
• Cuando $k = 1$ siempre hay un grupo de este tipo. Esto da la segunda diagonal de la derecha de sus números.
• Cuando $k = 2$ hay $n$ cadenas con un racimo y el resto de ellas, ${n \choose 2} - n$ , tienen dos racimos. Esto da la tercera diagonal de la derecha de sus números.
• Cuando $k = 3$ hay de nuevo $n$ cadenas con una agrupación (esto es cierto para todos los $k$ ). Una cadena con dos grupos debe tener un grupo de $2$ y un grupo de $1$ uno. Hay $n$ posibles posiciones del $2$ -cluster y $n-4$ posibles posiciones del $1$ -en relación con el clúster de dos para un total de $n(n-4)$ cadenas con dos racimos. Hay ${n \choose 3} - n - n(n-4)$ cadenas restantes y tienen tres racimos.

En cuanto a una fórmula general, todavía estoy pensando en ello.

Answer 2

Aquí hay una fórmula que se basa en la descripción combinatoria de @QiaochuYuan.

Dejemos que $f(n,k,c)$ sea el número de cadenas binarias con $n$ bits, $k$ y $c$ racimos circulares. Sea $f_{00}(n,k,c)$ es el número de cadenas que empiezan y terminan en 0, y define $f_{01}$ , $f_{10}$ , $f_{11}$ análogamente, así $f=f_{00}+f_{01}+f_{10}+f_{11}$ .

Teniendo en cuenta lo que ocurre cuando añadimos un 0 o un 1 al extremo izquierdo de cada cadena (por ejemplo, para las cadenas contadas por $f_{00}$ un 1 al final añade un 1 y un racimo), tenemos lo siguiente: $$ \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} $$ donde la última identidad proviene de considerar la inversión de cada cadena binaria.

Mediante la inspección propongo $$ \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} $$ y podemos demostrar que son correctas por inducción utilizando las identidades anteriores.

Por lo tanto, $$ \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} $$

Así, por ejemplo, dejemos que $n=13,k=5$ . Para $c=1,2,3,4,5$ obtenemos $f=13,182,546,455,91$ que es uno de sus conjuntos (reordenados).