[obm-l] Numero de involucoes em A

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Seja A um conjunto finito com n elementos e F uma involucao em A (ou seja,
uma funcao F:A -> A que obedece a F(F(x)) = x para todo x em A).

Para cada x em A existem duas hipoteses:
1) F(x) = x (x eh um ponto fixo de F)
ou
2) F(x) = y <> x  e  F(y) = x.

Assim, dada F, podemos particionar A em subconjuntos de 1 ou 2 elementos
tais que, se B eh um desses subconjuntos, entao F(B) = B.

Por outro lado, dada uma particao de A em subconjuntos de 1 ou 2 elementos,
podemos definir F:A -> A tal que:
se {x} eh um subconjunto da particao, entao F(x) = x
e
se {x,y} eh um subconjunto da particao, entao F(x) = y  e  F(y) = x.

Conclusao: o numero de involucoes em A eh igual ao numero de maneiras de se
particionar A em subconjuntos de 1 ou 2 elementos.

*****

Consideremos uma particao de A em p conjuntos unitarios e q conjuntos de 2
elementos (binarios?). Claro que n = p + 2q.

Os p conjuntos unitarios podem ser escolhidos de Binom(n,p) = Binom(n,2q)
maneiras.

Uma vez escolhidos os unitarios, ficamos com n - p = 2q elementos de A para
formar q pares, o que pode ser feito de (2q)!/(2^q*q!) maneiras.

Logo, o numero de particoes de A em p conjuntos unitarios e q conjuntos
binarios eh igual a Binom(n,2q)*(2q)!/(2^q*q!) = n!/(q!*(n-2q)!*2^q)

Agora eh soh somar estes numeros, com q variando de 0 ateh [n/2]:
No. de Involucoes em A = SOMA(0<=q<=[n/2]) n!/(q!*(n-2q)!*2^q).

Alguem sabe determinar uma formula fechada para esta soma?

Com uma planilha eu achei o seguinte:
|A|   No. de Involucoes em A
 1    1
 2    2
 3    4
 4    10
 5    26
 6    76
 7    232
 8    764
 9    2620
10    9496
11    35696
12    140152
13    568504
14    2390480
15    10349536
16    46206736
17    211799312
18    962854399
19    4154972365
20    16556644271
21    60372347071

Tambem vale conferir o site:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismum.cgi

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