EULER transformation.

[Antti Karttunen]

Dear Neil,
 Dear SeqFans,

In article by Bernstein and Sloane, Some canonical sequences of integers, Linear
Algebra and Its Applications, vol. 226-228, pp. 57-72, 1995
http://www.research.att.com/~njas/doc/eigen.ps
or  http://www.research.att.com/~njas/doc/eigen.pdf

there's the following text about the transformation

  EULER

  1 + Sum_{n=1..inf} b_n x^n = Product_{n=1..inf} 1/((1 - x^n)^a_n)

 If a_n enumerates a class of connected structures on n unlabeled nodes,
 b_n enumerates the same structures when connectedness is not required.
 b_n is also the number of ways of partitioning the integer n, given that
 there are a_k possible types of parts of size k, for k = 1,2,...

 ...
 (e.g. EULER([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]);
   gives the partition numbers, A000041: [1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56,
77, 101, 135, 176, 231]
   which can also be interpreted that all-1 sequence
   enumerates the connected sets of n dashes: {-}, {--}, {---}, {----}, {-----},
...
   and A000041 counts also the possible unconnected variants:
   {-}, {--, - -}, {---, -- -, - - -}, {----, --- -, -- --, -- - -, - - - -},
etc.)

 ...
 Calculations are facilitated by setting the left side equal to

  exp Sum_{n=1..inf} c_n x^n / n, so that

   c_n = n b_n - Sum_{k=1..n-1} c_k b_{n-k}

   a_n = 1/n Sum_{d|n} mu(n/d) c_d

(or maybe the following Maple code from
http://www.research.att.com/~njas/sequences/transforms.txt
is clearer:)


# EULER takes [a_1,a_2,a_3,...] and produces [b_1,b_2,b_3,...] with
# 1 + Sum_{n=1..inf} b_n x^n = 1 / Product_{n=1..inf} (1-x^n)^a_n.
EULER:=proc(a)  local b,c,i,d:
if whattype(a) <> list then RETURN([]); fi:
c:=[]:
for i to nops(a) do c:=[op(c), sum( 'd*did(i,d)*a[d] ', 'd'=1..i)]: od:
b:=[]:
for i to nops(a) do
b:=[op(b),(1/i)*(c[i]+ sum( 'c[d]*b[i-d]', 'd'=1..i-1))]: od:
RETURN(b);
end:

EULERi:=proc(b)  local a,c,i,d:
if whattype(b) <> list then RETURN([]); fi:
c:=[]:
for i to nops(b) do c:=[op(c),i*b[i]-sum('c[d]*b[i-d]', 'd'=1..i-1)]: od:
a:=[]:
for i to nops(b) do a:=[op(a),(1/i)*sum('mob(i,d)*c[d] ', 'd'=1..i)]: od:
RETURN(a);
end:

did:=proc(m,n) if irem(m,n) = 0 then 1           else 0: fi: end:
mob:=proc(m,n) if irem(m,n) = 0 then mobius(m/n) else 0: fi: end:

-----------------------------------------------------------------------

Now, my QUESTION: does these auxiliary, intermediate transformations

   a_n <--> c_n <--> b_n

have any COMBINATORIAL significance, or are they just
generatingfunctionological magic?

At least the transformation

   a_n = 1/n Sum_{d|n} mu(n/d) c_d

looks suspiciously like a formula for aperiodic necklaces (Lyndon words),
cf. for example A001037: a(n) = (1/n) sum_{d|n} mu(n/d) 2^d.
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001037




Terveisin,
  Salut,


Antti Karttunen