Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A_n$ be an ordered set: $$A_n = \{ 1,2,3,\dots,n\}$$ Then the powerset of $A_n$ lets call it $P_n$, is $$P_n=\{\emptyset,\{1\},\{2\},\dots,\{1,2\},\{1,3\},\dots,\{1,2,3,\dots,n\}\}$$

How can I find the formula $F(i,j)\colon\mathbb{N}\times\mathbb{N} \to \mathbb{N}$, that given $i$ and $j$ will return $P_n[i][j]$, that is $j$'th element in $i$'th set of $P_n$? I searched google but couldn't find anything like that.

Edit: How about a formula that returns the number of elements in $i$'th set in powerset?

share|improve this question
    
I have to imagine any such formula would be fairly horrible looking. You might have some luck if you restricted yourself to finding the $j^{th}$ element of the $i^{th}$ subset of $A_n$ of size $k$. Certainly there are quick algorithms to do this. –  JSchlather Jan 17 '13 at 11:15
    
To begin with I guess it'd more "natural" or expectable do define $\,F: A_n\times A_n\to A_n\,$ , or even perhaps with the naturals indead of $\,A_n\,$ ... –  DonAntonio Jan 17 '13 at 11:23
    
Why does it say $\mathbb{R\times R}$? Do you mean $\mathbb{N\times N}$ maybe? –  Asaf Karagila Jan 17 '13 at 11:36
    
@AsafKaragila Yes, you are right, I meant $\mathbb{N}$. I fixed it. –  Sunny88 Jan 17 '13 at 11:38
2  
@b-wilson Well, you can order them linearly by size and then lexicographicly in each size. Which is fairly natural. –  JSchlather Jan 17 '13 at 11:44

2 Answers 2

up vote 6 down vote accepted

The easy thing to do is to notice that the $2^n$ subsets of an $n$-element set correspond in a natural way to the binary expansions of the numbers $0\ldots 2^n-1$:

000 {     }
001 {    a}
010 {  b  }
011 {  b,a}
100 {c    }
101 {c,  a}
110 {c,b  }
111 {c,b,a}

If you're willing to order the sets in this way, then the $n$th set contains element $m$ exactly when the binary expansion of the number $n$ has its $m$th-least significant bit set.

Let's write $f_m(n)$ for the function that has value 1 if the $m$th bit of the binary numeral $n$ is a 1, and 0 if it is a 0; it has value 1 if the $n$th subset contains the $m$th element, and 0 if not. Then $f_0(n) = n\bmod 2$, and

$$ \begin{align} f_m(n) & = f_{m-1}\left(\left\lfloor \frac n2\right\rfloor\right) \\ & = f_{0}\left(\left\lfloor \frac n{2^m}\right\rfloor\right) \\ & = \begin{cases}1,&\text{if $\left\lfloor \frac n{2^m}\right\rfloor$ is odd}\\0,&\text{if it is even}\end{cases} \end{align} $$

share|improve this answer
1  
I like this method because it reflects "downwards" in the sense that the formula doesn't really depends on the $n$ chosen. $\mathcal P(A_3)$ is an initial segment of $\mathcal P(A_4)$ in this ordering. –  Asaf Karagila Jan 17 '13 at 13:43
    
Perhaps I should add that it is not at all hard to product an efficient computer algorithm which efficiently generates the $m$th subset in the order where the subsets are ordered first by length, and then lexicographically among subsets of the same length. But writing its output as a closed-form formula would be difficult. This is is because closed-form formulas are not very expressive. –  MJD Jan 17 '13 at 14:17

First, I supose we'd have to define a definite order in $\,P_n:=P(A_n)\,$ , and for this we could do something ressembling the cycles in the permutations group $\,S_n\,$ (if you still haven't studied this don't worry: you won't need it but perhaps it will help others to feel more comfortable with the following), so we can try the lexicographic order.

First, we agree to "order" the elements within each element in $\,P_n\,$ (i.e., within each subset of $\,A_n\,$) in ascending natural order, so that we'll write $\,\{3,5,6,9\}\,$ and not $\,\{5,9,3,6\}\,$ or $\,\{3,6,5,9\}\,$ , etc.

Take now $\,A,B\in P_n\,,\,A=\{i_1,...,i_r\}\,,\,B=\{j_1,...,j_s\}\,,\,\,i_k,j_m\in A_n\,,\,1\leq r,s,\leq n\,\,$ , and define

$$A\prec B\Longleftrightarrow \begin{cases}|A|<|B|\;\;,\text{ or}\\r=s\,\,\wedge\,\,\exists\, 1<k<r\,\,\;s.t.\;\,\,i_1=j_1\,,\,...,i_k=j_k\,,\,i_{k+1}<j_{k+1} \end{cases}$$

Thus, for example, $\,\{6,7,9\}\prec\{1,2,3,4,\}\,\,,\,\,\{4,7,9\}\prec\{4,7,11\} \,$ , etc.

With the above order we can ennumerate the elements of $\,P_n\,$ , beginning from zero to include the empty set:

$$0\to\emptyset\\1\to\{1\}\\...\\n\to\{n\}\\n+1\to\{1,2\}\\n+2\to\{1,3\}\\...\\n+n-1=2n-1\to\{1,n\}\\...$$

The resulting matching is not the nicest thing one could expect to meet in the street, but it is also not that terrible. Now you can define your function, perhaps first trying some easy examples when $\,n=3,4,5\,$...have fun!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.