Quantas operações diferentes é possível definir em um conjunto A que tenha exatamente n elementos? Entre essas operações, quantas são comutativas?

Passo 1

O enunciado pede para contar quantas operações binárias diferentes podem ser definidas num conjunto A com exatamente n elementos e, dentre elas, quantas satisfazem a propriedade de comutatividade. O conteúdo usado será a combinatória de funções, pois uma operação binária é simplesmente uma função de Atimes A em A.

Passo 2

Uma operação binária em A é uma função
ast : A times A to A
Como lvert Arvert = n, o conjunto Atimes A tem lvert Atimes Arvert = n^2 elementos. Para cada um desses n^2 pares ordenados podemos escolher livremente uma imagem em um dos n elementos de A. Logo, o número total de operações possíveis é
n^n^2

Passo 3

Para que a operação seja comutativa precisamos que
forall,a,bin A, aast b = bast a
Isso significa que só precisamos definir a imagem nos pares ordenados (a,b) com a<= b (ou seja, nos pares não ordenados com repetição). O número de tais pares é o número de combinações com repetição de n elementos tomados 2 a 2, que é
binomn+12 ;=;n(n+1)2
Em cada um desses tfracn(n+1)2 pares podemos escolher um dos n valores de saída, de modo que o total de operações comutativas é
n^n(n+1)2

Resposta

Total de operações: n^n^2
Total de operações comutativas: n^n(n+1)2

Exercícios relacionados