On 15 mayo, 10:21, Antonio González <gonfe...***gmail.com> wrote:
> jhni...***gmail.com escribió:
>
>
>
>
>
> > On 14 mayo, 12:41, Antonio González <gonfe...***gmail.com> wrote:
> >> jhni...***gmail.com escribió:
>
> >>> On 13 mayo, 15:39, Antonio González <gonfe...***gmail.com> wrote:
> >>>> Se elige un número combinatorio C(n,m) al azar entre todos los
> >>>> coeficientes con n < 2^N, con N grande. ¿Cuánto vale aproximadamente la
> >>>> probabilidad de que sea impar?
> >>>> ¿Será la misma que si se elige un número combinatorio C(n,m) entre todos
> >>>> los que tienen el mismo n, con n elegido al azar entre todos los números
> >>>> n < 2^N?
> >>>> --
> >>>> *** ***Antonio
> >>> y el m cómo se elige?
> >> En el primer caso, el par (n,m) se elige de forma equiporbable entre
> >> todos los posibles pares (n,m).
>
> >> En el segundo, dado un n, m se elige de forma equiprobable entre 0 y n.
>
> >> --
>
> >> *** ***Antonio
>
> > Tengo muy poco tiempo estos días, pero sin pensarlo mucho,
> > si n>=0 la cantidad de C(n,m) impares (m=0,...,n) es 2^u,
> > donde u es la cantidad de unos en la expansión binaria de n.
> > Entonces la cantidad de C(n,m) impares (0<=n<2^N, 0<=m<=n)
> > es suma(C(N,k)2^k, k=0..N) = 3^N
>
> ¿Cómo llegas a este resultado? Yo llego al 3^N utilizando la
> autosimilaridad del triángulo de Tartaglia módulo 2 (análogo al
> triángulo de Serpinski), pero no veo tu camino.
>
> , mientras que el total
>
> > de C(n,m)'s es 1+2+3+...+2^N = (2^N + 1)2^(N-1)
> > y la probabilidad de que C(n,m) sea impar es
>
> > 3^N/[(2^N + 1)2^(N-1)]
>
> > Para el segundo caso no tengo tiempo ahora, espero que
> > alguien lo complete.
>
> Yo también. :-)
>
> --
>
> *** ***Antonio- Ocultar texto de la cita -
>
> - Mostrar texto de la cita -

Si consideras los números en base 2 de 0 a 2^N-1, es decir
0, 1, 10, 11, 100, 101,..., 11...1 (N unos)
se observa que hay C(N,k) de ellos que tienen exactamente
k unos, y cada uno de ellos (digamos n) aporta 2^k coeficientes
binomiales C(n,m) impares, de ahí que el total de esos
coeficientes binomiales impares sea

suma(C(N,k)2^k, k=0..N) = 3^N.

Para el segundo caso habría que calcular

suma((2^u(n))/(n+1), n=0..N)/2^N

o al menos una aproximación asintótica para N grande,
cosa que ahora no se me ocurre cómo hacer.

Pero es claro que los dos casos son diferentes, por
ejemplo para N=2 la probabilidad en el primer caso
es 9/10, mientras que en el segundo caso es 11/12.

Saludos,

jhn

