Fatoriais divisíveis

Recentemente, fiquei completamente perplexo com esse tweet da Farm Library:


"É o que acontece se você não se multiplicar, mas se dividir no fatorial."

Quando o vi, tive que desistir dos meus negócios, pegar um caderno e verificar a fórmula. O resultado preliminar parecia lógico. Desde a versão multiplicativa $$$n!$ com o aumento $$$n$ tende ao infinito, a versão "dividida" tende a zero. E $$$\ frac {n ^ 2} {n!}$ se comporta dessa maneira; função polinomial $$$n ^ 2$ cresce mais devagar que uma função de energia $$$n!$ para grande o suficiente $$$n$ :

$$

$$\ frac {1} {1}, \ frac {4} {2}, \ frac {9} {6}, \ frac {16} {24}, \ frac {25} {120}, \ frac {36 } {720}, \ frac {49} {5040}, \ frac {64} {40320}, \ frac {81} {362880}, \ frac {100} {3628800}$$

Mas por que o resultado da divisão assume a forma $$$\ frac {n ^ 2} {n!}$ ? De onde vem $$$n ^ 2$ ?

Para responder a essa pergunta, tive que desmontar o antigo trauma associado ao estudo da divisão fracionária, mas lidei com a dor. Passando da fórmula do tweet da esquerda para a direita, obtemos primeiro $$$\ frac {n} {n-1}$ . Em seguida, dividindo esse valor por $$$n-2$ nós temos

$$

$$\ cfrac {\ frac {n} {n-1}} {n-2} = \ frac {n} {(n-1) (n-2)}$$

Continuando dessa maneira, terminamos com:

$$

$$n \ mathbin {/} (n-1) \ mathbin {/} (n-2) \ mathbin {/} (n-3) \ mathbin {/} \ cdots \ mathbin {/} 1 = \ frac {n } {(n-1) (n-2) (n-3) \ cdots 1} = \ frac {n} {(n-1)!}$$

Para obter o resultado mostrado no tweet $$$\ frac {n ^ 2} {n!}$ , apenas multiplicamos o numerador e o denominador por $$$n$ . (Embora para o meu gosto, a expressão $$$\ frac {n} {(n-1)!}$ mais claro.)

---

Eu sou um fã fatorial oficialmente reconhecido. Mantenha suas seqüências de Fibonacci com você; aqui está o meu recurso favorito. Toda vez que aprendo uma nova linguagem de programação, meu primeiro exercício é escrever vários procedimentos para calcular fatoriais. Ao longo dos anos, propus várias variações deste tópico, por exemplo, uma substituição na definição $$$\ vezes$ em $$$+$ (que nos fornece números triangulares). Mas parece que eu nunca pensei em substituir antes $$$\ vezes$ em $$$\ mathbin {/}$ . Acontece estranho. Como a multiplicação é comutativa e associativa, podemos definir $$$n!$ assim como o produto de todos os números inteiros de $$$1$ antes $$$n$ sem se preocupar com a ordem das operações. Mas, ao dividir, a ordem não pode ser ignorada. No caso geral $$$x \ mathbin {/} y \ ne y \ mathbin {/} x$ e $$$(x \ mathbin {/} y) \ mathbin {/} z \ ne x \ mathbin {/} (y \ mathbin {/} z)$ .

No tweet da Farm Library, os divisores estão em ordem decrescente: $$$n, n-1, n-2, \ ldots, 1$ . Obviamente, isso será substituído por uma ordem crescente: $$ . O que acontece se definirmos o fatorial de divisão como $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ ? Outro retorno ao algoritmo da divisão fracionária da escola nos dá uma resposta simples:

$$

$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n = \ frac {1} {2 \ vezes 3 \ vezes 4 \ times \ cdots \ times n} = \ frac {1} {n!}$$

Em outras palavras, quando fazemos divisão muitas vezes, fazendo uma contagem de $$$1$ antes $$$n$ , o resultado final será igual ao valor recíproco $$$n!$ . (Gostaria de colocar um ponto de exclamação no final desta frase, mas infelizmente!) Se você estiver procurando uma resposta canônica para a pergunta “O que obtemos ao dividir em vez de multiplicar em $$$n!$ ? ", Então eu diria que $$$\ frac {1} {n!}$ É um candidato melhor do que $$$\ frac {n} {(n - 1)!}$ . Por que não aceitamos a simetria entre $$$n!$ e seu valor inverso?

