Resumen funciones combinatorias numéricas

Funciones combinatorias numéricas

Resumen de todas las funciones combinatorias de la aplicación Combine Tools que calculan los valores númericos.

  • Factorial

    Las permutaciones de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar. Se denota generamente como P(n) y su valor es P(n) = n! denominado el factorial. Se calcula recursivamente con n! = n (n-1)!.

    • Factorial recursivo

      0! = 1,
      n! = n × (n-1)!

      // n! = n * (n-1)!
function factorial(n){
    if (n<=0){
        return 1;
    } else {
        return n*factorial(n-1);
    }
}
      Permutaciones

  • Bionomial

    El número de combinaciones sin repetición de n elementos distintos en subconjuntos de k elementos son las posibles muestras de k elementos distintos y sin orden que pueden extraerse de los n elementos. En estas páginas las denotaremos como C(n, k) aunque las veremos como (nk). Su valor numérico se calcula con la fórmula n!/(k!(n-k)!).

    • Binomial con fórmula cerrada

      C(n, k) =n!
      k! (n-k)!

      // C(n, k) = n! / (k! (n-k)!)
function binomial(n, k) {
    if (n<k) {
        return k===0 ? 1 : 0;
    } else {
        return factorial(n) / (factorial(k)*factorial(n-k));
    }
}
      Combinaciones

    • Binomial con Triángulo Pascal

      Se calcula recursivamente con C(n, k) = C(n-1, k-1) + C(n-1, k) conocida como fórmula del Triángulo de Pascal.

      C(n, 0) = 1,
      C(0, k) = 0,
      C(n, k) = C(n-1, k-1) + C(n-1, k)

      // C(n, k) = C(n-1, k-1) + C(n-1, k)
function binomial1(n, k) {
    if (k===0) {
        return 1;
    } else if (n===0) {
        return 0;
    } else {
        return binomial1(n-1, k-1) + binomial1(n-1, k)
    }
}
      Combinaciones

    • Binomial con identidad Hockey-stick

      Otra fórmula recursiva es C(n, k) = ∑j=k..n C(j-1, k-1), denominada identidad Hockey-stick.

      C(n, 0) = 1,
      C(n, k) = ∑j=k..n C(j-1, k-1)

      // C(n, k) = sum_(j=k)^n C(j-1, k-1)
function binomial2(n, k) {
    if (k===0) {
        return 1;
    } else {
        let value = 0;
        for (let j=k; j<=n; j++){
            value += binomial2(j-1, k-1);
        }
        return value;
    }
}
      Combinaciones 2

  • Factorial descendente

    El factorial descendente (fallingFactorial factorial), que se denota como (x)n o bien xn, se define para n>0 de la forma siguiente: (x)n = xn = x(x-1)(x-2)···(x-n+1). Se conviene que x0 = 1.
    Se relaciona con el factorial ascendente con xn = (x-n+1)n = (-1)n (-x)n.
    El factorial ordinario, ascendente y descendente se relacionan con 1n = nn = n!.
    Otras relaciones son V(n, k) = nk siendo V(n, k) = C(n, k) k! las variaciones, pudiendo expresarse entonces como nk = V(n, k) = n!/(n-k)!.

    • Factorial descendente

      nk =n!= k! C(n, k)
      (n-k)!

      // Falling factorial = n! / (n-k)!
function fallingFactorial(n, k) {
    return factorial(n) / factorial(n-k);
}
      Factorial descendente

  • Factorial ascendente o Pochhammer

    El factorial ascendente (rising factorial) o función de Pochhammer, que se denota como x(n) o bien xn, se define para n>0 de la forma siguiente: x(n) = xn = x(x+1)(x+2)···(x+n-1). Se conviene que x0 = 1.
    Está relacionado con las combinaciones con repetición mediante la expresión nk = k! C(n+k-1, k) = k! CR(n, k), recordando que CR(n, k) = C(n+k-1, k).
    Se relaciona con el factorial descendente con xn = (x+n-1)n = (-1)n (-x)n.
    El factorial ordinario, ascendente y descendente se relacionan con 1n = nn = n!.

    • Factorial ascendente o Pochhammer

      nk =(n+k-1)!= k! C(n+k-1, k)
      (n-1)!

      // pochhammer = (n+k-1)! / (n-1)!
