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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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?

*****

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?


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
=========================================================================