Moebius function and expansion in sequence $A280194$

76 Views Asked by At

For my research interest, I came accross with OEIS sequence A280194

In particular I am interested how is obtained the value $36203$ in the sequence

Expansion of:

$\frac{1}{1-\sum_{k>=1}{\mu(k)^2\cdot x^k}}$ where $\mu$ is the Moebius function.

Let $a(n)$ denote a term in the sequence OEIS A280194. How is calculated for example $a(4)=7$?

1

There are 1 best solutions below

0
On

You asked

Let a(n) denote a term in the sequence Oeis A280194. How is calculated for example a(4)=7?

The OEIS sequence A280194 entry states:

EXAMPLE a(4) = 7 because we have [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2] and [1, 1, 1, 1].

This comes from the comment

Number of compositions (ordered partitions) into squarefree parts (A005117). INVERT transform of the absolute value of the Möbius function (A008966). - Alois P. Heinz, Feb 11 2021

and the example shows the $7$ compositions of $4$ into squarefree parts in reverse lexicographic order. To show that $a(5)=14$ list all of the 14 compositions of $5$ into squarefree parts

$$ \texttt{ 5 = 3+2 = 3+1+1 = 2+3 = 2+2+1 = 2+1+2 = 2+1+1+1 = 1+3+1 =}\\ \texttt{ 1+2+2 = 1+2+1+1 = 1+1+3 = 1+1+2+1 = 1+1+1+2 = 1+1+1+1+1}. $$

The interpretation as compositions into squarefree parts comes almost directly from the name of the sequence

Expansion of 1/(1 - Sum_{k>=1} mu(k)^2*x^k), where mu(k) is the Moebius function (A008683).

The square of the Moebius function is the indicator of squarefree numbers.

A simple example is the case of $\,1/(1 - x - x^2)\,$ which is the generating function of the Fibonacci numbers with $\,a(n)=0\,$ if $\,n<0,\,$ $\,a(0) = 1,\,$ and $\,a(n) = a(n-1)+a(n-2) \,$ if $\,n>0.\,$ The interpretation is that $\,a(n)\,$ is the number of compositions of $n$ into parts of $1$ and $2$ only.

Your question

In particular I am interested how is obtained the value 36203 in the sequence

asks how to evaluate $a(17) = 36203.$ In this case it is possible to write a program to systematically list all $36203$ compositions of $17$. An easier method is to use the recursion which comes from the generating function similar to the Fibonacci example. That is

$$ \texttt{ a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-5) + a(n-6) + a(n-7) + a(n-10)}\\ \texttt {+ a(n-11) + a(n-13) + a(n-14) + a(n-15) + a(n-17) +}\cdots. $$

The easiest method is to use a Computer Algebra System to do the calculation with power series.