[seqfan] divisor convolution

Christian G.Bower bowerc at usa.net
Fri Sep 18 15:15:31 CEST 1998

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


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|    |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:
(Not in EIS, yet)

One sequence, surprisingly not in the EIS is:
set I(n)=n. I DCONV I is
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

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
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

(all twos) EXP-DCONV (all ones) is

Hope others out there find uses for these tools.


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

More information about the SeqFan mailing list