jhnieto***gmail.com escribió:
> On 15 mayo, 10:21, Antonio González <gonfe...***gmail.com> wrote:
>> jhni...***gmail.com escribió:
>>
>>
>>
>>
>>
>>> On 14 mayo, 12:41, Antonio González <gonfe...***gmail.com> wrote:
>>>> jhni...***gmail.com escribió:
>>>>> On 13 mayo, 15:39, Antonio González <gonfe...***gmail.com> wrote:
>>>>>> Se elige un número combinatorio C(n,m) al azar entre todos los
>>>>>> coeficientes con n < 2^N, con N grande. ¿Cuánto vale aproximadamente la
>>>>>> probabilidad de que sea impar?
>>>>>> ¿Será la misma que si se elige un número combinatorio C(n,m) entre todos
>>>>>> los que tienen el mismo n, con n elegido al azar entre todos los números
>>>>>> n < 2^N?
>>>>>> --
>>>>>> Antonio
>>>>> y el m cómo se elige?
>>>> En el primer caso, el par (n,m) se elige de forma equiporbable entre
>>>> todos los posibles pares (n,m).
>>>> En el segundo, dado un n, m se elige de forma equiprobable entre 0 y n.
>>>> --
>>>> Antonio
>>> Tengo muy poco tiempo estos días, pero sin pensarlo mucho,
>>> si n>=0 la cantidad de C(n,m) impares (m=0,...,n) es 2^u,
>>> donde u es la cantidad de unos en la expansión binaria de n.
>>> Entonces la cantidad de C(n,m) impares (0<=n<2^N, 0<=m<=n)
>>> es suma(C(N,k)2^k, k=0..N) = 3^N
>> ¿Cómo llegas a este resultado? Yo llego al 3^N utilizando la
>> autosimilaridad del triángulo de Tartaglia módulo 2 (análogo al
>> triángulo de Serpinski), pero no veo tu camino.
>>
>> , mientras que el total
>>
>>> de C(n,m)'s es 1+2+3+...+2^N = (2^N + 1)2^(N-1)
>>> y la probabilidad de que C(n,m) sea impar es
>>> 3^N/[(2^N + 1)2^(N-1)]
>>> Para el segundo caso no tengo tiempo ahora, espero que
>>> alguien lo complete.
>> Yo también. :-)
>>
>> --
>>
>> Antonio- Ocultar texto de la cita -
>>
>> - Mostrar texto de la cita -
>
> Si consideras los números en base 2 de 0 a 2^N-1, es decir
> 0, 1, 10, 11, 100, 101,..., 11...1 (N unos)
> se observa que hay C(N,k) de ellos que tienen exactamente
> k unos, y cada uno de ellos (digamos n) aporta 2^k coeficientes
> binomiales C(n,m) impares, de ahí que el total de esos
> coeficientes binomiales impares sea
>
> suma(C(N,k)2^k, k=0..N) = 3^N.

Ah, sí. Está claro.

Tal como yo lo hacía era observando que al pasar de 2^(N-1) a 2^N el
triángulo de Tartaglia (mod 2) se amplía con un triángulo sólo de 0's y
dos triángulos idénticos al original, por lo que el número de 1's pasa a
ser el triple. Como en el caso N=0 hay 1, pues queda 3^N.

>
> Para el segundo caso habría que calcular
>
> suma((2^u(n))/(n+1), n=0..N)/2^N
>
> o al menos una aproximación asintótica para N grande,
> cosa que ahora no se me ocurre cómo hacer.
>
> Pero es claro que los dos casos son diferentes, por
> ejemplo para N=2 la probabilidad en el primer caso
> es 9/10, mientras que en el segundo caso es 11/12.
>

Sí, el primer método da más peso a los valores mayores de n (que tienen
muchos m) mientras que el segundo se lo da a los menores.

En Mathworld vienen sumas del tipo u/(n+1), pero no 2^u/(n+1). A ver si
encuentro algo...
--
Antonio

jhnieto***gmail.com escribió:
> On 15 mayo, 10:21, Antonio González <gonfe...***gmail.com> wrote:
>> jhni...***gmail.com escribió:
>>
>>
>>
>>
>>
>>> On 14 mayo, 12:41, Antonio González <gonfe...***gmail.com> wrote:
>>>> jhni...***gmail.com escribió:
>>>>> On 13 mayo, 15:39, Antonio González <gonfe...***gmail.com> wrote:
>>>>>> Se elige un número combinatorio C(n,m) al azar entre todos los
>>>>>> coeficientes con n < 2^N, con N grande. ¿Cuánto vale aproximadamente la
>>>>>> probabilidad de que sea impar?
>>>>>> ¿Será la misma que si se elige un número combinatorio C(n,m) entre todos
>>>>>> los que tienen el mismo n, con n elegido al azar entre todos los números
>>>>>> n < 2^N?
>>>>>> --
>>>>>> Antonio
>>>>> y el m cómo se elige?
>>>> En el primer caso, el par (n,m) se elige de forma equiporbable entre
>>>> todos los posibles pares (n,m).
>>>> En el segundo, dado un n, m se elige de forma equiprobable entre 0 y n.
>>>> --
>>>> Antonio
>>> Tengo muy poco tiempo estos días, pero sin pensarlo mucho,
>>> si n>=0 la cantidad de C(n,m) impares (m=0,...,n) es 2^u,
>>> donde u es la cantidad de unos en la expansión binaria de n.
>>> Entonces la cantidad de C(n,m) impares (0<=n<2^N, 0<=m<=n)
>>> es suma(C(N,k)2^k, k=0..N) = 3^N
>> ¿Cómo llegas a este resultado? Yo llego al 3^N utilizando la
>> autosimilaridad del triángulo de Tartaglia módulo 2 (análogo al
>> triángulo de Serpinski), pero no veo tu camino.
>>
>> , mientras que el total
>>
>>> de C(n,m)'s es 1+2+3+...+2^N = (2^N + 1)2^(N-1)
>>> y la probabilidad de que C(n,m) sea impar es
>>> 3^N/[(2^N + 1)2^(N-1)]
>>> Para el segundo caso no tengo tiempo ahora, espero que
>>> alguien lo complete.
>> Yo también. :-)
>>
>> --
>>
>> Antonio- Ocultar texto de la cita -
>>
>> - Mostrar texto de la cita -
>
> Si consideras los números en base 2 de 0 a 2^N-1, es decir
> 0, 1, 10, 11, 100, 101,..., 11...1 (N unos)
> se observa que hay C(N,k) de ellos que tienen exactamente
> k unos, y cada uno de ellos (digamos n) aporta 2^k coeficientes
> binomiales C(n,m) impares, de ahí que el total de esos
> coeficientes binomiales impares sea
>
> suma(C(N,k)2^k, k=0..N) = 3^N.

