3
$\begingroup$

I have just learned that the formula is right, but the definition of $c_n^{(r)}$ was wrong. The correct problem is: Prove $$c_{n+1}^{(r)} = \sum_{k=n-r+1}^n n^{\underline{n-k}} c_k^{(r)}$$ where $c_n^{(r)} = |\left\{\sigma \in S_n:\ \text{the length of each cycle of $\sigma$ is at most $r$} \right\}|.$

I will try to prove this with the same approach: classifying by the length of the cycle containing $n+1$.

[edit] I've just tried this and one details still puzzles me: I assume the cycle that containing $n+1$ to have length $n+1-k$ which leaves $k$ elements for the other cycles. There are $c_k^{(r)}$ ways to make them admissible and I want to accumulate all the cases for $n+1-k$ from 1 to $n$, thus $k$ from $n+1-r$ to $n$. So far, so good. Now we need to consider all possible permutations of the cycle containing $n+1$. But here's my problem: Those should be $(n+1)^{\underline{(n+1)-k}}$ because I have different possibilities for the position of $n+1$ itself. But the formula doesn't seem to account for that.

I have thought about this for quite some time now, but I'm still confused. Can anyone help me answering this?

I also considered $n^{\underline{n-k}}=(n-k)! \binom{n}{n-k}$ which basically gives the same meaning: We choose $n-k$ elements for the cycle containing $n+1$ and consider all possible permutations for them. Clearly, I don't have to choose $n+1$ in the first place, but why is $n+1$ not included in those permutations?

[Old question before correction:]

I want to prove this formula: $$c_{n+1}^{(r)} = \sum_{k=n-r+1}^n n^{\underline{n-k}} c_k^{(r)}$$ where $c_n^{(r)} = |\left\{\sigma \in S_n:\ \sigma^r = id \right\}|$ and I will write $C_n^{(r)} = \left\{\sigma \in S_n:\ \sigma^r = id \right\}$ for the respective set. $n^{\underline{n-k}} = n(n-1)...(n-k+1)$ are the falling factorials and $[n]=\left\{1,...n\right\}.$

I tried simple non-trivial examples and looked at the cycle representation. For $\sigma \in C_n^{(r)}$ the length of every cycle of $\sigma$ has to divide $r$ (of course that condition is not sufficient). But I don't see how that helps so far.

Right now, I'm trying to give some meaning to the right hand side of the recurrence formula and so far I came up with this: Consider the cycle representation of $\sigma \in C_{n+1}^{(r)}$. I can designate the cycle that contains $n+1$. It's length is between $1$ and $r$. Since we have $c_k^{(r)}$ on the right hand side, I want to be left with $k$ elements of $[n+1]$ for the remaining cycles, so the length of the cycle that contains $n+1$ should be $n+1-k$. This also makes sense because it means $1 \leq n+1-k \leq r$ and hence $n+1-r \leq k \leq n$. That's why the indices go from $n+1-r$ to $n$. Now, for $k=n+1-r,...,n$, $c_k^{(r)}$ should be the number of ways to arrange the remaining $k$ elements of $[n+1]$ (those that don't belong to the cycle with $n+1$) into cycles such that $\sigma^r=id$ is possible (necessary condition).

However, at this point I'm stuck because I don't see how the falling factorials fit in, and I don't see how it gives a sufficient condition for $\sigma^r=id$.

$\endgroup$
  • $\begingroup$ I edited again because I have a little problem solving the actual question. Hopefully, someone can help me out with that... $\endgroup$ – Amarus May 9 '14 at 1:27
1
$\begingroup$

I am not sure about your recurrence, but here is another one that can be derived.

We are working with the labelled species $$\mathfrak{P}\left(\sum_{d|r} \mathfrak{C}_d(\mathcal{Z})\right).$$ This yields the generating function $$G(z) = \exp\left(\sum_{d|r} \frac{z^d}{d}\right).$$ Therefore $$C_{n+1}^{(r)} = (n+1)! [z^{n+1}] \exp\left(\sum_{d|r} \frac{z^d}{d}\right).$$ Differentiate to obtain $$C_{n+1}^{(r)} = n! [z^n] \exp\left(\sum_{d|r} \frac{z^d}{d}\right) \sum_{d|r} z^{d-1}.$$

