Reducir la suma de una función indicadora a una forma más sencilla.

Question

Quiero simplificar lo siguiente:

$\sum_{n=0}^x 1 - (1 - I[a \ne 0] * I[a \ge b]) * (1 - I[b \ne 0] * I[b \ge c]) * (1 - I[c \ne 0] * I[c \ge d]) * (1 - I[d = 0])$

Answer 1

Dejemos que $x$ ser una base $y$ número entero no negativo con un máximo de $4$ dígitos. Sea $a$ , $b$ , $c$ , $d$ tal que $0\le a,b,c,d<y$ y se cumplen las siguientes ecuaciones: $$\left\{\begin{aligned} a&=\lfloor\frac{n}{1000}\rfloor\ mod\ 10 \\[2ex]b&=\lfloor\frac{n}{100}\rfloor\ mod\ 10 \\[2ex]c&=\lfloor\frac{n}{10}\rfloor\ mod\ 10 \\[2ex]d&=\lfloor n\rfloor\ mod\ 10 \end{aligned}\right.$$

La expresión en la pregunta, $1-(1-I[a\neq0]I[a\ge b])(1-I[b\neq0]I[b\ge c])(1-I[c\neq0]I[c\ge d])(1-I[d=0])$ se evaluará a $0$ si y sólo si $x$ es un valor no nulo $z$ -(es decir, la cifra más significativa de $x$ es el $z$ de la derecha) tal que todos los $z$ Los dígitos están en orden ascendente. En caso contrario, se evaluará como $1$ .

Que todos los valores posibles de $x$ cuya expresión se evalúa como $1$ llamarse números omitidos y que todos los valores posibles de $x$ cuya expresión se evalúa como $0$ llamarse números no omitidos .

Por cada no omitido $x$ , dejemos que $g(x)$ sea el número de no omitido números hasta $x$ .

$g(x)$ puede describirse como sigue:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ &\binom{y-1}1+ \sum_{i=y-c}^{y-2}\binom i1+(d-c) \\y^2\le x\le y^3-1\to\ &\binom{y-1}1+\binom{y-1}2+ \sum_{i=y-b}^{y-2}\binom i2+ \sum_{i=y-c}^{y-b-2}\binom i1+(d-c) \\y^3\le x\le y^4-1\to\ &\binom{y-1}1+\binom{y-1}2+\binom{y-1}3\\&+ \sum_{i=y-a}^{y-2}\binom i3+ \sum_{i=y-b}^{y-a-2}\binom i2+ \sum_{i=y-c}^{y-b-2}\binom i1+(d-c) \end{aligned}\right.$

Para cada número entero $n\ge0$ y que exista una función $h_n:\{x|x\in\mathbb Z,x\ge n\}\to\mathbb Z$ tal que $h_n(x)=\sum_{i=n}^x\binom in$ . Entonces $g$ puede replantearse de la siguiente manera:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ &\binom{y-1}1\\&+ h_1(y-2)-h_1(y-c-1)+(d-c) \\y^2\le x\le y^3-1\to\ &\binom{y-1}1+\binom{y-1}2\\&+ h_2(y-2)-h_2(y-b-1)\\&+ h_1(y-b-2)-h_1(y-c-1)+(d-c) \\y^3\le x\le y^4-1\to\ &\binom{y-1}1+\binom{y-1}2+\binom{y-1}3\\&+ h_3(y-2)-h_3(y-a-1)\\&+ h_2(y-a-2)-h_2(y-b-1)\\&+ h_1(y-b-2)-h_1(y-c-1)+(d-c) \end{aligned}\right.$

Se puede demostrar que $h_n(x)=\binom xn+\binom {x-1}n+...+\binom nn=\binom{x+1}{n+1}$ . A continuación, la función puede replantearse de nuevo como sigue:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ &\binom{y-1}1+ \binom{y-1}2-\binom{y-c}2+(d-c) \\y^2\le x\le y^3-1\to\ &\binom{y-1}1+\binom{y-1}2+ \binom{y-1}3-\binom{y-b}3\\&+ \binom{y-b-1}2-\binom{y-c}2+(d-c) \\y^3\le x\le y^4-1\to\ &\binom{y-1}1+\binom{y-1}2+\binom{y-1}3+ \binom{y-1}4-\binom{y-a}4\\&+ \binom{y-a-1}3-\binom{y-b}3+ \binom{y-b-1}2-\binom{y-c}2\\&+(d-c) \end{aligned}\right.$

Lo siguiente se convertirá en forma polinómica por orden:

1. todos los casos de $\binom{y-1}1+\binom{y-1}2$ En $\frac{y(y-1)}2$
2. la única instancia de $\binom{y-1}3+\binom{y-1}4$ En $\frac{y(y-1)(y-2)(y-3)}{24}$
3. el resto $\binom{y-1}3$ En $\frac{(y-1)(y-2)(y-3)}6$
4. todos los casos de $-\binom{y-c}2+(d-c)$ En $\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2$

A continuación, la descripción de la función se reordena como sigue:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ & \frac{y(y-1)}2+\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2 \\y^2\le x\le y^3-1\to\ & \frac{y(y-1)}2+\frac{(y-1)(y-2)(y-3)}6\\& +\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2\\& +\binom{(y-1)-b}2-\binom{y-b}3 \\y^3\le x\le y^4-1\to\ & \frac{y(y-1)}2+\frac{y(y-1)(y-2)(y-3)}{24}\\& +\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2\\& +\binom{(y-1)-b}2-\binom{y-b}3\\& +\binom{(y-1)-a}3-\binom {y-a}4 \end{aligned}\right.$

Considere que cada instancia de $\frac{y(y-1)}2$ y $-\frac{y(y-1)}2$ se puede anular, dejando el descriptor de función final:

---

$$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ & \frac{c((2y-3)-c)}2+d \\y^2\le x\le y^3-1\to\ & \frac{(y-1)(y-2)(y-3)}6 +\frac{c((2y-3)-c)}2+d\\& +\binom{(y-1)-b}2-\binom{y-b}3 \\y^3\le x\le y^4-1\to\ & \frac{y(y-1)(y-2)(y-3)}{24} +\frac{c((2y-3)-c)}2+d\\& +\binom{(y-1)-b}2-\binom{y-b}3 +\binom{(y-1)-a}3-\binom {y-a}4 \end{aligned}\right.$$

---

Para cada número entero $x\ge0$ , dejemos que $f(x)$ sea el número de omitido números hasta $x$ y para cada número entero $x>0$ , dejemos que $j(x)$ sea el mayor número no omitido que no sea mayor que $x$ . En el caso especial de que $x=0$ El valor de $j(x)$ es $0$ .

Por definición de $g$ ,

$$f(x)=x+1-g(j(x))\text.$$

---

Notas:
1. $g(x)$ puede se puede enunciar sin binomios. He dejado algunos binomios como están porque los polinomios en los que se convierten son demasiado complejos.
2. Puede simplificar $g(x)$ un poco al enchufar el valor de $y$ y realizar algún cálculo previo, o puede dejarlo estar y hacer que el compilador haga el cálculo previo por usted.
3. $g(x)$ sólo pretende producir el resultado esperado si $x$ no se salta. Por eso he definido $j$ .