Note que um bloco acaba em a_k se, e somente se, a_k<a_(k+1). Entao o numero de cadencia de uma permutacao eh exatamente igual ao numero de vezes em que a_k<a_(k+1) dentro da permutacao, mais um.
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<a_(k+1)) em 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 < [email protected]> 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.
