Supongamos que nos preguntan acerca de la máxima esperada de largo plazo cuando seleccionamos $m$ elementos de un total de $n.$
Para una longitud de ejecución en más de $k$ primero debemos elegir una carrera de algunos de longitud
posiblemente precedido por una brecha, dando (la variable $w$ cuenta el número
de los elementos de la tupla)
$$\frac{1}{1-z} \sum_{q=1}^k w^q z^p $$
seguido por una secuencia de brechas seguido por una carrera
$$\frac{z}{1-z} \sum_{q=1}^k w^q z^p$$
posiblemente seguido en la final por otra brecha
$$\frac{1}{1-z}.$$
Esto le da a la generación de la función
$$f_k(z,w) = \frac{1}{(1-z)^2} \left(\sum_{q=1}^k w^q z^q \ \ derecho)
\sum_{p\ge 0} \left( \frac{z}{1-z} \sum_{q=1}^k w^q z^q \ \ derecho)^p.$$
Estamos interesados en el número total de
$$[z^n] [w^m]
\sum_{k=1}^m k (f_k(z,w) - f_{k-1}(z, w))
\\ = [z^n] [w^m]
\left(m f_m(z,w) - \sum_{k=1}^{m-1} f_k(z, w)\right).$$
La suma de los componentes en $f_k(z, w)$ es
$$\sum_{p\ge 0}
\left( \frac{wz^2}{1-z} \sum_{q=0}^{k-1} w^q z^q \ \ derecho)^p
\\ = \frac{1}{1-wz^2(1-w^k z^k)/(1-z)/(1-wz)}.$$
En este momento parece que estamos mucho mejor trabajar con
$$g_k(z,w) = \frac{1}{(1-wz)^2} \left(\sum_{q=1}^k z^q \ \ derecho)
\sum_{p\ge 0} \left( \frac{wz}{1-wz} \sum_{q=1}^k z^q \ \ derecho)^p$$
que se da por la suma de componentes
$$\sum_{p\ge 0} \left( \frac{wz^2}{1-wz} \sum_{q=0}^{k-1} z^q \ \ derecho)^p
\\ = \frac{1}{1-wz^2(1-z^k)/(1-wz)/(1-z)}.$$
Este rendimientos
$$g_k(z,w) = \frac{1}{1-wz} \left(\sum_{q=1}^k z^q \ \ derecho)
\frac{1}{1-wz-wz^2(1-z^k)/(1-z)}
\\ = \frac{1}{1-wz} \left(\sum_{q=1}^k z^q \ \ derecho)
\frac{1}{1-w(z-z^2+z^2(1-z^k))/(1-z)}
\\ = \frac{1}{1-wz} \left(\sum_{q=1}^k z^q \ \ derecho)
\frac{1}{1-w(z-z^{k+2}))/(1-z)}.$$
Extraer el coeficiente de en $[w^{n-m}]$ obtenemos
$$\left(\sum_{q=1}^k z^q \ \ derecho)
\sum_{p=0}^{n-m} z^{n-m-p} \frac{z^p(1-z^{k+1})^p}{(1-z)^p}
\\ = z^{n-m} \left(\sum_{q=1}^k z^q \ \ derecho)
\sum_{p=0}^{n-m} \frac{(1-z^{k+1})^p}{(1-z)^p}
\\ = z^{n-m}
\left(\left(\frac{1-z^{k+1}}{1-z}\right)^{n-m+1}-1\right).$$
Extraer el coeficiente de en $[z^n]$ obtenemos
$$[z^n] z^{n-m}
\left(\frac{1-z^{k+1}}{1-z}\right)^{n-m+1}
= [z^m] \left(\frac{1-z^{k+1}}{1-z}\right)^{n-m+1}.$$
Este es
$$\sum_{p=0}^{\lfloor m/(k+1)\rfloor}
{n-m+1\elegir p} (-1)^p {n-m+m-p(k+1)\elegir n-m}
\\ = \sum_{p=0}^{\lfloor m/(k+1)\rfloor}
{n-m+1\elegir p} (-1)^p {n-p(k+1)\elegir n-m}.$$
Sustituir esto en la suma fórmula para obtener
$$m {n\elegir m}
- \sum_{k=1}^{m-1} \sum_{p=0}^{\lfloor m/(k+1)\rfloor}
{n-m+1\elegir p} (-1)^p {n-p(k+1)\elegir n-m}
\\ = {n\elegir m}
- \sum_{k=1}^{m-1} \sum_{p=1}^{\lfloor m/(k+1)\rfloor}
{n-m+1\elegir p} (-1)^p {n-p(k+1)\elegir n-m}.$$
Este es
$${n\elegir m}
+ \sum_{p=1}^m
{n-m+1\elegir p} (-1)^p {n-p\elegir n-m}
\\ - \sum_{k=0}^{m-1} \sum_{p=1}^{\lfloor m/(k+1)\rfloor}
{n-m+1\elegir p} (-1)^p {n-p(k+1)\elegir n-m}
\\ = {n\elegir m}
+ \sum_{p=1}^m
{n-m+1\elegir p} (-1)^p {n-p\elegir n-m}
\\ - \sum_{1\le pq \le m}
{n-m+1\elegir p} (-1)^p {n-pq\elegir n-m}.$$
Ahora debemos hacer una última simplificación en el primer y el segundo término
juntos, los cuales son
$$\sum_{p=0}^m
{n-m+1\elegir p} (-1)^p {n-p\elegir n-m}$$
y presentar para su uso con el método Egorychev
$${n-p\elegir n-m} = {n-p\elegir m-p}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m-p+1}} (1+z)^{n-p} \; dz.$$
Tenga en cuenta que esto es igual a cero cuando p $\gt m$ así que podemos extender $p$ a infinito,
llegar
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m+1}} (1+z)^{n}
\sum_{p\ge 0} {n-m+1\elegir p} (-1)^p \frac{z^p}{(1+z)^p}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m+1}} (1+z)^{n}
\left(1-\frac{z}{1+z}\right)^{n-m+1}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m+1}} (1+z)^{n}
\frac{1}{(1+z)^{n-m+1}}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m+1}} (1+z)^{m-1}
\; dz = [z^m] (1+z)^{m-1} = 0.$$
Dividiendo por ${n\elegir m}$ para la expectativa de
y sin el cero, la contribución de los dos primeros términos
de este modo, obtener por la expectativa de la máxima longitud de
$${\large\color{#080}{{n\elegir m}^{-1} \sum_{1\le pq \le m}
{n-m+1\elegir p} (-1)^{p+1} {n-pq\elegir n-m}}}.$$
El lector es invitado a probar esto de una manera diferente,
quizás sin el uso ordinario de la generación de funciones.
El Arce de código que se utilizó para verificar estos incluyen un total
la enumeración de rutina era la siguiente:
con(planta);
sr :=
proc(n, m)
local sel, sel2, maxr, cur, res, pos;
sel := firstcomb(n, m);
res := 0;
mientras que el tipo(sel, `set`)
sel2 := convert(sel, `lista`);
maxr := -1; p := 1;
para pos de 2 a m hacer
si sel2[pos] = 1 + sel2[pos-1], a continuación,
p := p + 1;
otra cosa
si cur > maxr, a continuación,
maxr := cur;
fi;
cur := 1;
fi;
od;
si cur > maxr, a continuación,
maxr := cur;
fi;
res := res + maxr;
sel := nextcomb(sel, n);
od;
res;
end;
f :=
proc(k)
de base local;
base := añadir(w^q*z^q, q=1..k);
1/(1-z)^2*base*sum((z/(1-z)*base)^p, p=0..infinity);
end;
Hf :=
proc(m)
m*f(m)-añadir(f(k), k=1..m-1);
end;
Qf :=
proc(n, m)
coeftayl(coeftayl(Hf(m), w=0, m), z=0, n);
end;
g :=
proc(k)
de base local;
base := añadir(z^q, q=1..k);
1/(1-w*z)^2*base*sum((w*z/(1-w*z)*base)^p, p=0..infinity);
end;
Hg :=
proc(m)
m*g(m)-agregar(g(k), k=1..m-1);
end;
Qg :=
proc(n, m)
coeftayl(coeftayl(Hg(m), w=0, n-m), z=0, n);
end;
X :=
proc(n, m)
locales CF;
CF := (n,m,k)->
agregar(binomial(n-m+1,p)*(-1)^p*binomial(n-p*(k+1), n-m),
p=0..piso(m/(k+1)));
m*binomial(n,m) - agregar(CF(n,m, k), k=1..m-1);
end;
X1 :=
proc(n, m)
local p, q, res;
res := binomial(n,m) +
agregar(binomial(n-m+1,p)*(-1)^p*binomial(n-p,n-m), p=1..m);
para p a m hacer
para q el suelo(m/p) ¿
res := res -
binomial(n-m+1,p)*(-1)^p*binomial(n-p*q,n-m);
od;
od;
res;
end;
X2 :=
proc(n, m)
local p, q, res;
res := 0;
para p a m hacer
para q el suelo(m/p) ¿
res := res +
binomial(n-m+1,p)*(-1)^(p+1)*binomial(n-p*q,n-m);
od;
od;
res;
end;
