Re: [obm-l] F(F(x)) = x e combinatoria

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

  Oi Claudio,  
  Vamos la':

>
>Oi, Artur e Duda:
>
>Esse problema do livro do Elon me sugeriu dois problemas de combinatoria.
> 
>1) Seja A um conjunto qualquer e F: A -> A uma funcao tal que, para todo x
>em A vale F(F(x)) = x. F eh chamada uma involucao em A. Eh facil ver que
>toda involucao em A eh uma bijecao.
>
>Se A for finito e |A| = n, entao existem n! bijecoes de A em A.
>
>Pergunta: Qual o numero de involucoes em A?
>
   Seja a_n esse numero. Entao a_(n+1)=a_n+n.a_(n-1) (veja para onde vai o
n+1: se fica fixo caimos no caso anterior, senao escolhemos um dos outros n
elementos para permutar com ele e caimos no caso n-1 para o resto).
Considerando f(x)=serie(a_n.x^n/n!), isso da'  f'(x)=f(x)+x.f(x), e olhando
para os primeiros valores, temos f(x)=e^(x+x^2/2).  Se eu nao errei as
contas, f(n) deve ser assintoticamente algo como raiz(2).(n/e)^(n/2).
Veja A000085 na encyclopedia of integer sequences, ou, mais diretamente,
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismum.cgi
   
>*****
>
>2) Seja A um conjunto finito com |A| = n (e portanto |P(A)| = 2^n).
>Seja F: P(A) -> P(A) uma funcao tal que, para todos X e Y em P(A):
>F(F(X)) = X   
>e   
>X contido em Y ==> F(Y) contido em F(X).
>
>Pergunta: Quantas funcoes de P(A) em P(A) existem com essas duas
>propriedades?

   Primeiro vou caracterizar tais f. Elas devem ser do tipo que eu descrevi
na minha mnensagem anterior (mesmo no caso infinito): deve existir uma
involucao f de X tal que F(X)={f(y), y nao esta' em X}. Assim, a resposta e'
o mesmo a_n do item anterior. Para provar isso, note primeiro que dado a em
A existe f(a) em A com F({a})=A\{f(a)}. De fato, se F({a}) esta' contido em
A\{c,d}, {a} contem F(A\{c,d}), que contem estritamente F(A\{c}), que contem
estritamente F(A)=vazio (de fato F e' bijecao), absurdo. Como F({a}) esta'
contido estritamente em F({}), segue nossa afirmacao. Como F(X) e' a
intersecao dos F({x}) para x em X, basta provar que f e' involucao, mas se
f(f(a)) nao e' a, como F({f(a)})=A\{f(f(a))}, temos que a pertence a
F({f(a)}), mas entao A\{f(a)}=F({a}) conteria F(F({f(a)}))={f(a)}, absurdo.

   Abracos,
             Gugu
 

>
>
>Um abraco,
>Claudio.
>
>
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>=========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================