function pochhammer(n, k) {
    return factorial(n+k-1) / factorial(n-1);
}
      Factorial descendente

  • K-Tuplas

    Definimos las K-Tuplas de un conjunto A con n elementos distintos a todas las sublistas ordenadas que podemos generar con las permutaciones aplicadas sobre todos los subconjuntos de orden k hasta n que se obtienen desde el conjunto A. Las denotamos como K(n, k).

    • K-Tuplas con fórmula cerrada


      Se calcula con la fórmula cerrada K(n, k) = ∑j=0..n-k n!/j!.

      K(n, k) = ∑j=0..n-kn!
      j!

      // K(n, k) = sum_(j=0)^(n-k) n!/j!
function ktuples(n, k) {
    let value = 0;
    let fn = factorial(n);
    for (let i=0; i<=n-k; i++) {
        value += fn/factorial(j);
    }
    return value;
}
      K-Tuplas

    • K-Tuplas con recurrencia


      Se calcula recursivamente con K(n, k) = n K(n-1, k) + n!/(n-k)!.

      n<k ⇒ K(n, k) = 0,
      n=k ⇒ K(n, k) = k!
      K(n, k) = n K(n-1, k) +n!
      (n-k)!

      // K(n, k) = n K(n-1, k) + !n/(n-k)!
function ktuples1(n, k){
    if (n<k){
        return 0;
    } else if (n===k) {
        return factorial(k);
    } else {
        return n * ktuples1(n-1, k) + (factorial(n) / factorial(n-k));
    }
}
      K-Tuplas

  • Función Gamma

    La Función Gamma, función que extiende los factoriales a los números reales y complejos. Se define de forma general como Γ(n) = (n-1)!, que se obtiene de su expresión como recursiva Γ(n) = (n-1) Γ(n-1). Aunque se calcula recursivamente, se puede aproximar con funciones apropiadas para cálculos de los primeros valores de n=x-1. Se basa en la fórmula de Stirling Γ(x) = √2π/x (x/e)x (1 + O(1/x))

    • La función Gamma

      x=n+1
      Γ(x) ≈ √(2π) ( (x) √(x sinh(1) +1) ) x
      xex810 x6

      function gamma(n=0) {
    let x = n+1;
    return Math.sqrt(2*Math.PI/x)*((x/Math.E) * 
        Math.sqrt(x * Math.sinh(1/x) + (1 / (810 * x**6))))**x;
}
      Función Gamma

  • Subfactorial

    Los desarreglos (derangement) de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar de tal forma que ninguno aparece en su posición original. Se denota como D(n). Y también como !n, el subfactorial de n. Una permutación de n elementos tiene uno o más elementos que son puntos fijos si esos elementos se mantienen en su posición original. Desde esta definición un desarreglo es una permutación que no tiene ningún punto fijo.

    • Subfactorial con fórmula cerrada


      Se calcula con la fórmula cerrada D(n) = !n = ∑j=0..n (-1) j n!/j!.

      !n = ∑j=0..n(-1) j n!
      j!

      // !n = sum_(j=0)^n (-1)^j n!/j!
function subfactorial(n) {
    let value = 0;
    let fn = factorial(n);
    for (let j=0; j<=n; j++){
        value += (-1)**j * fn / factorial(j);
    }
    return value;
}
      Desarreglos

    • Subfactorial con recurrencia


      También D(n) = !n puede calcularse con la recurrencia !n = (n-1) !(n-1) + (n-1) !(n-2).

      !0 = 1,
      !1 = 0,
      !n = (n-1) !(n-1) + (n-1) !(n-2)

      // !n= (n-1) !(n-1) + (n-1) !(n-2)
function subfactorial1(n) {
    let value = 0;
    if (n===0){
        value = 1;
    } else if (n===1){
        value = 0;
    } else {
        value = (n-1) * subfactorial1(n-1) + (n-1) * subfactorial1(n-2);
    }
    return value;
}
      Desarreglos

    • Subfactorial con recurrencia (2)


      Otra recurrencia es !n = n !(n-1) + (-1)n.

      !0 = 1,
      !n = n !(n-1) + (-1)n

      // !n = n !(n-1) + (-1)^n
