Elegia's blog

By Elegia, history, 4 years ago, In English

We will get the bivariate generating function $$$\widehat F(z, t) = \sum_{n\ge 1}\sum_{k=1}^n A_{n,k}\frac{z^nt^k}{n!}$$$, where $$$A_{n,k}$$$ is the sum of occurrences of $$$k$$$ in all good sequence of length $$$n$$$. Consider the inclusion-exclution principle. For all contribution with $$$\max k = m$$$, we have

$$$ \sum_{j=1}^m \sum_{S \subseteq \{1, 2, \cdots m-1\}} (-1)^{|S|} Q(S, z, t, j) $$$

This means that for all $$$i \in S$$$, we force all recurrences of $$$i$$$ are before $$$i + 1$$$, and the occurrences of $$$j$$$ are counted.

After some tough calculation, we will found out that this equates to $$$\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}$$$. Here are the details:

Details

Now our goal is to calculate

$$$ [z^n]\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})} $$$

We consider $$$\left([z^n]\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}\right) + 1 = (1-t)[z^n] \frac 1{(1-z)(1-t\mathrm e^{z(1-t)})}$$$, which looks simpler. We let $$$z = \frac u{1-t}$$$, then

$$$ [z^n]\frac 1{(1-z)(1-t\mathrm e^{z(1-t)})} = (1-t)^n[u^n] \frac1{(1-\frac u{1-t})(1-t\mathrm{e}^u)} $$$

Hence we have

$$$ \begin{aligned} (1-t)[z^n] \frac 1{(1-z)(1-t\mathrm e^{z(1-t)})} &= [u^n]\frac{(1-t)^{n+2}}{(1-\frac{t}{1-u})(1-t\mathrm e^u)(1-u)}\\&= (1-t)^{n+2} [u^n] \left(\frac{-\mathrm e^u}{\left(\mathrm e^u u-\mathrm e^u+1\right) \left(1-t \mathrm e^u\right)}+\frac{\frac{1}{1-u}}{\left(\mathrm e^u u-\mathrm e^u+1\right) (1-\frac{t}{1-u})}\right)\end{aligned} $$$

Noticed that $$$[u^m]\mathrm{e}^{ku} = \frac{k^m}{m!}$$$, this could be calculated straightly through multipoint evaluation with time complexity of $$$\Theta(n\log^2 n)$$$. And $$$[u^m] \frac1{(1-u)^k} = \binom{n+k-1}{n} = \frac{(n+k-1)!}{n!(k-1)!}$$$ so this part could be calculated through a convolution. It will pass if your implementation doesn't have a big constant.

It could also be improved to $$$\Theta(n\log n)$$$ through the Lagrange Inversion formula similar to the original solution, I leave this as an exercise.

UPD1: simplified some deduction.

  • Vote: I like it
  • +172
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by Elegia (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Is it competitive coding ?

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

After seeing this blog, I went your profile to make sure my guess that you are Chinese!

»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

UPD1: simplified some deduction.

Thanks!

»
4 years ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

How do you calculate the last part with multipoint evaluation? Elegia

Also, the "tough calculation" part is actually similar to the formula for Eulerian polynomials:

$$$F(x,t) = \displaystyle\sum_{d \ge 0}A_{d}(x)\frac{t^{d}}{d!} = \frac{1-x}{1 - xe^{(1-x)t}},$$$

where $$$A_{d}(x) = \displaystyle\sum_{k=1}^{d}A(d,k)x^{k}$$$ is an Eulerian polynomial. Here, $$$A(d,k)$$$ is the number of permutations of length $$$d$$$ with $$$k-1$$$ descents. We can derive a bijection showing that the answer for $$$k$$$ is $$$n! \cdot \sum_{i=1}^{n}\frac{E(i,k)}{i!}$$$, which is basically the prefix sum of coefficients of $$$F(x,t)$$$, and thus we can simplify "prefix sum" to "coefficient of single term" by multiplying $$$F(x,t)$$$ with $$$\frac{1}{1-t}$$$, which gives the function described in the blog.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    For the $$$[u^m] f(u)/(1-t\mathrm{e}^u)$$$ part:

    $$$ \begin{aligned} [u^n] \frac{f(u)}{1-t \mathrm{e}^u} & = \sum_k [u^n] t^k f(u)\mathrm{e}^{ku} \\ &= \sum_k t^k \sum_{0\le j} \frac{k^j}{j!} [u^{n-j}] f(u)\\ &= \sum_k t^k \sum_{0\le j} k^j \frac{f_{n-j}}{j!}\\ &= \sum_k t^k P(k) \end{aligned} $$$

    For the $$$[u^m] g(u)/(1-\frac t{1-u})$$$ part, it might cost $$$\Theta(n\log^2 n)$$$ to calculate the coefficient straightly bacause you need to expand the polynomial expressed by the linear combination of $$$\binom{n+x-1}{n}$$$ through divide and conquer.

    Speaking of Eulerian Polynomial: Yes, it's surely Eulerian Polynomial. But what I'm going to show is that there is a way to get the GF with no knowledge of Eulerian Polynomial nor bijection to the permutation. It will be updated a few times later. >_<

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you help me to prove this bijection, please.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I have done it in my tutorial on Generating Functions here.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

My implementation: 80415302

In your last expression, $$$(1-t)^{n+2}$$$ should be $$$(1-t)^{n+1}$$$. Or replace the terms after $$$[u^n]$$$ with the following:

$$$\frac{-e^u}{(e^uu-e^u+1)(1-te^u)}+\frac{1/(1-u)}{(e^uu-e^u+1)(1-t/(1-u))}$$$
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

stO Elegia! I found that u've been keen on generating function these days XD.

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it