#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Lecture 39 - Chapter 3: Databases

2»

• Options
51.
edited June 2018

Matthew wrote:

For this I am thankful for the patience and guidance of the people on this forum as I muddle about.

By the way: I was trying to make fun of myself, not you, when I said the construction "completely doesn't work". I thought it did, and said so! When Simon said there was a "mild problem", it made me think about how I'm rarely so polite.

Also by the way: Simon is a friend of mine, so we always joke around. If I say annoying stuff when he's around, that might be the reason. I will try to restrain myself.

Comment Source:Matthew wrote: > For this I am thankful for the patience and guidance of the people on this forum as I muddle about. By the way: I was trying to make fun of myself, not you, when I said the construction "completely doesn't work". I thought it did, and said so! When Simon said there was a "mild problem", it made me think about how I'm rarely so polite. Also by the way: Simon is a friend of mine, so we always joke around. If I say annoying stuff when he's around, that might be the reason. I will try to restrain myself.
• Options
52.
edited June 2018

John wrote:

Puzzle. If p is prime, how many actions of the group Z/p are there on a set with n elements?

For a database with schema $$\mathbb{Z}_p$$ and maps the node to a set with n elements, the edge is mapped to either the identity or an n-permutation of order p. So to find how many actions we have, we need to count the number of different n-permutations of order p and then add 1 to such number. For this purpose, let's review some basic notions and properties of n-permutations.

• We use the notation $$(i_1,i_2, ..., i_k)$$ to denote the permutation which maps the $$i^{th}_1$$ element to the $$i^{th}_2$$ element, the $$i^{th}_2$$ element to the $$i^{th}_3$$ element, ..., the $$i^{th}_k$$ element to the $$i^{th}_1$$ element, and leave the rest of the elements fixed. Such permutations are called a k-cycle. Each k-cycle is of order k.

• Two cycles $$(i_1,i_2, ..., i_k)$$ and $$(j_1,j_2, ..., j_l)$$ are disjoint if the sets $$\lbrace i_1,i_2, ..., i_k\rbrace$$ and $$\lbrace j_1,j_2, ..., j_l\rbrace$$ are disjoint.

• Every n-permutation can be written uniquely (up to rearrangement of the cycles) as a composition of disjoint cycles.

• The order of a composition of disjoint cycles is equal to the LCM of the orders of the constituent cycles.

Now, suppose $$F$$ is a functor representing an action of the group $$\mathbb{Z}_p$$ on a set with n elements, $$e$$ is the edge in $$\mathbb{Z}_p$$, then $$F(e)$$ is either the identity or an n-permutation of order p. According to the above properties, $$F(e)$$ must be a p-cycle, a composition of 2 p-cycles, a composition of 3 p-cycles, ..., or at most a composition of $$\lfloor n/p \rfloor$$ p-cycles. Let's count the number of different permutations in each case.

• 1 p-cycle: We have n choices for the first element in the p-cycle, (n-1) choices for the second element, ..., and (n-p+1) choices for the $$p^th$$ element. However, for each such p-cycle, we overcount it by p times because the cyclic permutations of the p elements produce the same permutation. For example, $$(123)=(231)=(312)$$. Hence, there are

$$\frac{n(n-1)...(n-p+1)}{p}$$ different p-cycles.

• Composition of 2 p-cycles: Again, for the first p-cycle in the composition, we have $$\frac{n(n-1)...(n-p+1)}{p}$$ choices. For the second p-cycle, since the pool of elements to pick is down to $$(n-p)$$ elements, there are only $$\frac{(n-p)(n-p-1)...(n-2p+1)}{p}$$ choices. Finally, since disjoint p-cycles commute, scambling the order of composition produces the same permutation, we have to divide the product of the abover numbers by $$2!$$. Hence the number of different compostions of 2 p-cycles is

$$\frac{n(n-1)...(n-2p+1)}{2!p^2}.$$ ...