Obviamente, existem muitas outras maneiras de colocar n valores inteiros no conjunto $$$\ {1 \ ldots n \}$ . Mas quanto exatamente? Como se viu, exatamente $$$n!$ ! Portanto, pode parecer que exista $$$n!$ maneiras únicas de definir uma função de divisão $$$n!$ . No entanto, estudar as respostas das duas permutações mostradas acima nos faz entender que um padrão mais simples funciona aqui. Qualquer que seja o elemento da sequência que apareça primeiro, ele aparece no numerador de uma grande fração e o produto de todos os outros elementos é o denominador. Portanto, no final, há apenas $$$n$ resultados diferentes (assumindo que sempre realizamos operações de divisão estritamente da esquerda para a direita). Para qualquer número inteiro $$$k$ na faixa de $$$1$ antes $$$n$ definindo $$$k$ no início da linha, criamos uma divisão $$$n!$ igual a $$$k$ dividido por todos os outros fatores. Você pode escrever isso da seguinte maneira:

$$

$$\ cfrac {k} {\ frac {n!} {k}}, \ text {que pode ser convertido em} \ frac {k ^ 2} {n!}$$

Então resolvemos um pequeno enigma sobre como neste tweet $$$\ frac {n} {(n-1)!}$ transformado em $$$\ frac {n ^ 2} {n!}$ .
Vale ressaltar que todas essas funções convergem para zero quando $$$n$ ao infinito. Do ponto de vista assintótico, $$$\ frac {1 ^ 2} {n!}, \ frac {2 ^ 2} {n!}, \ ldots, \ frac {n ^ 2} {n!}$ idêntico.

---

Sim Missão cumprida. O problema está resolvido. O trabalho está feito. Agora sabemos tudo o que precisamos sobre a divisão de fatoriais, certo?

Bem, talvez haja mais uma pergunta. O que o computador dirá? Se pegarmos nosso algoritmo fatorial favorito e fizermos o que é proposto em um tweet, substituindo todas as ocorrências do operador $$$\ vezes$ (ou * ) em / , o que acontecerá? Qual dos $$$n$ opções de divisão $$$n!$ o programa nos dará?

Aqui está o meu algoritmo favorito para calcular fatoriais como um programa em Julia :

 function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end end 

Esse algoritmo introduziu gerações inteiras de nerds no conceito de recursão. Em forma de texto, ele lê: se $$$n$ é igual a $$$1$ então $$$mul! (n)$ é igual a $$$1$ . Caso contrário, você precisa calcular a função $$$mul! (n-1)$ e depois multiplique o resultado por $$$n$ .

_{Você pode perguntar o que acontece se} $$_{$n$ será zero ou negativo. Você pode perguntar, mas é melhor não. Para nossos objetivos atuais} $$_{$n \ in \ mathbb {N}$ .}

Começando com qualquer positivo $$$n$ , a sequência de chamadas recursivas, mais cedo ou mais tarde, cairá para $$$n = 1$ .

Uma função pode ser escrita de forma mais sucinta usando o estilo de definição Julia de linha única:

 mul!(n) = n == 1 ? 1 : n * mul!(n - 1) 

A parte correta do operador de atribuição é uma expressão condicional ou um operador ternário do formulário a ? b : c a ? b : c . Aqui a é a condição booleana do teste, que deve retornar true ou false . Se a for true , a expressão b avaliada e o resultado se tornará o valor de toda a expressão. Caso contrário, c calculado.

Apenas para garantir que eu fiz tudo certo, aqui estão os 10 primeiros fatoriais calculados por este programa:

 [mul!(n) for n in 1:10] 10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 

Agora, vamos mudar essa definição e transformar a única ocorrência * em / , deixando todo o resto inalterado (exceto o nome da função).

 div!(n) = n == 1 ? 1 : n / div!(n - 1) 

E é isso que o programa retornará se o executarmos para os valores $$$n$ de $$$1$ antes $$$20$ :

 [div!(n) for n in 1:20] 20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418 

O que? Definitivamente, não é como convergir para zero, assim como $$$\ frac {1} {n!}$ ou $$$\ frac {n} {n - 1}$ . De fato, os valores não são assim, porque não vão convergir. A julgar pelo gráfico abaixo, a sequência consiste em dois componentes intermitentes, cada um dos quais parece crescer lentamente em direção ao infinito e também se desvia do outro.


Entendendo o que estamos observando aqui, será útil alterar o tipo de saída da função div! . Em vez de usar o operador de divisão / , que retorna o valor como um número de ponto flutuante, podemos substituí-lo pelo operador // , que retorna o valor racional exato, arredondado para o termo mais baixo.

 div!(n) = n == 1 ? 1 : n // div!(n - 1) 

Aqui está uma sequência de valores para n 1:20 :

 20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189 

