[EULER transformation.]

[Antti Karttunen]

Christian Bower asked me to forward this reply also publicly
to SeqFan list:

-------- Original Message --------
Subject: Re: [EULER transformation.]
Date: 7 Jun 2001 10:56:43 PDT
From: "Christian G.Bower" <bowerc at usa.net>
To: Antti Karttunen <karttu at megabaud.fi>

Antti Karttunen <karttu at megabaud.fi> wrote:
> 
> 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
> 
...
> Now, my QUESTION: does these auxiliary, intermediate transformations
> 
>    a_n <--> c_n <--> b_n
> 
> have any COMBINATORIAL significance, or are they just
> generatingfunctionological magic?
> 

If we are determined, we can come up with a combinatorial interpretation
for anything, including this intermediate sequence.

Using the connectedness analogy, if a is the connected structures, b the
not necessarily connected structures, then c can be identified as a set
of identical connected structures where the structure as a whole can be
colored k different ways where k is the size of the connected structure
and the structure as a whole is colored, not the individual nodes or
individual connected substructures.

So taking a=A001349 (connected graphs)
          b=A000088 (graphs)
          c=A003083 1,3,7,27,106,681,5972,88963...

c(4)=27 can be seen as the 6 connected graphs of order 4 in 4 colors
(for 24 structures)

A pair of 2 element connected graphs in 2 colors (for 2 structures)

A set of 4 isolated nodes in 1 color (for 1 structure).

Or take a=A000012 (all 1's)
        b=A000041 (partitions)
        c=A000203 (sigma, sim of divisors) 1,3,4,7,6,12,8...

for Antti's dash problem:
c(6)=12 can be seen as 1 connected 6-dash in 6 colors (6)

A pair of 3-dashes in 3 colors (3)

A trio of 2-dashes in 2 colors (2)

A sextet of 1-dashes in 1 color (1)

Christian


____________________________________________________________________
Get free email and a permanent address at http://www.netaddress.com/?N=1