Escrito por Fábio Medeiros
1 Introdução
O método do Snake Oil permite o cálculo de somatórios que, à primeira vista, parecem desafiadores! Desse modo, originou-se o nome: óleo de cobra, como uma cura milagrosa a contas doentias…
Ele pode ser aplicado tanto em problemas de bijeção quanto em contagens, sendo uma técnica necessária para atacar muitos problemas da Combinatória Moderna.
Obs: esse material tem como pré-requisito noções em funções geratrizes. Você pode aprender ou revisar esse tema no Curso Noic clicando aqui<\a>!
A ideia por trás dessa técnica é bem simples, mas antes vamos relembrar algumas identidades que serão úteis na resolução de problemas!
1.1 Identidades
Lembre-se que sempre trabalhamos com séries formais. Assim, caso um somatório esteja sem indíces, adote como \(\sum_{n=0}^{\infty}\).
| 1. \((1+x)^n=\sum \binom{n}{k}x^k\) | 5. \(\frac{x^m}{2}\left(\frac{1}{(1-x)^{m+1}}+\frac{(-1)^m}{(1+x)^{m+1}}\right)=\sum \binom{2n}{m}x^{2n+1}\) |
| 2. \(\frac{x^k}{(1-x)^{k+1}}=\sum \binom{n}{k}x^n;\ k=0:\frac{1}{1-x}=\sum x^n\) | 6. \(\frac{x^m}{2}\left(\frac{1}{(1-x)^{m+1}}-\frac{(-1)^m}{(1+x)^{m+1}}\right)=\sum \binom{2n+1}{m}x^{2n}\) |
| 3. \(\sum \binom{m}{2n}x^{2n}=\frac{(1+x)^m+(1-x)^m}{2}\) | 7. \(\frac{1-\sqrt{1-4x}}{2x}=\sum \frac{1}{n+1}\binom{2n}{n}x^n\) |
| 4. \(\sum \binom{m}{2n+1}x^{2n+1}=\frac{(1+x)^m-(1-x)^m}{2}\) | 8. \(\text{(Fibonacci) }\frac{x}{1-x-x^2}=\sum F_nx^n\) |
Ao longo dos problemas, sempre que usarmos alguma das identidades acima (por exemplo a \(I_1\)), indicaremos acima da igualdade \(\left(\overset{I_1}{=}\right)\).
1.2 Demonstrações
Passaremos rapidamente por elas, já que não são o foco do material.
- Teorema do Binômio com \(y=1\): \((x+y)^r=\sum \binom{r}{k}x^ky^{r-k}\).
- Temos \(\frac{1}{(1-x)^{k+1}}=(1-x)^{-(k+1)}=\sum \binom{-(k+1)}{n}(-x)^n\stackrel{\star}{=}\sum \binom{n+k}{k}(-1)^n(-x)^n=\sum \binom{n+k}{k}x^n\Rightarrow \frac{x^k}{(1-x)^{k+1}}=\sum \binom{n+k}{k}x^{n+k}=\sum \binom{n}{k}x^n\) onde usamos o Lema da Negação Superior em \(\star\) (visto no material de Funções Geratrizes).
- Basta notar que ao expandir os binomias de \((1+x)^m+(1-x)^m\), os termos de coeficiente ímpar cortam e os pares ficam dobrados.
- Basta notar que ao expandir os binomias de \((1+x)^m-(1-x)^m\), os termos de coeficiente par cortam e os ímpares ficam dobrados.
- A mesma ideia do item 3, mas agora usando a identidade 2.
- A mesma ideia do item 4, mas agora usando a identidade 2.
- É a geratriz da sequência de Catalan apresentada no material de Funções Geratrizes.
- É a geratriz da sequência de Fibonacci apresentada no material de Funções Geratrizes.
2 Ideia e Exemplos
Suponha que queremos calcular uma soma \(S\). Primeiro identificamos a variável livre de qual \(S\) depende. Seja \(n\) tal variável e defina \(S=f(n)\). Assim, buscamos uma fórmula explícita para \(S\) em função de \(n\) (o que muitos problemas nos pedem, certo?).
O método do Snake Oil consiste em encontrar a função geratriz \(F(x)\) para a sequência \((f(n))_{n=0}^{\infty}\).
F(x)=\sum_{n=0}^{\infty} f(n)x^n
\]
Se conseguirmos escrever \(F(x)\) de outro jeito mais simples \(F(x)=\sum g(n)x^n\) com \(g(n)\) uma função que conhecemos, então podemos comparar os coeficientes desses polinômios e deduzir que \(f(n)=g(n)\).
Para isso, realizamos um truque de contagem dupla: quando escrevemos
F(x)=\sum_n f(n)x^n
\]
temos (pelo menos) uma soma dupla: externa em \(n\) e interna que envolve a definição de \(S=f(n)\). Em seguida, trocamos a ordem da soma (\(S\) passa para a soma externa enquanto \(n\) para a interna). Obtendo o valor da soma interna em termos de \(n\), reescrevemos \(F(x)\) de um jeito mais simples e concluímos.
Vamos mostrar esse passo a passo com um exemplo!
Exercício 1. Calcule
\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}
\]
Solução. Seguindo o processo descrito acima, primeiro identificamos uma variável livre. Mas o que é uma variável livre? É aquela que não varia ao longo do somatório.
Nesse caso, apenas \(k\) varia dentro do somatório. Assim, podemos escolher \(n\) ou \(m\) para ser nossa variável livre. Vamos com \(m\): queremos calcular
f(m)=\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}
\]
O segundo passo é considerar a geratriz:
\begin{aligned}
F(x)&=\sum_m f(m)x^m
=\sum_m\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}x^m\\
&=\sum_m\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{k}{m}x^m
\end{aligned}
\]
já que \(\binom{k}{m}=0\) para \(k \lt m\). Como \(\sum_a\sum_b h(a,b)=\sum_b\sum_a h(a,b)\), podemos inverter o somatório:
F(x)=\sum_m\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{k}{m}x^m
=\sum_{k=0}^{n}\sum_m(-1)^k\binom{n}{k}\binom{k}{m}x^m
\]
Perceba que podemos puxar para fora tudo que está no somatório interno \(\left(\sum_m\right)\) e que não depende de \(m\):
\begin{aligned}
F(x)&=\sum_{k=0}^{n}\sum_m(-1)^k\binom{n}{k}\binom{k}{m}x^m\\
&=\sum_{k=0}^{n}(-1)^k\binom{n}{k}\sum_m\binom{k}{m}x^m
\overset{I1}{=}\sum_{k=0}^{n}(-1)^k\binom{n}{k}(1+x)^k\\
&=(-1)^n\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}(1+x)^k
\overset{I1}{=}(-1)^n(-1+(1+x))^n=(-x)^n
\end{aligned}
\]
Assim, calculamos \(F(x)\) de outro jeito:
F(x)=\sum_n g(m)x^m
\]
onde \(g(m)=0\) se \(m\neq n\) e \(g(m)=(-1)^n\) se \(n=m\). Como estamos trabalhando com séries formais, a igualdade implica igualdade coeficiente a coeficiente:
\sum_m f(m)x^m=F(x)=\sum_m g(m)x^m\Rightarrow
f(m)=
\begin{cases}
(-1)^n, & n=m\\
0, & n\neq m
\end{cases}
\]
Exercício 2. Calcule
\sum_k\binom{k}{n-k}
\]
Solução. A variável livre aqui é \(n\) e queremos achar a soma \(f(n)=\sum_k\binom{k}{n-k}\). Portanto, consideramos
F(x)=\sum_n f(n)x^n=\sum_n\sum_k\binom{k}{n-k}x^n=\sum_k\sum_n\binom{k}{n-k}x^n
\]
O próximo passo é puxar para fora do segundo somatório o que não depende de \(n\). Contudo, \(\binom{k}{n-k}\) e \(x^n\) parecem depender de \(n\), certo?
Entretanto, podemos puxar um \(x^k\) de \(x^n\):
\sum_k\sum_n\binom{k}{n-k}x^n
=\sum_k x^k\sum_n\binom{k}{n-k}x^{n-k}
\stackrel{\star}{=}\sum_k x^k\sum_n\binom{k}{n}x^n
\]
\(\star\): já que para \(n\lt k\) temos \(\binom{k}{n-k}=0\), então podemos transladar o índice. Logo,
F(x)=\sum_k x^k\sum_n\binom{k}{n}x^n
\overset{I1}{=}\sum_k x^k(1+x)^k
=\sum_k(x+x^2)^k
\overset{I2}{=}\frac{1}{1-(x+x^2)}=\frac{1}{1-x-x^2}
\]
Lembrando que a geratriz dos Fibonaccis é \(\sum F_nx^n=G(x)=\frac{x}{1-x-x^2}\Rightarrow xF(x)=G(x)\Rightarrow\)
\sum f(n)x^{n+1}=xF(x)=G(x)=\sum F_nx^n\Rightarrow f(n)=F_{n+1}
\]
Perceba que ao fazermos a inversão dos somatórios, tivemos que ser criativos para puxar um \(x^k\) e deixar \(x^{n-k}\). Pode parecer artificial, mas o objetivo é que você treine com os problemas propostos a seguir para que essas ideias se tornem naturais. Uma dica é sempre tentar fazer surgir as identidades que são conhecidas (as quais relembramos no início do material).
Dicas e soluções dos problemas a seguir estão no fim do material!
3 Problemas Propostos
Problema 1. Calcule
\sum_{k=m}^{n}\binom{n}{k}\binom{k}{m}
\]
Problema 2. Calcule
\sum_k\binom{n+k}{2k}2^{n-k}
\]
Problema 3. Calcule
\sum_k\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}
\]
Problema 4. Fatore em irredutíveis o seguinte polinômio (assim, você poderia calcular o somatório para qualquer \(x\)):
\sum_k\binom{n}{\left\lfloor \frac{k}{2}\right\rfloor}x^k
\]
Problema 5. Dado \(n\), encontre o valor de
\sum_{m>0}\sum_{\substack{k_1+k_2+\cdots+k_m=n\\ k_1,k_2,\ldots,k_n>0}}F_{k_1}F_{k_2}\cdots F_{k_m}
\]
sendo \(F_i\) o \(i\)-ésimo Fibonacci.
Problema 6. (ELMO SL 2025) Sejam \(n\) e \(k\) inteiros positivos fixos. Seja \(T\) o conjunto de todas as tuplas infinitas \(A=(a_0,a_1,\ldots)\) de inteiros tais que \(0\le a_i\le k\) para todo \(i\) e
\sum_{i=0}^{\infty}2^ia_i=n.
\]
Calcule
\sum_{A\in T}\prod_{i=0}^{\infty}\binom{k}{a_i}.
\]
Problema 7. (Vingança Olímpica 2017) Seja \(n\) um inteiro positivo. Um par \((\pi,C)\) composto por uma permutação \(\pi:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}\) e uma função binária \(C:\{1,2,\ldots,n\}\to\{0,1\}\) é chamado de vingativo se satisfaz as duas condições a seguir:
- Para todo \(i\in\{1,2,\ldots,n\}\), existe \(j\in S_i=\{i,\pi(i),\pi(\pi(i)),\ldots\}\) tal que \(C(j)=1\).
- Se \(C(k)=1\), então \(k\) é um dos \(v_2(|S_k|)+1\) maiores elementos de \(S_k\), onde \(v_2(t)\) é o maior inteiro não negativo tal que \(2^{v_2(t)}\mid t\) para todo inteiro positivo \(t\).
Seja \(V\) o número de pares vingativos e \(P\) o número de partições de \(n\) cujas partes são todas potências de \(2\). Determine \(\frac{V}{P}\).
4 Dicas:
Problema 1. Repita o que fizemos no exercício 1.
Problema 2.
\sum_n\binom{n+k}{2k}(2x)^{n-k}
=\sum_n\binom{(n-k)+2k}{n-k}(2x)^{n-k}
=\sum_n\binom{n+2k}{n}(2x)^n
\]
Use a identidade 2 deslocada (a que usamos em sua demonstração)!
Problema 3. Considere \(n\) como a variável livre. Use a Identidade 2 e a Identidade 7 (Catalan).
Problema 4. Separe o somatório em \(k\) par e \(k\) ímpar.
Problema 5. Perceba que \(x^nF_{k_1}F_{k_2}\cdots F_{k_m}=F_{k_1}x^{k_1}\cdot F_{k_2}x^{k_2}\cdots F_{k_m}x^{k_m}\).
Problema 6. Seja \(f(n)\) a expressão que queremos calcular e \(F(x)\) sua geratriz. Use que \(x^n=x^{2^0a_0+2^1a_1+\cdots}\).
Problema 7. Escreva a função geratriz \(P\) das partições de \(n\). Agora, ache uma recursão para \(V=v(n)\) considerando o ciclo da permutação em que \(1\) está. Você quer provar que \(\frac{V}{P}=n!\).
5 Soluções:
Problema 1. Sejam
f(m)=\sum_{k=m}^{n}\binom{n}{k}\binom{k}{m}\quad\text{e}\quad F(x)=\sum x^mf(m)
\]
Então temos:
\begin{aligned}
F(x)&=\sum_m x^mf(m)=\sum_m x^m\sum_{k=m}^{n}\binom{n}{k}\binom{k}{m}\\
&=\sum_m x^m\sum_{k=0}^{n}\binom{n}{k}\binom{k}{m}
=\sum_k\binom{n}{k}\sum_m\binom{k}{m}x^m\\
&\overset{I1}{=}\sum_k\binom{n}{k}(1+x)^k
=\sum_k\binom{n}{k}(1+x)^k\cdot 1^{n-k}
\overset{I1}{=}(1+(1+x))^n
\end{aligned}
\]
Logo, chegamos a
F(x)=(2+x)^n\Rightarrow (2+x)^n=\sum_m\binom{n}{m}2^{n-m}x^m
\]
Portanto, o valor da soma pedida é \(f(m)=\binom{n}{m}2^{n-m}\).
Problema 2. Sejam
f(n)=\sum_k\binom{n+k}{2k}2^{n-k}\quad\text{e}\quad F(x)=\sum f(n)x^n,
\]
\begin{aligned}
F(x)&=\sum_n\sum_k\binom{n+k}{2k}2^{n-k}x^n
=\sum_k\sum_n\binom{n+k}{2k}2^{n-k}x^n\\
&=\sum_k\sum_n\binom{(n-k)+2k}{n-k}2^{n-k}x^n
=\sum_k x^k\sum_n\binom{(n-k)+2k}{n-k}(2x)^{n-k}\\
&=\sum_k x^k\sum_n\binom{n+2k}{n}(2x)^n\\
&\overset{I2/x^k}{=}\sum_k x^k\cdot\frac{1}{(1-2x)^{2k+1}}
=\frac{1}{1-2x}\sum_k\left(\frac{x}{(1-2x)^2}\right)^k\\
&\overset{I2;\ k=0}{=}\frac{1}{1-2x}\cdot\frac{1}{1-\frac{x}{(1-2x)^2}}
=\frac{1-2x}{(1-2x)^2-x}\\
&=\frac{1-2x}{1-5x+4x^2}
=\frac{1-2x}{(1-4x)(1-x)}
=\frac{1}{3}\frac{1}{1-x}+\frac{2}{3}\frac{1}{1-4x}\\
&=\sum_{n\ge0}\left(\frac{1}{3}+\frac{2}{3}4^n\right)x^n.
\end{aligned}
\]
Portanto, ao igualar os coeficientes de \(x^n\), obtemos
\sum_{k\ge0}\binom{n+k}{2k}2^{n-k}=\frac{1}{3}+\frac{2}{3}4^n.
\]
Problema 3. Sejam
f(n)=\sum_k\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}\quad\text{e}\quad F(x)=\sum_n f(n)x^n\Rightarrow
\]
\begin{aligned}
F(x)&=\sum_n x^n\sum_k\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}\\
&=\sum_k\sum_n x^n\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}\\
&=\sum_k\binom{2k}{k}\frac{(-1)^kx^{-k}}{k+1}\sum_n\binom{n+k}{m+2k}x^{n+k}\\
&\overset{I2}{=}\sum_k\binom{2k}{k}\frac{(-1)^kx^{-k}}{k+1}\cdot\frac{x^{m+2k}}{(1-x)^{m+2k+1}}\\
&=\frac{x^m}{(1-x)^{m+1}}\sum_k\frac{1}{k+1}\binom{2k}{k}\left(\frac{-x}{(1-x)^2}\right)^k\\
&\overset{I7}{=}\frac{x^m}{(1-x)^{m+1}}\cdot\frac{1-\sqrt{1-4\left(\frac{-x}{(1-x)^2}\right)}}{2\frac{-x}{(1-x)^2}}\\
&=\frac{-x^{m-1}}{2(1-x)^{m-1}}\left(1-\sqrt{\frac{(1+x)^2}{(1-x)^2}}\right)\\
&=\frac{-x^{m-1}}{2(1-x)^{m-1}}\cdot\frac{-2x}{(1-x)}
=\frac{x^m}{(1-x)^m}\\
&\overset{I2}{=}x\sum_n\binom{n}{m-1}x^n
=\sum_n\binom{n-1}{m-1}x^n
\Rightarrow f(n)=\binom{n-1}{m-1}
\end{aligned}
\]
Problema 4. Seja
F(x)=\sum_k\binom{n}{\left\lfloor \frac{k}{2}\right\rfloor}x^k
\]
Podemos dividir nossa geratriz em duas somas:
\begin{aligned}
F(x)&=\sum_k\binom{n}{\left\lfloor k/2\right\rfloor}x^k
=\sum_{k=2k_1}\binom{n}{\left\lfloor \frac{2k_1}{2}\right\rfloor}x^{2k_1}
+\sum_{k=2k_2+1}\binom{n}{\left\lfloor \frac{2k_2+1}{2}\right\rfloor}x^{2k_2+1}\\
&=\sum_{k_1}\binom{n}{k_1}(x^2)^{k_1}
+x\sum_{k_2}\binom{n}{k_2}(x^2)^{k_2}
=(1+x^2)^n+x(1+x^2)^n\\
&=(1+x)(1+x^2)^n
\end{aligned}
\]
Problema 5. Queremos calcular
f(n)=\sum_{m>0}\sum_{\substack{k_1+k_2+\cdots+k_m=n\\ k_1,k_2,\ldots,k_n>0}}F_{k_1}F_{k_2}\cdots F_{k_m}
\]
Seja \(G(x)=\sum f(n)x^n\) e \(\frac{x}{1-x-x^2}=A(x)=\sum F_kx^k\) a geratriz dos Fibonacci. Perceba que
\begin{aligned}
G(x)&=\sum_n x^n\sum_{m>0}\sum_{\substack{k_1+k_2+\cdots+k_m=n\\ k_1,k_2,\ldots,k_n>0}}F_{k_1}F_{k_2}\cdots F_{k_m}\\
&=\sum_n\sum_{m>0}\sum_{\substack{k_1+k_2+\cdots+k_m=n\\ k_1,k_2,\ldots,k_n>0}}F_{k_1}x^{k_1}F_{k_2}x^{k_2}\cdots F_{k_m}x^{k_n}\\
&=\sum_{m>0}\sum_{\substack{k_1+k_2+\cdots+k_m=n\\ k_1,k_2,\ldots,k_n>0}}\sum_n F_{k_1}x^{k_1}F_{k_2}x^{k_2}\cdots F_{k_m}x^{k_n}\\
&=\sum_{m>0}\sum_{k_1,k_2,\ldots,k_n>0}F_{k_1}x^{k_1}F_{k_2}x^{k_2}\cdots F_{k_m}x^{k_n}\\
&=\sum_{m>0}\left(\sum_{k_1>0}F_{k_1}x^{k_1}\right)\left(\sum_{k_2>0}F_{k_2}x^{k_2}\right)\cdots\left(\sum_{k_m>0}F_{k_m}x^{k_m}\right)\\
&=\sum_{m>0}A(x)^m\\
&=\frac{A(x)}{1-A(x)}
=\frac{x}{1-2x-x^2}
=\frac{x}{-(x-(\sqrt{2}-1))(x-(-1-\sqrt{2}))}\\
&=\frac{A}{x-(\sqrt{2}-1)}+\frac{B}{x-(-1-\sqrt{2})}
\end{aligned}
\]
onde \(A=\frac{\sqrt{2}-1}{-2\sqrt{2}}=\frac{\sqrt{2}-2}{4}\) e \(B=\frac{-1-\sqrt{2}}{2\sqrt{2}}=\frac{-2-\sqrt{2}}{4}\)
Portanto,
\begin{aligned}
G(x)&=\frac{1}{4}\left(\frac{\sqrt{2}-2}{x-(\sqrt{2}-1)}+\frac{-2-\sqrt{2}}{x-(-1-\sqrt{2})}\right)\\
&=\frac{1}{4}\left(\frac{\sqrt{2}-2}{x-(\sqrt{2}-1)}+\frac{-2-\sqrt{2}}{x-(-1-\sqrt{2})}\right)\\
&=\frac{1}{4}\left(-\frac{\frac{\sqrt{2}-2}{\sqrt{2}-1}}{1-\frac{x}{\sqrt{2}-1}}-\frac{\frac{-2-\sqrt{2}}{-1-\sqrt{2}}}{1-\frac{x}{-1-\sqrt{2}}}\right)\\
&=\frac{1}{4}\left(\frac{\sqrt{2}}{1-\frac{x}{\sqrt{2}-1}}-\frac{\sqrt{2}}{1-\frac{x}{-1-\sqrt{2}}}\right)\\
&=\frac{\sqrt{2}}{4}\left(\frac{1}{1-\frac{x}{\sqrt{2}-1}}-\frac{1}{1-\frac{x}{-1-\sqrt{2}}}\right)
\end{aligned}
\]
\Rightarrow f(n)=[x^n]=\frac{\sqrt{2}}{4}\left(\left(\frac{1}{\sqrt{2}-1}\right)^n-\left(\frac{1}{-1-\sqrt{2}}\right)^n\right)
\]
Obs: a sequência \(f(n)\) que achamos é famosa: ela é conhecida como a Sequência dos Números de Pell. Tal sequência ordena os denominadores (em ordem crescente de precisão) dos racionais que melhor aproximam o valor de \(\sqrt{2}\). Clique aqui para saber mais.
Problema 6. Queremos calcular
f(n)=\sum_{n=\Sigma 2^ia_i}\prod_{i=0}^{\infty}\binom{k}{a_i}
\]
Seja
\begin{aligned}
F(x)&=\sum f(n)x^n
=\sum_n\sum_{n=\Sigma 2^ia_i}x^n\prod_{i=0}^{\infty}\binom{k}{a_i}\\
&=\sum_n\sum_{(\Sigma 2^ia_i)=n}x^{\Sigma 2^ia_i}\prod_{i=0}^{\infty}\binom{k}{a_i}\\
&=\sum_n\sum_{(\Sigma 2^ia_i)=n}\prod_{i=0}^{\infty}\binom{k}{a_i}(x^{2^i})^{a_i}\\
&\overset{\text{inverto }\Sigma\text{‘s}}{=}\sum_{a_1,a_2,\ldots}\sum_{n=\Sigma 2^ia_i}\prod_{i=0}^{\infty}\binom{k}{a_i}(x^{2^i})^{a_i}\\
&=\sum_{a_1,a_2,\ldots}\prod_{i=0}^{\infty}\binom{k}{a_i}(x^{2^i})^{a_i}\\
&=\prod(1+x^{2^i})^k
=\left(\prod(1+x^{2^i})\right)^k\\
&=(1+x+x^2+x^3+\ldots)^k
=\frac{1}{(1-x)^k}
\overset{I2}{=}\sum_n\binom{n+k-1}{k-1}x^n
\end{aligned}
\]
\Rightarrow f(n)=\binom{n+k-1}{k-1}
\]
Problema 7. Primeiramente, calculemos \(p(n)=\#\) partições de \(n\) em potências de \(2\). Tal número é o coeficiente de \(x^n\) em:
P(x)=(1+x^2+x^4+x^6+\ldots)(1+x^4+x^8+x^{12}+\ldots)\cdots=\prod_i\frac{1}{1-x^{2^i}}
\]
Dessa forma, queremos achar
F(x)=\sum_n v(n)x^n
\]
em função de \(P(x)\) para descobrir quanto vale \(\frac{V}{P}=\frac{v(n)}{p(n)}\)
Vamos achar uma recursão para \(v(n)\). Olhando para o tamanho \(i\) do ciclo em que o \(1\) está, temos \(\binom{n-1}{i-1}\) opções para escolher os elementos restantes dele. Ademais, devemos ordenar essa permutação circular: \(\{1,\pi(1),\pi(\pi(1)),\ldots,\pi^{i-1}(1),\pi^i(1)=1\}\). Como tem \(i\) elementos, devemos multiplicar po \((i-1)!\). Além disso, há \(2^{v_2(i)+1}-1\) escolhas possíveis da função binária nesse ciclo (qualquer subconjunto dos \(v_2(i)+1\) maiores, sem ser o subconjunto vazio).
Assim, restam \(n-i\) números e podemos associá-los a \(v(n-i)\). Dessa forma, chegamos a:
v(n)=\sum_{i\ge1}\binom{n-1}{i-1}(i-1)!(2^{v_2(i)+1}-1)v(n-i)
=\sum_{i\ge1}\frac{(n-1)!}{(n-i)!}(2^{v_2(i)+1}-1)v(n-i)
\]
\Leftrightarrow
\frac{v(n)}{n!}=\frac{1}{n}\sum_{i\ge1}(2^{v_2(i)+1}-1)\frac{v(n-i)}{(n-i)!}
\]
Seja \(F(x)=\sum \frac{v(n)}{n!}x^n\). Provaremos que \(F(x)=P(x)\Rightarrow \frac{v(n)}{n!}=p(n)\Rightarrow \frac{V}{P}=\frac{v(n)}{p(n)}=n!\).
Temos:
\begin{aligned}
F(x)&=\sum_n\frac{1}{n}x^n\sum_{i\ge1}(2^{v_2(i)+1}-1)\frac{v(n-i)}{(n-i)!}
\Rightarrow
F'(x)=\sum_n x^{n-1}\sum_{i\ge1}(2^{v_2(i)+1}-1)\frac{v(n-i)}{(n-i)!}\\
\Rightarrow xF'(x)&=\sum_n\sum_{i\ge1}(2^{v_2(i)+1}-1)\frac{v(n-i)}{(n-i)!}x^n
=\sum_{i\ge1}\sum_n(2^{v_2(i)+1}-1)\frac{v(n-i)}{(n-i)!}x^n\\
&=\sum_{i\ge1}(2^{v_2(i)+1}-1)x^i\sum_n\frac{v(n-i)}{(n-i)!}x^{n-i}
=\sum_{i\ge1}(2^{v_2(i)+1}-1)x^iF(x)\\
&=F(x)\sum_{i\ge1}(2^{v_2(i)+1}-1)x^i\\
\Rightarrow\frac{F'(x)}{F(x)}&=\frac{1}{x}\sum_{i\ge1}(2^{v_2(i)+1}-1)x^i
=\sum_{i\ge1}(2^{v_2(i)+1}-1)x^{i-1}\\
&=\sum_k\sum_j(2^{k+1}-1)x^{(2j+1)2^k-1}\\
&=\sum_k(2^{k+1}-1)x^{2^k-1}\sum_j x^{2^{k+1}j}
=\sum_k(2^{k+1}-1)\frac{x^{2^k-1}}{1-x^{2^{k+1}}}
\end{aligned}
\]
Vamos integrar os dois lados. Primeiramente, note que
\int \frac{F’}{F}dx=\int \frac{dF}{dx}\cdot\frac{1}{F}dx=\int \frac{1}{F}dF=\log F\Rightarrow F=\exp\left(\int \frac{F’}{F}dx\right)
\]
Mas, perceba que fazendo \(u=x^{2^k}\Rightarrow du=2^kx^{2^k-1}dx\) e temos:
\begin{aligned}
\int \frac{x^{2^k-1}}{1-x^{2^{k+1}}}dx
&=\int \frac{1}{2^k}\frac{1}{1-u^2}du\\
&=\int \frac{1}{2^{k+1}}\left(\frac{1}{1-u}+\frac{1}{1+u}\right)du\\
&=\frac{1}{2^{k+1}}\log\left(\frac{1+u}{1-u}\right)+C\\
&=\frac{1}{2^{k+1}}\log\left(\frac{1+x^{2^k}}{1-x^{2^k}}\right)+C
\end{aligned}
\]
\Rightarrow
\int \frac{F’}{F}dx
=\sum_k\int (2^{k+1}-1)\frac{x^{2^k-1}}{1-x^{2^{k+1}}}dx
=\sum_k\frac{2^{k+1}-1}{2^{k+1}}\log\left(\frac{1+x^{2^k}}{1-x^{2^k}}\right)
\]
\Rightarrow
F=\exp\left(\int\frac{F’}{F}dx\right)
=\exp\left(\sum_k\left(1-\frac{1}{2^{k+1}}\right)\log\left(\frac{1+x^{2^k}}{1-x^{2^k}}\right)+C\right)
=e^C\prod_k\left(\frac{1+x^{2^k}}{1-x^{2^k}}\right)^{\left(1-\frac{1}{2^{k+1}}\right)}
\]
Contudo, sabemos que \([x^0]\) em \(F\) é \(1\Rightarrow e^C=1\). Logo,
F=\prod_k\left(\frac{1+x^{2^k}}{1-x^{2^k}}\right)^{\left(1-\frac{1}{2^{k+1}}\right)}
\]
e queremos provar que \(F=P\)
\Leftrightarrow
\prod_k\left(\frac{1+x^{2^k}}{1-x^{2^k}}\right)^{\left(1-\frac{1}{2^{k+1}}\right)}
=\prod_k\frac{1}{1-x^{2^k}}
\Leftrightarrow
1=\prod_k(1+x^{2^k})^{\left(1-\frac{1}{2^{k+1}}\right)}(1-x^{2^k})^{\frac{1}{2^{k+1}}}
\]
=\prod_k(1+x^{2^k})^{\left(1-\frac{1}{2^{k+1}}\right)}
\left((1-x)(1+x)(1+x^2)\ldots(1+x^{2^{k-1}})\right)^{\frac{1}{2^{k+1}}}
=G(x)
\]
Note que \(v_{(1-x)}(G(x))=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=1\) e \(v_{(1+x^{2^k})}(G(x))=1-\frac{1}{2^{k+1}}+\frac{1}{2^{k+2}}+\frac{1}{2^{k+3}}+\frac{1}{2^{k+4}}+\cdots=1\)
\Rightarrow 1=G(x)\Leftrightarrow 1=(1-x)\prod_k(1+x^{2^k})\Leftrightarrow \prod_k(1+x^{2^k})=\frac{1}{1-x}
\]
Mas ambos são equivalentes à \(1+x+x^2+x^3+\ldots\), concluindo que \(\frac{V}{P}=n!\).