A lista está cheia de padrões interessantes. É uma hélice dupla na qual números pares e ímpares em zigue-zague se movem em segmentos complementares. Números pares não são apenas pares, são todos graus $$$2$ . Além disso, eles aparecem em pares - primeiro no numerador, depois no denominador - e sua sequência não diminui. Mas existem lacunas; nem todos os graus estão presentes $$$2$ . O fio ímpar parece ainda mais complexo, diferentes coeficientes simples pequenos aparecem e desaparecem nos números. (Os números primos devem ser pequenos, pelo menos menos $$$n$ .)

Esse resultado me surpreendeu. Eu esperava ver uma sequência muito mais suave, como as que calculei no papel. Todos esses saltos quebrados e tristes não faziam sentido. A tendência geral de crescimento ilimitado na proporção também não fazia sentido. Como podemos nos dividir constantemente, ao receber todos os números cada vez maiores?

Nesse ponto, você pode pausar a leitura e tentar criar sua própria teoria sobre a origem desses números em zigue-zague. Se você precisa de uma dica, tem uma, e muito forte, quase um spoiler: procure uma sequência de numeradores ou uma sequência de denominadores na Enciclopédia on-line de sequências inteiras .

---

Aqui está outra pista. Uma pequena mudança no programa div! converte completamente a saída. Apenas mude a última expressão substituindo n // div!(n - 1) por div!(n - 1) // n .

 div!(n) = n == 1 ? 1 : div!(n - 1) // n 

Agora os resultados são assim:

 10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800 

Essa é a função inversa do fatorial que já vimos, uma série de valores gerados indo da esquerda para a direita em uma sequência crescente de divisores $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ .

Não é de surpreender que a alteração da última expressão em um procedimento altere o resultado. No final, sabemos que a divisão não é comutativa nem associativa. Mas é difícil entender por que a sequência de valores gerados pelo programa original apresenta uma forma em zigue-zague tão estranha. Que mecanismo dá origem a tais poderes emparelhados de dois e alternando valores ímpares e pares?

Descobri que explicar o que está acontecendo em uma sequência em zigue-zague é mais fácil em uma versão iterativa do procedimento, do que em uma versão recursiva. (Essa afirmação pode parecer irritante para quem acha as definições recursivas mais simples, mas acabou de acontecer.) Veja como é o programa:

 function div!_iter(n) q = 1 for i in 1:n q = i // q end return q end 

