[seqfan] divisor convolution

[Christian G.Bower]

After working out formulas to the necklace sequences, I noticed it
was common for the formulas to contain something like:

sum{d|n}(a(n/d)*b(d))

It occurred to me that this might be a good operation to define on
sequences. Thus I'm defining "divisor convolution" or DCONV as follows:

(a DCONV b)(n) = sum{d|n}(a(n/d)*b(d))

Here I'm taking n>=1, i.e. a(0)=b(0)=0.
All sequences shown below begin at index 1.

Thus if c = a DCONV b and A, B and C are the generating functions of
a, b and c then

C(x) = sum{i>=1}(b(i)*A(x^i)) = sum{i>=1}(a(i)*B(x^i))

If a and b each count the number of unlabeled structures of some
type, then (a DCONV b) counts structures defined as follows.

Sets of identical b-structures organized according to a.

For example: 2^n counts the number of strings of n 2-colored beads.
             3^n counts the number of strings of n 3-colored beads.
So 2^n DCONV 3^n counts strings of 2 colored large beads where each
large bead contains an identical string of 3-colored small beads.
The "n" is the total number of small beads.
(Don't count the large beads.)

 BLACK      WHITE      WHITE      BLACK
+-----+    +-----+    +-----+    +-----+
|black|    |black|    |black|    |black|
|white|    |white|    |white|    |white|
| red |----| red |----| red |----| red |
| red |    | red |    | red |    | red |
|white|    |white|    |white|    |white|
+-----+    +-----+    +-----+    +-----+

A 2^n DCONV 3^n structure for n=20.

The number of structures for n>=1 is:
6,30,78,246,582,1830,4758,...
(Not in EIS, yet)

(*)
One sequence, surprisingly not in the EIS is:
set I(n)=n. I DCONV I is
1,4,6,12,10,24,14,32,27,40,...
d(n)*n where d is the number of divisors of n

The Moebius transform of any sequence a is
mu DCONV a

The Inverse Moebius transform is
(all ones) DCONV a

A couple sequence that are in the EIS
phi (A000010) DCONV phi
1,2,4,5,8,8,12,12,16,16,20
A029935

I DCONV phi
1,3,5,8,9,15,13,20,21,27,21
A018804
Sum of gcd(k,n) for 1 <= k <= n.

A018804 is the Moebius transform of (*) and the
Inverse Moebius transform of A029935.

So far I have counted only unlabeled objects. How about labeled?

I'll defined an operation exponential divisor convolution
(EXP-DCONV) which (I believe) constructs the same sort of structure
when the objects are labeled.

(a EXP-DCONV b)(n) = sum {d|n}((a(d)*b(n/d)^d*n!)/(d!*((n/d)!)^d)

A simple example:

(all ones) EXP-DCONV (all ones) is
1,2,2,5,2,27,2,142,282,1073,2,32034,...
Not in EIS!
Number of ways to partition a labeled set into subsets of equal size.
Exponential generating function: sum {k>=1} (exp(x^k/k!)-1)

Note that EXP-DCONV is not commutative even though DCONV is.

(all ones) EXP-DCONV (all twos) is
2,6,10,30,34,226,130,207,...

(all twos) EXP-DCONV (all ones) is
2,4,4,10,4,54,4,284,564,...

Hope others out there find uses for these tools.

Christian


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