function subfactorial2(n) {
    let value = 0;
    if (n===0){
        value = 1;
    } else {
        value = n * subfactorial1(n-1) + (-1)**n;
    }
    return value;
}
      Desarreglos

  • Desarreglos parciales

    Los desarreglos parciales (partial derangements) de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar de tal forma que solo k elementos aparecen en su posición original. También se pueden definir como las permutaciones de n elementos con k puntos fijos. Las denotamos como D(n, k), correspondiendo con k=0 a los desarreglos sin puntos fijos o subfactoriales. También se les denomina Rencontres numbers traducido como Problema de encuentros (o reencuentros).

    • Desarreglos con k puntos fijos, fórmula cerrada

      Se calcula con la fórmula cerrada D(n, k) = C(n, k) × !(n-k).

      D(n, k) = C(n, k) × !(n-k)

      // D(n, k) = C(n, k) × !(n-k)
function partialDerange1(n, k) {
    return binomial(n, k) * subfactorial(n-k);
}
      Desarreglos

    • Desarreglos con k puntos fijos con recurrencia

      Se calcula recursivamente con D(n, k) = n/k D(n-1, k-1).

      D(n, 0) = !n,
      D(n, k) =nD(n-1, k-1)
      k

      // D(n, k) = n/k D(n-1, k-1)
function partialDerange2(n, k) {
    let value = 0;
    if (k===0) {
        value = subfactorial(n);
    } else {
        value = (n/k) * partialDerange2(n-1, k-1);
    }
    return value;
}
      Desarreglos

    • Desarreglos con k puntos fijos, fórmula cerrada (2)

      Otra fórmula cerrada para su cálculo es D(n, k) = !(n-k) × ∑j=k..n C(j-1, k-1).

      D(n, 0) = !n,
      D(n, k) = !(n-k) × ∑j=k..n C(j-1, k-1)

      // D(n, k) = !(n-k) × sum_(j=k)^n C(j-1, k-1)
function partialDerange3(n, k) {
    if (k===0) {
        return subfactorial(n);
    } else {
        let value = 0;
        for (let j=k; j<=n; j++){
            value += binomial(j-1, k-1);
        }
        return subfactorial(n-k) * value;
    }
}
      Desarreglos parciales 3

    • Desarreglos con k puntos fijos con recurrencia (2)

      Otra recurrencia es D(n, k, b) = ∑j=k..n D(n-1, j-1, b) donde b = n0 - k0 es un valor constante, siendo n0 y k0 los valores iniciales.

      b = n0 - k0
      D(b, k) = !b
      D(n, k, b) = ∑j=k..n D(n-1, j-1, b)

      // D(n, k) = sum_(j=k)^(n) D(n-1, j-1)
function partialDerange4(n, k, b=n-k) {
    if (n===b) {
        return subfactorial(n);
    } else {
        let value = 0;
        for (let j=k; j<=n; j++){
            value += partialDerange4(n-1, j-1, b);
        }
        return value;
    }
}
      Desarreglos parciales 3

  • Número armónico

    El n-ésimo número armónico se define como la suma de los recíprocos de los primeros n números naturales, con serie n≥1 igual a H(n) = ∑j=1..n 1/j

    • Número armónico

      H(n) = ∑j=1..n 1/j

      // H(n) = sum_(j=1)^n 1/j
function harmonic(n) {
    let value = 0;
    for (let j=1; j<=n; j++){
        value += 1/j;
    }
    return value;
}
      Número armónico

    • Número armónico recursivo


      Recursivamente se definen como H(n) = H(n-1) + 1/n.

      n<1 ⇒ H(n) = 0,
      n=0 ⇒ H(n) = 1,
      H(n) = H(n-1) +1
      n

      // H(n) = H(n-1) + 1/n
function harmonic1(n) {
    let value = 0;
    if (n<1) {
        value = 0;
    } else if (n===1) {
        return 1;
    } else {
        value = harmonic1(n-1) + 1/n;
    }
    return value;
}
      Número armónico

    • Número armónico y de Stirling primera clase


      Están relacionados con los números de Stirling de primera clase con H(n) = S(n+1, 2)/n!.

      H(n) =S(n+1, 2)
      n!

      // H(n) = 1/n! S(n+1, 2)
