P.S.: Outro jeito de fazer: defina o numero de "crescencia" como o numero
de blocos CRESCENTES maximais. Mostre que, para cada permutacao, a soma do
numero de cadencia com o de "crescencia" eh n+1 (confira isto!). Entao o
somatorio das cadencias com as crescencias de todas as permutacoes dah
(n+1).n!=(n+1)!. Por simetria, a soma das cadencias eh igual aa soma das
crescencias, entao (n+1)!/2 para cada soma.
On Fri, May 24, 2019 at 8:13 PM Ralph Teixeira wrote:
> Note que um bloco acaba em a_k se, e somente se, a_k numero de cadencia de uma permutacao eh exatamente igual ao numero de vezes
> em que a_k
> Por exemplo, em σ = (4, 2, 1, 5, 6, 3), temos apenas dois pares
> consecutivos crescentes, a saber, 1<5 e 5<6. Portanto, temos 2+1=3 blocos.
>
> Entao contar o numero de cadencia de todas as permutacoes eh o mesmo que
> contar todas as sequencias consecutivas crescentes (do tipo a_k todas elas, e somar (n!) (por causa daquele "mais um " em cada permutacao).
>
> Isto dito, se voce olhar todos os pares consecutivos que aparecem em todas
> as permutacoes, por simetria, metade deles serah crescente e metade
> decrescente. Ou seja, de todos os (n-1).n! pares consecutivos, temos
> (n-1).n!/2 que sao crescentes.
>
> Entao a resposta eh (n-1).n!/2+n!=(n+1)!/2.
>
> Abraco, Ralph.
>
> On Fri, May 24, 2019 at 5:23 PM Carlos Monteiro <
> cacacarlosalberto1...@gmail.com> wrote:
>
>> Sejam n um inteiro positivo e σ = (a1, . . . , an) uma permutação de {1,
>> . . . , n}. O número
>> de cadência de σ é o número de blocos decrescentes maximais. Por exemplo,
>> se n = 6 e
>> σ = (4, 2, 1, 5, 6, 3), então o número de cadência de σ é 3, pois σ
>> possui 3 blocos (4, 2, 1), (5),
>> (6, 3) descrescentes e maximais. Note que os blocos (4, 2) e (2, 1) são
>> decrescentes, mas não
>> são maximais, já que estão contidos no bloco (4, 2, 1).
>> Calcule a soma das cadências de todas as permutações de {1, . . . , n}.
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> acredita-se estar livre de perigo.
>
>
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