Declaro que esse procedimento com um ciclo funcional é idêntico a uma função recursiva, no sentido de que se div!(n) e div!_iter(n) retornam um resultado para algum número inteiro positivo n , então sempre será o mesmo. Aqui está a minha prova:

 [div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189 

Para entender o processo que gera esses números, considere os valores seqüenciais das variáveis $$$i$ e $$$q$ toda vez que você executa um loop Originalmente $$$i$ e $$$q$ são iguais $$$1$ ; portanto, após a primeira passagem do ciclo, a expressão q = i // q fornece $$$q$ valor $$$\ frac {1} {1}$ . Então $$$i = 2$ e $$$q = \ frac {1} {1}$ isto é, um novo significado $$$q$ é igual a $$$\ frac {2} {1}$ . Na terceira iteração $$$i = 3$ e $$$q = \ frac {2} {1}$ isso nos dá $$$\ frac {i} {q} \ rightarrow \ frac {3} {2}$ . Se isso ainda é confuso, imagine $$$\ frac {i} {q}$ como $$$i \ times \ frac {1} {q}$ . Uma observação importante aqui é que a cada ciclo de loop $$$q$ obtém o valor oposto, tornando-se $$$\ frac {1} {q}$ .

Se você expandir essas operações e observar as multiplicações e divisões incluídas em cada elemento da série, surgirá um padrão:

$$

$$\ frac {1} {1}, \ quad \ frac {2} {1}, \ quad \ frac {1 \ cdot 3} {2}, \ quad \ frac {2 \ cdot 4} {1 \ cdot 3 }, \ quad \ frac {1 \ cdot 3 \ cdot 5} {2 \ cdot 4} \ quad \ frac {2 \ cdot 4 \ cdot 6} {1 \ cdot 3 \ cdot 5}$$

De forma geral:

$$

$$\ frac {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n} {2 \ cdot 4 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {odd} n) \ qquad \ frac {2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n} {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {even} n)$$

---

Funções $$$1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n$ para estranho $$$n$ e $$$2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n$ por igual $$$n$ tem seu próprio nome! Eles são chamados fatoriais duplos e são escritos como $$$n !!$ .

_{Terminologia horrível, certo? Seria melhor se eles fossem chamados de "semi-fatoriais". E se eu não soubesse, eu leria} $$_{$n !!$ como fatorial fatorial.}

O fatorial duplo n é definido como o produto de n e todos os números inteiros positivos menores da mesma paridade. Portanto, nossa curiosa sequência de valores em zigue-zague é apenas $$$\ frac {n !!} {(n-1) !!}$ .

Um artigo de 2012 de Henry W. Gould e Jocelyn Quentens (infelizmente, por trás do paywall) explora o uso de fatoriais duplos. Eles são muito mais comuns do que você imagina. Em meados do século XVII, John Wallis derivou a seguinte identidade:

$$

$$\ frac {\ pi} {2} = \ frac {2 \ cdot 2 \ cdot 4 \ cdot 4 \ cdot 6 \ cdot 6 \ cdots} {1 \ cdot 3 \ cdot 3 \ cdot 5 \ cdot 5 \ cdot 7 \ cdots} = \ lim_ {n \ rightarrow \ infty} \ frac {((2n) !!) ^ 2} {(2n + 1) !! (2n - 1) !!}$$

Uma série ainda mais estranha envolvendo um cubo de valores fatoriais duplos é resumida em $$$\ frac {2} {\ pi}$ . Ele foi descoberto por ninguém menos que Srinivasa Ramanujan.

Gould e Kientens também consideraram o duplo fatorial equivalente para os coeficientes binomiais. O coeficiente binomial padrão é definido como:

$$

$$\ binom {n} {k} = \ frac {n!} {k! (n-k)!}$$

A versão dupla é assim:

$$

$$\ left (\! \ binom {n} {k} \! \ right) = \ frac {n !!} {k !! (n-k) !!}$$

Observe que nossos números em zigue-zague correspondem a essa descrição e, portanto, podem ser considerados coeficientes binomiais de fatoriais duplos. Mais especificamente, são esses números:

$$

$$\ left (\! \ binom {n} {1} \! \ right) = \ left (\! \ binom {n} {n - 1} \! \ right) = \ frac {n !!} {1 !! (n-1) !!}$$

Feijão $$$\ binom {n} {1}$ não é muito interessante; ele é igual $$$n$ . Mas a versão dupla $$$\ left (\! \ binom {n} {1} \! \ right)$ como vimos, uma dança mais animada está dançando. E, diferentemente do binômio usual, nem sempre é um número inteiro. (Os únicos valores inteiros são $$$1$ e $$$2$ .)

Uma olhada nos números em zigue-zague como um quociente de fatoriais duplos explica algumas de suas propriedades, começando com valores pares e ímpares alternados. Também podemos ver por que todos os números pares na sequência são potências de 2. Considere o exemplo com $$$n = 6$ . O numerador dessa fração é $$$2 \ cdot 4 \ cdot 6 = 48$ recebendo de $$$6$ multiplicador $$$3$ . Mas o denominador é $$$1 \ cdot 3 \ cdot 5 = $ 1$ . Os trigêmeos acima e abaixo encolhem, deixando-nos $$$\ frac {16} {5}$ . Tais reduções ocorrem em cada caso. Sempre que um fator ímpar aparece na sequência de números pares $$$m$ , necessariamente tem a forma $$$2 \ cdot m$ mas a essa altura $$$m$ já deve aparecer em uma sequência de números ímpares.

---

Uma sequência de números em zigue-zague é uma resposta razoável à pergunta: “O que acontece se nos dividirmos, em vez de nos multiplicarmos? $$$n!$ ? " Ou o programa de computador que os gerou acabou se revelando um algoritmo errado? Na minha opinião pessoal, $$$\ frac {1} {n!}$ - uma resposta mais intuitiva, mas $$$\ frac {n !!} {(n - 1) !!}$ mais interessante.

Além disso, a própria existência de uma sequência em zigue-zague amplia nossos horizontes. Como afirmado acima, se você insistir em que o algoritmo de divisão sempre deve estar em ordem na lista de numeradores $$$n$ , em cada etapa que divide o número à esquerda pelo número à direita, há um total $$$n$ resultados possíveis, e todos eles parecem muito semelhantes. Mas a solução em zigue-zague oferece possibilidades muito mais amplas. Podemos formular o problema da seguinte maneira: pegue o conjunto de numeradores $$$\ {1 \ dots n \}$ , escolha seu subconjunto e inverta todos os elementos desse subconjunto; Agora multiplicamos todos os numeradores, inversos e diretos. Se o subconjunto invertido estiver vazio, o resultado será um fatorial regular $$$n!$ . Se todos os numeradores se tornaram inversos aos seus valores, obtemos o oposto $$$\ frac {1} {n!}$ . E se cada segundo numerador for convertido, começando com $$$n - 1$ , o resultado será um elemento de uma sequência em zigue-zague.

Estas são apenas algumas das muitas opções disponíveis; no total existe $$$2 ^ n$ subconjuntos de $$$n$ elementos. Por exemplo, você pode tomar o inverso de cada número que é primo ou um poder primo $$$(2, 3, 4, 5, 7, 8, 9, 11, \ pontos)$ . Em pequenas $$$n$ os resultados estão saltando, mas permanecem constantemente abaixo de $$$1$ :


No entanto, se eu continuasse este gráfico por mais $$$n$ , ele decolaria na estratosfera. Os graus dos primos se tornam muito esparsos na linha numérica.

---

Agora vou fazer uma pergunta. Vimos variações fatoriais próximas de zero como $$$n$ ao infinito, por exemplo $$$1 / n!$ . Vimos outras variações crescendo com o aumento $$$n$ ilimitado, inclusive eu $$$n!$ e números em zigue-zague. Existem variedades do processo fatorial que convergem para algum limite finito que não é zero?

Primeiro de tudo, o seguinte algoritmo me ocorreu:

 function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q end 

Passamos por valores inteiros de $$$n$ até $$$1$ cálculo do produto / quociente atual no processo $$$q$ . Em cada etapa, se o valor atual $$$q$ mais $$$1$ , dividimos pelo próximo numerador, caso contrário, realizamos a multiplicação. Esse esquema implementa algum tipo de gerenciamento de feedback ou comportamento de pesquisa de destino. Se $$$q$ ficando muito grande, reduzimos; se for muito pequeno, aumentamos. Sugeri que, enquanto se esforça $$$n$ ao infinito $$$q$ convergirá para uma faixa de valores constantemente reduzida ao lado de $$$1$ .

Mas o experimento me lançou outra surpresa:


Essa onda de dente de serra não é exatamente o que eu esperava. Curiosamente, a curva não é simétrica em torno de $$$1$ ; desvios de cima têm uma amplitude maior do que de baixo. Mas essa distorção é mais visual do que matemática. Desde $$$q$ é privado, distância do $$$1$ antes $$$10$ igual à distância de $$$1$ antes $$$\ frac {1} {10}$ mas em uma escala linear não se parece com isso. Você pode corrigir isso compilando um gráfico logarítmico do quociente:


Agora o gráfico é simétrico, ou pelo menos aproximadamente o mesmo, e centralizado em relação ao valor $$$0$ qual é o logaritmo $$$1$ . Mas permanece um segredo mais sério. Onda dente de serra é muito regular e tem um período $$$4$ , embora não mostre sinais de compressão na direção do valor-limite esperado $$$\ log q = 0$ . Valores numéricos sugerem que quando $$$n$ até o infinito, os picos da curva convergem para um valor ligeiramente maior $$$q = \ frac {5} {3}$ , e os mínimos estão chegando a um valor um pouco menor $$$q = \ frac {3} {5}$ . (Logaritmos de base correspondentes $$$10$ são aproximadamente iguais $$$\ pm0.222$ ) Eu não conseguia descobrir por que isso está acontecendo. Talvez alguém possa explicar.

A falha neste algoritmo ganancioso não significa que não possamos dividir o fatorial convergente para $$$q = 1$ .

_{Se trabalharmos com os logaritmos dos numeradores, esse procedimento se tornará o caso de um conhecido problema computacional chamado "problema de dividir um conjunto de números". Recebemos muitos números reais e devemos dividi-los em dois conjuntos, cuja soma é igual ou o mais próximo possível da igualdade. Essa é uma tarefa comprovadamente difícil, mas também é chamada ( PDF ) de "a tarefa complexa mais simples".}

Para qualquer $$$n$ podemos descobrir que, ao usar os valores inversos de algum outro subconjunto de numeradores, é possível obter uma melhor aproximação de $$$n! = 1$ . Para pequenas $$$n$ podemos resolver esse problema com força bruta: basta considerar tudo $$$2 ^ n$ subconjuntos e escolha o melhor.

Calculei as partições ideais até $$$n = 30$ quando você precisar escolher entre um bilhão de opções.


Obviamente, o gráfico está ficando mais plano. Você pode usar o mesmo método para forçar a convergência para qualquer outro valor no intervalo de $$$0$ antes $$$n!$ .

E assim obtemos outra resposta para a pergunta feita pelo tweet e começamos nossa jornada. O que acontece se dividirmos e não multiplicarmos $$$n!$ ? Tudo o que quisermos.