function harmonic2(n) {
    return stirlingS1(n+1, 2) / factorial(n);
}
      Número armónico

  • Números de Stirling de primera clase

    Los números de Stirling de primera clase, sin signo, pueden definirse como el número permutaciones de n elementos en k ciclos disjuntos. Se denotan como S(n, k) y también como [nk]. Con signo se denotan como s(n, k) y ambos se relacionan con s(n, k) = (-1)n-k S(n, k)

    • Números de Stirling primera clase (sin signo)

      Sin signo se calcula recursivamente S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)

      n=k ⇒ S(n, k) = 1,
      n=0 ∨ k=0 ∨ n<k ⇒ S(n, k) = 0,
      S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)

      // S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)
function stirlingS1(n, k) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k){
        return 0;
    } else {
        return (n-1) * stirlingS1(n-1, k) + stirlingS1(n-1, k-1);
    }
}
      Números Stirling primera clase

    • Números de Stirling primera clase (con signo)

      Con signo se calcula recursivamente s(n+1, k) = -n s(n, k) + s(n, k-1)

      n=k ⇒ s(n, k) = 1,
      n=0 ∨ k=0 ∨ n<k ⇒ s(n, k) = 0,
      s(n, k) = - (n-1) s(n-1, k) + s(n-1, k-1)

      // s(n, k) = -(n-1) s(n-1, k) + s(n-1, k-1)
function stirlingS1_1(n, k) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k){
        return 0;
    } else {
        return -(n-1) * stirlingS1_1(n-1, k) + stirlingS1_1(n-1, k-1);
    }
}
      Números Stirling primera clase

    • Números de Stirling primera clase (con y sin signo)

      s(n, k) = (-1)n-k S(n, k)

      // s(n, k) = (-1)^(n-k) S(n, k)
function stirlingS1_2(n, k) {
    return (-1)**(n-k) * stirlingS1(n, k);
}
      Números Stirling primera clase

    • Números de Stirling primera clase sin signo (recurrencia 2)

      n=k ⇒ S(n, k) = 1,
      n=0 ∨ k=0 ∨ n<k ⇒ S(n, k) = 0,
      k=1 ⇒ S(n, k) = (n-1)!,
      S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)

      // S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)
function stirlingS1_3(n=0, k=0) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k) {
        return 0;
    } else if (k===1){
        return factorial(n-1);
    } else {
        return (n-1) * stirlingS1_3(n-1, k) + stirlingS1_3(n-1, k-1);
    }
}
      Números Stirling primera clase

    • Números de Stirling primera clase sin signo (recurrencia 3)

      n=k ⇒ S(n, k) = 1,
      n=0 ∨ k=0 ∨ n<k ⇒ S(n, k) = 0,
      S(n, k) = ∑j=k-1..n-1 S(n-1, j) C(j, k-1)

      // S(n, k) = sum_(j=k-1)(n-1) S(n-1, j) C(j, k-1)
function stirlingS1_4(n=0, k=0) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k) {
        return 0;
    } else {
        let sum = 0;
        for (let j=k-1; j<=n-1; j++) {
            sum += stirlingS1_4(n-1, j) * binomial(j, k-1);
        }
        return sum;
    }
}
      Números Stirling primera clase

  • Números de Stirling de segunda clase

    Un número de Stirling de segunda clase es el número de formas de particionar un conjunto de n elementos en k subconjuntos no vacíos, denotados como S2(n, k) o {nk}.
    Por ejemplo, el número de formas de particionar el conjunto {a, b} en subconjuntos de elementos k=1 es S2(2, 1) = 1 siendo esa partición {{a, b}}, mientras que con dos elementos k=2 también tendremos S2(2, 2) = 1 una partición con dos subconjuntos {{a}, {b}}, ya que k será el número de subconjuntos involucrados en cada partición.
    El número total de particiones de un conjunto se calcula con el número de Bell, con la expresión B(n) = ∑j=0..n S2(n, j), que para el ejemplo anterior sería B(2) = 2.
    El número de Stirling se calcula de forma recursiva con S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)

    • Números Stirling segunda clase con recurrencia

      n=k ⇒ S2(n, k) = 1,
      n=0 ∨ k=0 ∨ n<k ⇒ S2(n, k) = 0,
      S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)

      // S2(n, k) = S2(n-1, k-1) + k * S2(n-1, k)
