Counting Possible Operations

Algebra Level 4

Let $A$ be any set:

An operation $*$ on $A$ is a rule which assigns to each ordered pair $(a,b)$ of elements of $A$ exactly one element $a*b$ in $A.$

If, for example, $A$ is a set consisting of just two distinct elements, say $a$ and $b$ , each operation on $A$ may be described by a table such as the one below:

$(x,y)$				$x*y$
$(a,a)$
$(a,b)$
$(b,a)$
$(b,b)$

Where $x*y$ could be either of the elements of $A$ ( $a$ or $b$ ) for any $(x,y)$ in $A$ . In general, there are many possible operations on a given set. A set containing just two elements for example, has $16$ possible operations.

How many possible operations are there on a set containing $n$ elements?

2^n

2^{n^2}

n^2

n^3

n^n

n^{n^2}

1 solution

Akeel Howell
Sep 7, 2017

Consider a set $A$ with $n$ distinct elements, $a_1,a_2,a_3, \cdots, a_n$ . For each time an element, $a_i$ , is the first element of an ordered pair, all $n$ elements can be the second one. Since this happens $n$ times (for $n$ elements) there are $n(n) = n^2$ possible ordered pairs of elements of $A$ in which $a_i$ is the first element $(i \in \mathbb{Z^+} \leq n)$ . Thus, there are $n^2$ possible ordered pairs of elements of $A$ .

Since every operation on $A$ must assign a unique element of $A$ to each ordered pair of elements of $A$ , we have $n$ possible values of $a_i*a_j$ , where $*$ is the operation and $i,j \in \mathbb{Z^+} \leq n$ . This suggests that there are $n$ possible operations for each ordered pair of elements of $A$ . Given that there are $n^2$ possible ordered pairs of elements of $A$ , it can thus be seen that there are $\underbrace{n \times n \times n \times \cdots \times n}_{n^2 \text{ terms }} = n^{n^2}$ possible operations on $A$ .

When you say "a set $A$ ", this implicitly assumes that the elements of $A$ are distinct (since the definition of set doesn't allow repeated elements). A simple thing to note is that an operator $\ast$ on $A$ is basically a map $\ast\colon A\times A\to A$ and it thus follows that there are $|A|^{|A\times A|}=n^{n\times n}=n^{n^2}$ such maps (a map $f\colon X\to Y$ can be constructed in $|Y|^{|X|}$ ways).

Prasun Biswas - 3 years, 9 months ago

Counting Possible Operations

1 solution

0 pending reports