Secuencias estrictamente crecientes de enteros positivos

Question

Sea $\alpha$ y $\beta$ enteros no negativos. Supongamos que el número de secuencias estrictamente crecientes de enteros $a_0,a_1,\dots,a_{2014}$ que satisfacen $0 \leq a_m \leq 3m$ es $2^\alpha (2\beta + 1)$. Encuentra $\alpha$.

Necesitamos $0 \leq a_0 \leq 0, 0 \leq a_1 \leq 3, 0 \leq a_2 \leq 6,\ldots,0 \leq a_{2014} \leq 6042$. También necesitamos asegurarnos de que la secuencia sea estrictamente creciente. ¿Cómo contamos el número de secuencias que cumplen ambas condiciones?

Answer 1

Creo que podemos hacer esto por inducción.

Caso Base: Hay $1$ posibilidad para una secuencia con solo $a_0$, que es $a_0=0$.

Inducción: Supongamos que hay $n_l$ posibilidades para $a_0,a_1,a_2,...,a_m$ donde $a_m=l$. Entonces, hay $n_l$ posibilidades más para $a_{m+1}=l+1$, $n_l$ posibilidades más para $a_{m+1}=l+2$, $n_l$ posibilidades más para $a_{m+1}=l+3$, y así sucesivamente hasta $n_l$ posibilidades más para $a_{m+1}=3m+3$. Por lo tanto, cada posibilidad añadida a $a_{m+1}=k$ también se añade a $a_{m+1}=k-1$ excepto para $a_m=k-1$, que solo se agrega a este último. Esto significa que las posibilidades para $a_{m+1}=k$ son las mismas de $a_{m+1}=k-1$ más las de $a_m=k-1$.

A través de este razonamiento, podemos crear un algoritmo para encontrar cuántas posibilidades hay para $a_{2014}$ sumando todos los $n_l$ para $m=2014$.

# last_posses[k] es el número de secuencias satisfactorias de a_0 -> a_{m-1} tal que a_{m-1}=k
last_posses = []
# Establecer el caso base para m=0
last_posses.append(1)
# De m=1 a m=2015
for m in range(1, 2015):
    # new_posses[k] es el número de secuencias satisfactorias de a_0 -> a_m tal que a_m=k
    # Para k=0, el número de posibilidades es 0 para m > 0
    new_posses = [0]
    # Establecer el número de posibilidades para a_m=k como el de a_{m-1}=k-1 y a_m=k-1
    for k in range(1, 3*m+1):
        last_posses_k_1 = 0
        if k-1 < len(last_posses): last_posses_k_1 = last_posses[k-1]
        new_posses.append(last_posses_k_1+new_posses[k-1])
    # Imprimir las posibilidades para a_m
    print(m, sum(new_posses))
    # Finalmente, establecer last_posses para el siguiente valor de m:
    last_posses = new_posses

Para $m=2014$, obtenemos la respuesta de: $$300944681162684001151640196315570262912490285211828310556664649918797521048397756803724053493686234060772983644188615444364445715960971301814799375024467161174877911666302036867022738910237798614296647918450594305601536435465706257207839814116587503183522505420084832559595270057408005238605282753319199407094154605981402683531379773298133942467544029052620796868693901784114527997579479753200598973777281859052046519450677881065084861507468419025958959953826337633305923535438747028970142464977361390731394672987346144870805049482131446926859004559376848744374972762195525506379809670785589495124765016114867284730645855780137158044735688990951545587035696472146620282770740267912437701056054664828894730285292791238218871206260237480379487519489436560306357273878201791897613632153669304564546842506650005980913922087491157551215418102645927904090739395162946608767100217498521240507725493744045101849902093215987940776919386934640595294311584263890233837313006873467131971139141886401816791198029630347755204656905868820864062639204629334670687853180198627727428576528906944350084758351823830312063302990759042317004364195840133199751919342348023278027517025456411260931744321669818513549277183561757000597420548294365570155764490793396086533615146932320730089950925304245458617829868908892874147994788779309907913132288474242819351325009580);$$ El mayor potencia de $2$ que divide este número es $2^{11}$ (que se puede encontrar fácilmente por prueba y error usando un shell de Python para dividir este número por potencias de 2), entonces $\alpha=11$.

Answer 2

El número de secuencias crecientes $a_0, a_1, \dots, a_n$ tales que $a_k \leq 3k$ es claramente $\binom{3(n+1)}{n+1}/(2n+3)$.

Desde aquí usamos la fórmula de Polignac para encontrar $v_2$.

Tenemos $v_2(\binom{3\times 2015}{2015}/(2(2014)+3))=v_2(3\times2015)!-v_2(2\times 2015)!-v_2(2015)!$.

Usando la fórmula de Polignac esto es igual a:

$6036-4020-2005=11$.

(en lugar de usar la fórmula de Polignac también podríamos haber utilizado el teorema de Kummer).