function stirlingS2(n, k) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k) {
        return 0;
    } else {
        return stirlingS2(n-1, k-1) + k * stirlingS2(n-1, k);
    }
}
      Particiones y números de Stirling de segunda clase

    • Números Stirling segunda clase, fórmula cerrada

      Y también con la fórmula cerrada S2(n, k) = 1/k! ∑j=0..k (-1)k-j C(k, j) jn

      S2(n, k) =1∑j=0..k (-1)k-j C(k, j) jn
      k!

      // S2(n, k) = (1/k!) sum_(j=0)^(k) (-1)^(k-j) C(k, j) j^n
function stirlingS2_1(n, k) {
    let sum = 0;
    for (let j=0; j<=k; j++){
        sum += (-1)**(k-j) * binomial(k, j) * j**(n);
    }
    return (1/factorial(k)) * sum;
}
      Particiones y números de Stirling de segunda clase

    • Números Stirling segunda clase con recurrencia (2)

      y también con la recurrencia S2(n, k) = ∑j=k..n kn-j S2(j-1, k-1)

      n=k ⇒ S2(n, k) = 1,
      S2(n, k) = ∑j=k..n kn-j S2(j-1, k-1)

      // S2(n, k) = sum_(j=k)^(n) k^(n-j) S2(j-1, k-1)
function stirlingS2_2(n, k) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k) {
        return 0;
    } else {
        let sum = 0;
        for (let j=0; j<=n; j++) {
            sum += k**(n-j) * stirlingS2_2(j-1, k-1);
        }
        return sum;
    }
}
      Particiones y números de Stirling de segunda clase

    • Números Stirling segunda clase con recurrencia (3)

      y también con la recurrencia S2(n, k) = kn/k! - ∑j=1..k-1 S2(n, j)/(k-j)!

      n<k ⇒ S2(n, k) = 0,
      n=k ⇒ S2(n, k) = 1,
      S2(n, k) =kn- ∑j=1..k-1S2(n, j)
      k!(k-j)!

      // S2(n, k) = (k^n / k!) sum_(j=1)^(k-1) S2(n, j) / (k-j)!
function stirlingS2_3(n, k) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k) {
        return 0;
    } else {
        let sum = 0;
        for (let j=1; j<=k-1; j++) {
            sum += stirlingS2_3(n, j) / factorial(k-j);
        }
        return Math.round((k**n / factorial(k)) - sum);
    }
}
      Particiones y números de Stirling de segunda clase

    • Números Stirling segunda clase con recurrencia (4)

      y también con la recurrencia S2(n, k) = ∑j=k-1..n-1 C(n-1, j) S2(j, k-1)

      n<k ⇒ S2(n, k) = 0,
      n=k ⇒ S2(n, k) = 1,
      S2(n, k) = ∑j=k-1..n-1 C(n-1, j) S2(j, k-1)

      // S2(n, k) = sum_(j=k-1)^(n-1) C(n-1, j) S2(j, k-1)
function stirlingS2_4(n=0, k=0) {
    if (n===k) {
        return 1;
    } else if (n===0 || k===0 || n<k) {
        return 0;
    } else {
        let sum = 0;
        for (let j=0; j<=n-1; j++) {
            sum += binomial(n-1, j) * stirlingS2_4(j, k-1);
        }
        return sum;
    }
}
      Particiones y números de Stirling de segunda clase

  • Número de Bell

    El número de Bell Bn representa el total de particiones de un conjunto con n elementos. En lugar de denotarlo como Bn aquí lo escribiremos como B(n). Por ejemplo, con el conjunto {a, b} podemos establecer dos particiones {{a, b}} y {{a}, {b}}. En cada partición los subconjuntos son no vacíos y disjuntos, de tal forma que un elemento del conjunto aparecerá sólo en un conjunto.

    • Número de Bell con recurrencia

      Se calcula con la recurrencia B(n) = ∑j=0..n-1 C(n-1, j) B(j) y alternativamente con B(n) = ∑j=1..n C(n-1, j-1) B(n-j), no conociéndose una fórmula cerrada.

      B(0) = 1,
      B(n) = ∑j=0..n-1 C(n-1, j) B(j)

      // B(n) = sum_(j=0)^(n-1) C(n-1, j) B(j)