What we have here is the convolution of two generating functions. The first of $C_n^{(r)}$ and the second of $(d-1)!$. Therefore $$C_{n+1}^{(r)} = \sum_{d|r} {n\choose d-1} (d-1)! \times(n-d+1)! [z^{n-d+1}] \exp\left(\sum_{d|r} \frac{z^d}{d}\right).$$ This finally yields $$C_{n+1}^{(r)} = \sum_{d|r} {n\choose d-1} (d-1)! C_{n-d+1}^{(r)} = \sum_{d|r} \frac{n!}{(n-d+1)!} C_{n-d+1}^{(r)}.$$ Using the notation by Capelli and Toscano as documented at Wikipedia this becomes $$C_{n+1}^{(r)} = \sum_{d|r} n^{\underline{d}} C_{n-d+1}^{(r)}.$$ This formula is in fact quite trivial. Simply do the enumeration by classifying according to the cycle that $n+1$ is on.

Addendum.

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Addendum Sat Oct 10 CEST 2015. The recurrence above can just as easily be done without the convolution. We have $$n! [z^n] \exp\left(\sum_{d|r} \frac{z^d}{d}\right) \sum_{d|r} z^{d-1} = n! \sum_{d|r} [z^{n-d+1}] G(z) = n! \sum_{d|r} \frac{C_{n-d+1}^{(r)}}{(n-d+1)!}$$ and may continue as before.

Here the sum is understood to range over those $d$ where $n-(d-1)\ge 0$ as in the following Maple program:

C := proc(n, r)
local m, s, d;
option remember;
    if n = 0 then return 1 end if;
    m := n - 1;
    s := 0;
    for d in numtheory:-divisors(r) do
        if d - 1 <= m then s := s + C(m - d + 1, r)/(m - d + 1)! end if
    end do;
    m!*s
end proc
$\endgroup$
  • $\begingroup$ "This formula is in fact quite trivial. Simply do the enumeration by classifying according to the cycle that n+1 is on." I was going to give an answer giving the combinatorial proof of this, and indeed it is not too hard to find such a proof. However I couldn't obtain the OPs formula. I don't know how many people here know what a "labeled species" is, however. Could you explain a little? On the other hand, I suppose anyone that has read a little about generating functions knows about convolution, so it seems to addendum is unnecessary! $\endgroup$ – Pedro Tamaroff May 8 '14 at 0:43
  • $\begingroup$ This enumeration is in fact what I tried to do, isn't it? I couldn't get a result either, that's I was asking for help. @Marko: We didn't treat generating functions (or labelled species) so far, so I have great difficulty following your explanation above, but I will definitely look at it again as soon as I'm more familiar with the topic. $\endgroup$ – Amarus May 8 '14 at 0:45
  • $\begingroup$ I hope you'll let me keep the addendum this time, I usually include it when I do convolutions so the reader sees it right on the page without having to consult another resource, but I promise I will use it sparingly in the future. As for the formula in the OP I doubt it works since he says that the length of the cycle that $n+1$ is on is between $1$ and $r$, which is definitely not true. The only admissible cycles are the ones whose length $d$ divides $r$ and that should be fairly clear I think. $\endgroup$ – Marko Riedel May 8 '14 at 0:52
  • $\begingroup$ @Amarus This Wikipedia entry presents the method of analytical combinatorics and species theory, its history, contributors and additional relevant material. $\endgroup$ – Marko Riedel May 8 '14 at 1:12
  • 2
    $\begingroup$ Thanks for keeping the text of the old question. That way my effort was not entirely in vain. The generating function for the modified question is $$\exp\left(\sum_{k=1}^r \frac{z^k}{k}\right).$$ $\endgroup$ – Marko Riedel May 8 '14 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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