• Composition of $$\lfloor n/p \rfloor$$ p-cycles: By the same token, there are $$\frac{n(n-1)...(n-p+1)}{p}$$ choices for the first p-cycle, $$\frac{(n-p)(n-p-1)...(n-2p+1)}{p}$$ choices for the second p-cycle, ..., and $$\frac{(n-(\lfloor \frac{n}{p} \rfloor-1)p)(n-p-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{p}$$ choices for the last p-cycle. Moreover, there are $$\lfloor n/p \rfloor !$$ ways to scamble each composition, the number of different compostions of $$\lfloor n/p \rfloor$$ p-cycles is

$$\frac{n(n-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{\lfloor \frac{n}{p} \rfloor !p^{\lfloor \frac{n}{p} \rfloor}}.$$ So the total number of different actions of the group Z/p are there on a set with n elements is

$$1+\frac{n(n-1)...(n-p+1)}{p}+\frac{n(n-1)...(n-2p+1)}{2!p^2}+...\frac{n(n-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{\lfloor \frac{n}{p} \rfloor !p^{\lfloor \frac{n}{p} \rfloor}}.$$

Comment Source:John wrote: >Puzzle. If p is prime, how many actions of the group Z/p are there on a set with n elements? For a database with schema \$$\mathbb{Z}_p\$$ and maps the node to a set with n elements, the edge is mapped to either the identity or an n-permutation of order p. <img src="https://docs.google.com/drawings/d/e/2PACX-1vQG_2A7XFrper5y0LeefRtqql3JKUSfwFJONdk7OX_DVITAUMSgDmhisRdjUeSJa7unjcu_kemElbLJ/pub?w=728&amp;h=234"> So to find how many actions we have, we need to count the number of different n-permutations of order p and then add 1 to such number. For this purpose, let's review some basic notions and properties of n-permutations. - We use the notation \$$(i_1,i_2, ..., i_k)\$$ to denote the permutation which maps the \$$i^{th}_1\$$ element to the \$$i^{th}_2\$$ element, the \$$i^{th}_2\$$ element to the \$$i^{th}_3\$$ element, ..., the \$$i^{th}_k\$$ element to the \$$i^{th}_1\$$ element, and leave the rest of the elements fixed. Such permutations are called a k-cycle. Each k-cycle is of order k. - Two cycles \$$(i_1,i_2, ..., i_k)\$$ and \$$(j_1,j_2, ..., j_l)\$$ are disjoint if the sets \$$\lbrace i_1,i_2, ..., i_k\rbrace\$$ and \$$\lbrace j_1,j_2, ..., j_l\rbrace\$$ are disjoint. - Every n-permutation can be written uniquely (up to rearrangement of the cycles) as a composition of disjoint cycles. - The order of a composition of disjoint cycles is equal to the LCM of the orders of the constituent cycles. Now, suppose \$$F\$$ is a functor representing an action of the group \$$\mathbb{Z}_p\$$ on a set with n elements, \$$e\$$ is the edge in \$$\mathbb{Z}_p\$$, then \$$F(e)\$$ is either the identity or an n-permutation of order p. According to the above properties, \$$F(e)\$$ must be a p-cycle, a composition of 2 p-cycles, a composition of 3 p-cycles, ..., or at most a composition of \$$\lfloor n/p \rfloor\$$ p-cycles. Let's count the number of different permutations in each case. - **1 p-cycle**: We have n choices for the first element in the p-cycle, (n-1) choices for the second element, ..., and (n-p+1) choices for the \$$p^th\$$ element. However, for each such p-cycle, we overcount it by p times because the cyclic permutations of the p elements produce the same permutation. For example, \$$(123)=(231)=(312)\$$. Hence, there are $$\frac{n(n-1)...(n-p+1)}{p}$$ different p-cycles. - **Composition of 2 p-cycles**: Again, for the first p-cycle in the composition, we have \$$\frac{n(n-1)...(n-p+1)}{p}\$$ choices. For the second p-cycle, since the pool of elements to pick is down to \$$(n-p)\$$ elements, there are only \$$\frac{(n-p)(n-p-1)...(n-2p+1)}{p}\$$ choices. Finally, since disjoint p-cycles commute, scambling the order of composition produces the same permutation, we have to divide the product of the abover numbers by \$$2!\$$. Hence the number of different compostions of 2 p-cycles is $$\frac{n(n-1)...(n-2p+1)}{2!p^2}.$$ ... - **Composition of \$$\lfloor n/p \rfloor\$$ p-cycles**: By the same token, there are \$$\frac{n(n-1)...(n-p+1)}{p}\$$ choices for the first p-cycle, \$$\frac{(n-p)(n-p-1)...(n-2p+1)}{p}\$$ choices for the second p-cycle, ..., and \$$\frac{(n-(\lfloor \frac{n}{p} \rfloor-1)p)(n-p-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{p}\$$ choices for the last p-cycle. Moreover, there are \$$\lfloor n/p \rfloor !\$$ ways to scamble each composition, the number of different compostions of \$$\lfloor n/p \rfloor\$$ p-cycles is $$\frac{n(n-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{\lfloor \frac{n}{p} \rfloor !p^{\lfloor \frac{n}{p} \rfloor}}.$$ So the total number of different actions of the group Z/p are there on a set with n elements is $$1+\frac{n(n-1)...(n-p+1)}{p}+\frac{n(n-1)...(n-2p+1)}{2!p^2}+...\frac{n(n-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{\lfloor \frac{n}{p} \rfloor !p^{\lfloor \frac{n}{p} \rfloor}}.$$
• Options
53.
edited June 2018

Great, Cheuk Man Hwang! I realized after I gave that puzzle that it might be rather hard. I'll just sketch some of my own reasoning, without carrying out all the details.

As you note, the first step is to notice that to specify an action of a group on an $$n$$-element set is to break that set into disjoint sets called orbits. For the group $$\mathbb{Z}/p$$ these orbits must be of size $$1$$ or $$p$$ - this is a simplification that occurs because $$p$$ is prime.

For each orbit of size $$1$$ there's nothing more to say: the group $$\mathbb{Z}/p$$ must act trivially. For each orbit of size $$p$$ we must choose a cyclic ordering of that orbit, to say how the group acts. There are $$p!$$ orderings of a set of size $$p$$, but only $$(p-1)!$$ cyclic orderings.

So, our answer will involve 3 ideas:

1) Let $$k$$ be the number of orbits of size $$p$$. This can range from $$0$$ up to $$\lfloor n/p \rfloor$$, so our answer will start with

$$\sum_{k = 0}^{\lfloor n/p \rfloor} .$$ 2) Then we need to count the number of ways to chop our $$n$$-element set into $$k$$ subsets of size $$p$$ and $$n - k p$$ subsets of size $$1$$. The answer is the multinomial coefficient

$${n \choose p, p, \ldots, p, 1, 1, \dots , 1}$$ with $$k$$ $$p$$'s and $$n-kp$$ $$1$$'s. Remember, the multinomial coefficient is made for exactly this task:

$${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}$$ is the number of ways to chop an $$n$$-element set into disjoint parts of size $$k_1, \dots, k_m$$. In our particular example we get

$${n \choose p, p, \ldots, p, 1, 1, \dots , 1} = \frac{n!}{(p!)^k}$$ 3) Then we need to include a factor of $$(p-1)!$$ for each orbit of size $$p$$.

Putting these ideas together, we get

$$\sum_{k = 0}^{\lfloor n/p \rfloor} ((p-1)!)^k \frac{n!}{(p!)^k}$$ We can simplify this a bit and get

$$\sum_{k = 0}^{\lfloor n/p \rfloor} \frac{n!}{p^k}$$ I hope this answer agrees with yours! It would take some calculations to check this. It's also quite possible I made a mistake; I think the basic strategy is right but it's easy to make mistakes, and I haven't checked my answer.

Comment Source:Great, Cheuk Man Hwang! I realized after I gave that puzzle that it might be rather hard. I'll just sketch some of my own reasoning, without carrying out all the details. As you note, the first step is to notice that to specify an action of a group on an \$$n\$$-element set is to break that set into disjoint sets called [orbits](https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers). For the group \$$\mathbb{Z}/p\$$ these orbits must be of size \$$1\$$ or \$$p\$$ - this is a simplification that occurs because \$$p\$$ is prime. For each orbit of size \$$1\$$ there's nothing more to say: the group \$$\mathbb{Z}/p\$$ must act trivially. For each orbit of size \$$p\$$ we must choose a cyclic ordering of that orbit, to say how the group acts. There are \$$p!\$$ orderings of a set of size \$$p\$$, but only \$$(p-1)!\$$ cyclic orderings. So, our answer will involve 3 ideas: 1) Let \$$k\$$ be the number of orbits of size \$$p\$$. This can range from \$$0\$$ up to \$$\lfloor n/p \rfloor\$$, so our answer will start with $\sum_{k = 0}^{\lfloor n/p \rfloor} .$ 2) Then we need to count the number of ways to chop our \$$n\$$-element set into \$$k\$$ subsets of size \$$p\$$ and \$$n - k p \$$ subsets of size \$$1\$$. The answer is the multinomial coefficient ${n \choose p, p, \ldots, p, 1, 1, \dots , 1}$ with \$$k\$$ \$$p\$$'s and \$$n-kp\$$ \$$1\$$'s. Remember, the [multinomial coefficient](https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients) is made for exactly this task: ${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}$ is the number of ways to chop an \$$n\$$-element set into disjoint parts of size \$$k_1, \dots, k_m\$$. In our particular example we get ${n \choose p, p, \ldots, p, 1, 1, \dots , 1} = \frac{n!}{(p!)^k}$ 3) Then we need to include a factor of \$$(p-1)!\$$ for each orbit of size \$$p \$$. Putting these ideas together, we get $\sum_{k = 0}^{\lfloor n/p \rfloor} ((p-1)!)^k \frac{n!}{(p!)^k}$ We can simplify this a bit and get $\sum_{k = 0}^{\lfloor n/p \rfloor} \frac{n!}{p^k}$ I hope this answer agrees with yours! It would take some calculations to check this. It's also quite possible I made a mistake; I think the basic strategy is right but it's easy to make mistakes, and I haven't checked my answer. 
• Options
54.
edited June 2018

Dear John, you wrote

2) Then we need to count the number of ways to chop our n-element set into k subsets of size p and n−kp subsets of size 1. The answer is the multinomial coefficient (np,p,…,p,1,1,…,1) with k p's and n−kp 1's.

Since the arrangement of the orbits of size 1 does not matter, I would suggest that we should count the number of ways to chop our n-element set into k subsets of size p and 1 subset of size n-kp instead. For example, consider the $$\mathbb{Z}_2$$-action of a set of $$n=4$$ elements. The number of different ways to chop the set into $$k=1$$ subset of size $$p=2$$ and $$(n-k)=2$$ subsets of size 1 is $${4 \choose 2, 1, 1}=\frac{4!}{2!}=12$$

$$\begin{array}{cc} (12)(3)(4)&(12)(4)(3)\\ (13)(2)(4)&(13)(4)(2)\\ (14)(2)(3)&(14)(3)(2)\\ (23)(1)(4)&(23)(4)(1)\\ (24)(1)(3)&(24)(3)(1)\\ (34)(1)(2)&(34)(2)(1)\\ \end{array}$$ However, the 12 different partitions above only produce 6 different permutations, which is the same as $${4 \choose 2, 2}=\frac{4!}{2!2!}$$, the number of ways to chop the 4-element set into a subset of size 2 (the 2 elements that we swap) and another subset of size 2 (the other 2 elements that stay fixed). So in general, I believe the number of ways in step 2 of your comment should be $${n \choose p, ..., p, (n-kp)}=\frac{n!}{(p!)^k (n-kp)!}$$.

Finally, in step 3 of your comment, I think not only we should include a factor of $$(p-1)!$$ for each orbit of size $$p$$ but also we should divide it by $$k!$$ for the fact that the arrangement of the $$k$$ orbits of size $$p$$ does not matter. For example, consider chopping the $$n=4$$-element into $$k=2$$ subsets of size $$p=2$$, we have

$$\begin{array}{c} (12)(34)\\ (13)(24)\\ (14)(23)\\ (23)(14)\\ (24)(13)\\ (34)(12)\\ \end{array}$$ However, the pairs $$\left\lbrace(12)(34) \text{ and } (34)(12)\right\rbrace$$, $$\left\lbrace(13)(24) \text{ and } (24)(13)\right\rbrace$$, and $$\left\lbrace(14)(23) \text{ and } (23)(14)\right\rbrace$$ each produce the same permutation, so the actual number of different permutations is $$3=(2-1)!\frac{1}{2!}{4 \choose 2,2}$$. Therefore, in general, I believe that each summand in the final formula should be

$$(p-1)!\frac{1}{k!}{n \choose p, ..., p,(n-kp)}=\frac{n!}{k!p^k(n-kp)!}.$$ Taking these into consideration, your answer and my answer will match.

Comment Source:Dear John, you wrote > 2) Then we need to count the number of ways to chop our n-element set into k subsets of size p and n−kp subsets of size 1. The answer is the multinomial coefficient (np,p,…,p,1,1,…,1) with k p's and n−kp 1's. Since the arrangement of the orbits of size 1 does not matter, I would suggest that we should count the number of ways to chop our n-element set into k subsets of size p and 1 subset of size n-kp instead. For example, consider the \$$\mathbb{Z}_2\$$-action of a set of \$$n=4\$$ elements. The number of different ways to chop the set into \$$k=1\$$ subset of size \$$p=2\$$ and \$$(n-k)=2\$$ subsets of size 1 is \$${4 \choose 2, 1, 1}=\frac{4!}{2!}=12 \$$ $$\begin{array}{cc} (12)(3)(4)&(12)(4)(3)\\\\ (13)(2)(4)&(13)(4)(2)\\\\ (14)(2)(3)&(14)(3)(2)\\\\ (23)(1)(4)&(23)(4)(1)\\\\ (24)(1)(3)&(24)(3)(1)\\\\ (34)(1)(2)&(34)(2)(1)\\\\ \end{array}$$ However, the 12 different partitions above only produce 6 different permutations, which is the same as \$${4 \choose 2, 2}=\frac{4!}{2!2!}\$$, the number of ways to chop the 4-element set into a subset of size 2 (the 2 elements that we swap) and another subset of size 2 (the other 2 elements that stay fixed). So in general, I believe the number of ways in step 2 of [your comment](https://forum.azimuthproject.org/discussion/comment/19309/#Comment_19309) should be \$${n \choose p, ..., p, (n-kp)}=\frac{n!}{(p!)^k (n-kp)!} \$$. Finally, in step 3 of [your comment](https://forum.azimuthproject.org/discussion/comment/19309/#Comment_19309), I think not only we should include a factor of \$$(p-1)!\$$ for each orbit of size \$$p\$$ but also we should divide it by \$$k!\$$ for the fact that the arrangement of the \$$k\$$ orbits of size \$$p\$$ does not matter. For example, consider chopping the \$$n=4\$$-element into \$$k=2\$$ subsets of size \$$p=2\$$, we have $$\begin{array}{c} (12)(34)\\\\ (13)(24)\\\\ (14)(23)\\\\ (23)(14)\\\\ (24)(13)\\\\ (34)(12)\\\\ \end{array}$$ However, the pairs \$$\left\lbrace(12)(34) \text{ and } (34)(12)\right\rbrace\$$, \$$\left\lbrace(13)(24) \text{ and } (24)(13)\right\rbrace\$$, and \$$\left\lbrace(14)(23) \text{ and } (23)(14)\right\rbrace\$$ each produce the same permutation, so the actual number of different permutations is \$$3=(2-1)!\frac{1}{2!}{4 \choose 2,2}\$$. Therefore, in general, I believe that each summand in the final formula should be $$(p-1)!\frac{1}{k!}{n \choose p, ..., p,(n-kp)}=\frac{n!}{k!p^k(n-kp)!}.$$ Taking these into consideration, your answer and my answer will match.
• Options
55.
edited June 2018

Okay, I get it. The multinomial coefficient

$${n \choose p, p, \ldots, p, 1, 1, \dots , 1} = \frac{n!}{(p!)^k (1!)^{n-kp}} = \frac{n!}{(p!)^k}$$ counts the number of ways to take an $$n$$-element set and partition it into labeled parts, $$k$$ of size $$p$$ and $$n-kp$$ of size $$1$$. But we don't want labeled parts. We need to ignore the labelings. So we need to divide by $$k!$$ and $$(n-kp)!$$, to account for permutations of labelings.

$$\sum_{k = 0}^{\lfloor n/p \rfloor} \frac{n!}{p^k}$$ should be corrected to
$$\sum_{k = 0}^{\lfloor n/p \rfloor} \frac{n!}{p^k k! (n-kp)!}$$ Okay, that matches what you said.
Comment Source:Okay, I get it. The multinomial coefficient ${n \choose p, p, \ldots, p, 1, 1, \dots , 1} = \frac{n!}{(p!)^k (1!)^{n-kp}} = \frac{n!}{(p!)^k}$ counts the number of ways to take an \$$n\$$-element set and partition it into _labeled_ parts, \$$k\$$ of size \$$p\$$ and \$$n-kp\$$ of size \$$1\$$. But we don't want _labeled_ parts. We need to ignore the labelings. So we need to divide by \$$k!\$$ and \$$(n-kp)!\$$, to account for permutations of labelings. So, my incorrect answer $\sum_{k = 0}^{\lfloor n/p \rfloor} \frac{n!}{p^k}$ should be corrected to $\sum_{k = 0}^{\lfloor n/p \rfloor} \frac{n!}{p^k k! (n-kp)!}$ Okay, that matches what you said.