function bell(n) {
    if (n===0) {
        return 1;
    } else {
        let sum = 0;
        for (let j=0; j<=n-1; j++) {
            sum += binomial(n-1, j) * bell(j);
        }
        return sum;
    }
}
      Números de Bell

    • Número de Bell con recurrencia

      Se calcula con la recurrencia B(n) = ∑j=0..n-1 C(n-1, j) B(j) y alternativamente con B(n) = ∑j=1..n C(n-1, j-1) B(n-j), no conociéndose una fórmula cerrada.

      B(0) = 1,
      B(n) = ∑j=1..n C(n-1, j-1) B(n-j)

      // B(n) = sum_(j=1)^(n) C(n-1, j-1) B(n-j)
function bell1(n) {
    if (n===0) {
        return 1;
    } else {
        let sum = 0;
        for (let j=1; j<=n; j++) {
            sum += binomial(n-1, j-1) * bell1(n-j);
        }
        return sum;
    }
}
      Números de Bell

    • Número de Bell y Stirling segunda clase

      Se relaciona con los números de Stirling de segunda clase S2(n, k) con expresión B(n) = ∑j=0..n S2(n, j)

      B(n) = ∑j=0..n S2(n, j)
      S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)

      // B(n) = sum_(j=0)^(n) S2(n, j)
// S2(n, k) = S2(n-1, k-1) + k × S2(n-1, k)
function bell2(n) {
    let sum = 0;
    for (let j=0; j<=n; j++) {
        sum += stirlingS2(n, j);
    }
    return sum;
}
      Números de Bell y números de Stirling de segunda clase

    • Número de Bell con fórmula de Spivey


      La fórmula de Spivey relaciona la recurrencia B(n) = ∑j=0..n S2(n, j) con la recurrencia B(n+1) = ∑j=0..n C(n, j) B(j).

      B(n+k) = ∑i=0..n ∑j=0..k jn-i S2(k, j) C(n, i) B(i)

      //B(n+k) = sum_(i=0)^(n) sum_(j=0)^(k) j^(n-) S2(k, j) C(n, i) B(i)
function bell3(n=0, k=0) {
    let sum = 0;
    for (let i=0; i<=n; i++) {
        for (let j=0; j<=k; j++) {
            sum += j**(n-i) * stirlingS2(k, j) * binomial(n, i) * bell(i);
        }
    }
    return sum;
}
      Números de Bell y números de Stirling de segunda clase

    • Número de Bell con fórmula Dobinski


      La fórmula de Dobinski nos permite calcular un número de Bell usando una suma infinita, pudiendo usarla hasta n=20 con solo un rango 0..29 en el sumatorio.

      B(n) =1∑j=0..∞jn
      ej!

      //B(n) = 1/e sum_(j=0)^(∞) j^n/j!
//n≤20 ⇒ B(n) = Round(1/e sum_(j=0)^(29) j^n/j!)
function bell4(n=0) {
    let sum = 0;
    for (let j=0; j<=29; j++) {
        sum += j**n / factorial(j);
    }
    return (sum/Math.E).toFixed(3);
}
      Números de Bell y fórmula de Dobinski

  • Triángulo de Bell

    Triángulo de Bell, también denominado Array de Aitken o Triángulo de Pierce, como puede verse en la secuencia OEIS A011971, que lo define diciendo que B(n, k) es el número de relaciones de equivalencia sobre el conjunto {0, ..., n} tal que k no es equivalente a n, k+1 no es equivalente a n, ..., n-1 no es equivalente a n. Se basa en la propiedad recursiva B(n, k) = B(n, k-1) + B(n-1, k-1)

    • Triángulo de Bell

      aunque en esta versión se presenta con un algoritmo iterativo.

      B(0, 0) = 1,
      B(n, 0) = B(n-1, n-1),
      B(n, k) = B(n, k-1) + B(n-1, k-1)

      // Bell triangle