Ah, sí. Está claro.

Tal como yo lo hacía era observando que al pasar de 2^(N-1) a 2^N el
triángulo de Tartaglia (mod 2) se amplía con un triángulo sólo de 0's y
dos triángulos idénticos al original, por lo que el número de 1's pasa a
ser el triple. Como en el caso N=0 hay 1, pues queda 3^N.

>
> Para el segundo caso habría que calcular
>
> suma((2^u(n))/(n+1), n=0..N)/2^N
>
> o al menos una aproximación asintótica para N grande,
> cosa que ahora no se me ocurre cómo hacer.
>
> Pero es claro que los dos casos son diferentes, por
> ejemplo para N=2 la probabilidad en el primer caso
> es 9/10, mientras que en el segundo caso es 11/12.
>

Sí, el primer método da más peso a los valores mayores de n (que tienen
muchos m) mientras que el segundo se lo da a los menores.

En Mathworld vienen sumas del tipo u/(n+1), pero no 2^u/(n+1). A ver si
encuentro algo...
--
Antonio

Sea s(N) = sum_{n=0}^N 2^u(n)/(n+1). Demuestrese que

s(2^R-1) > (3/2)^R.

Pista: agrupar términos por el número de unos en la expansión binaria.

Un saludo.

--
+-------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, markoriedelde***yahoo.de |
| http://www.geocities.com/markoriedelde/index.html |
+-------------------------------------------------------------+

Sea s(N) = sum_{n=0}^N 2^u(n)/(n+1). Demuestrese que

s(2^R-1) > (3/2)^R.

Pista: agrupar términos por el número de unos en la expansión binaria.

Un saludo.

--
+-------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, markoriedelde***yahoo.de |
| http://www.geocities.com/markoriedelde/index.html |
+-------------------------------------------------------------+

jhnieto***gmail.com escribió:
>
> Para el segundo caso habría que calcular
>
> suma((2^u(n))/(n+1), n=0..N)/2^N
>

Una cosa que he determinado, que no sé si será útil, es lo siguiente:

Sea la función generatriz

F(x) = sum_0^(2^N-1) x^(n+1) 2^u(n)/(n+1)

(para la que buscamos F(1). Si derivamos aquí

f(x) = F'(x) = sum_0^(2^N-1) x^n 2^u(n) =

= 1 + 2(x + x^2 + x^4 + x^8 + ...) +

+ 2^2(x^(1+2) + x^(1+4) + x^(2+4) ...) +

+ 2^3(x^(1+2+4)....) + ...

que se puede escribir como el producto

f(x) = (1+2x)(1+2x^2)(1+2x^4) ...(1+2x^(2^(N-1))

= prod_(k=0)^(N-1) (1 + 2x^(2^k))

pero no veo que este productorio tenga una expresión cerrada que se
pueda integrar.

--

Antonio

jhnieto***gmail.com escribió:
>
> Para el segundo caso habría que calcular
>
> suma((2^u(n))/(n+1), n=0..N)/2^N
>

Una cosa que he determinado, que no sé si será útil, es lo siguiente:

Sea la función generatriz

F(x) = sum_0^(2^N-1) x^(n+1) 2^u(n)/(n+1)

(para la que buscamos F(1). Si derivamos aquí

f(x) = F'(x) = sum_0^(2^N-1) x^n 2^u(n) =

= 1 + 2(x + x^2 + x^4 + x^8 + ...) +

+ 2^2(x^(1+2) + x^(1+4) + x^(2+4) ...) +

+ 2^3(x^(1+2+4)....) + ...

que se puede escribir como el producto

f(x) = (1+2x)(1+2x^2)(1+2x^4) ...(1+2x^(2^(N-1))

= prod_(k=0)^(N-1) (1 + 2x^(2^k))

pero no veo que este productorio tenga una expresión cerrada que se
pueda integrar.

--

Antonio