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 <[email protected]> wrote: > 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.