function kbell(n=0, k=0) {
    if (k<0) {
        return 0;
    } else {
        let val = [1];
        for (let i=0; i<=n-1; i++) {
            let prev = [...val];
            val = [val.pop()];
            for (let j=0; j<=i; j++) {
                val.push(val[j]+prev[j]);
            }
        }
        return k<val.length ? val[k] : 0;
    }
}
      Triángulo de Bell

    • Triángulo de Bell recursivo

      B(0, 0) = 1,
      B(n, 0) = B(n-1, n-1),
      B(n, k) = B(n, k-1) + B(n-1, k-1)

      // Bell triangle recursive
function kbell1(n=0, k=0) {
    if (n<k || k<0) {
        return 0;
    } else if (n===0 && k===0) {
        return 1;
    } else if (k===0) {
        return kbell1(n-1, n-1);
    } else {
        return kbell1(n, k-1) + kbell1(n-1, k-1);
    }
}
      Triángulo de Bell recursivo

  • Particiones parciales con semi bloques

    Las particiones con semi bloques parciales (o semi Bell), que denominaremos sB(n, k), son las particiones de un conjunto con n elementos tal que ninguno de los subconjuntos (o bloques) son de longitud igual a k. Por ejemplo, para el conjunto con n elementos {a, b, c} tenemos con k=1 la única partición abc expresada de forma compacta, donde ningún subconjunto o bloque tienen longitud unitaria; con k=2 tenemos abc, a.b.c; con k=3 tenemos ab.c, ac.b, a.bc, a.b.c; mientras que con k=0 tenemos todas las particiones posibles abc, ab.c, ac.b, a.bc, a.b.c.

    • Particiones parciales con semi bloques

      n=0 ⇒ sB(0, k) = 1
      n>0 ⇒ sB(n, k) = ∑j=1..n (1 - δj,k) C(n-1, j-1) sB(n-j, k)

      // sB(n, k) = sum_(j=1)^(n) (j=k) (1-δ_(j,k)) sB(n-j, k) C(n-1, j-1)
function semiBell(n, k) {
    if (n===0) {
        return 1;
    } else {
        let sum = 0;
        for (let j=1; j<=n; j++) {
            if (j!==k) {
                sum += sB(n-j, k) * binomial(n-1, j-1)
            }
        }
        return sum;
    }
}

  • Particiones con bloques parciales

    Las particiones con bloques parciales (o Bell parcial), que denominaremos pB(n, k), son las particiones de un conjunto con n elementos tal que alguno de los subconjuntos (o bloques) son de longitud igual a k. Por ejemplo, para el conjunto con n elementos {a, b, c} tenemos con k=1 las particiones ab.c, ac.b, a.bc, a.b.c expresada de forma compacta, donde todas tienen un bloque longitud unitaria; con k=2 tenemos ab.c, ac.b, a.bc; con k=3 tenemos abc; mientras que con k=0 tenemos todas las particiones posibles abc, ab.c, ac.b, a.bc, a.b.c.

    • Particiones con bloques parciales

      k=0 ⇒ pB(n, 0) = sB(n, 0)
      k>0 ⇒ pB(n, k) = sB(n, 0) - sB(n, k)

      // pB(n, k) = sB(n, 0) - sB(n, k)
function partialBell(n=0, k=0) {
    let result = sB(n, 0);
    if (k>0) result -= sB(n, k);
    return result;
}

  • Rimas coincidentes

    Las particiones también cuentan el número de esquemas de rimas de un poema. Entonces podemos generar B(n) particiones y por tanto rimas distintas. Si el conjunto de partida son n líneas de poemas (o versos) numeradas 1..n, podemos generar B(n) posibles formas de disponer las rimas en esas líneas.
    Las rimas coincidentes se refiere a evitar aquellos poemas donde no haya ningún verso que no rime con otros. Esto equivale a evitar particiones con bloques unitarios.
    Hay B(n) particiones para un conjunto con n elementos. Si quitamos las particiones que contengan subconjuntos o bloques unitarios, denominaremos rB(n) al resto de las particiones sin bloques unitarios. Se calcula con rB(n) = pB(n-1, 1) particiones usando las particiones con bloques parciales pB(n, k).

    • Rimas coincidentes

      rB(0) = 0
      rB(n) = pB(n-1, 1)

      // rB(n) = pB(n, 1)
function rhymeBell(n=0) {
    if (n===0) {
        return 0;
    } else {
        return partialBell(n-1, 1);
    }
}