[EULER transformation.]
Antti Karttunen
karttu at megabaud.fi
Fri Jun 8 10:14:17 CEST 2001
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
More information about the SeqFan
mailing list