Further Transformations of Integer Sequences
This page was created by Christian G. Bower
and is a sub-page of the
On-Line Encyclopedia of Integer Sequences.
Keywords:
AFJ, AFK, AGJ, AGK, AIJ, BFJ, BFK, BGJ, BGK, BHJ, BHK, BIJ, BIK,
CFJ, CFK, CGJ, CGK, CHJ, CHK, CIJ, CIK,
DFJ, DFK, DGJ, DGK, DHJ, DHK, DIJ, DIK,
EFJ, EFK, EGJ.
Table of Contents
- Definition.
- Algorithms.
- Catalogue of Sequences.
- Back to Integer Sequences.
Part 1: Definition
This is a generalization of transforms that count the ways
objects can be partitioned.
Say we have boxes of different colors and sizes.
The sequence {an;n>=1}
represents the number of colors a box holding
n balls can be. The transformed sequence {bn;n>=1}
represents the
number of ways we can have a collection of boxes so that the
total number of balls is n, subject to the following rules.
The boxes are ordered in one of the following ways:
A. Linear (ordered)
The boxes are in a line from beginning to end.
B. Linear with turning over (reversible)
The boxes are in a line that can be read in either direction.
C. Circular (necklace)
The boxes are in a circle.
D. Circular with turning over (bracelet)
The boxes are in a circle that can be read in either direction.
E. None (unordered)
The order of the boxes is not important.
|
One of the following distinctness rules applies:
F. Size
No two boxes are the same size.
G. Element
No two boxes are the same size and color.
H. Identity
Any two boxes can be distinguished by size, color and position.
I. None (indistinct)
No restriction.
|
Distinctness H (identity) has different implications depending on the
chosen order.
- If order A is chosen, distinctness H is the same as distinctness I.
- If order B is chosen, the boxes cannot form a palindrome of length
greater than one.
Red 1
Blue 2
Red 1
is not allowed.
- If order C is chosen, the sequence of boxes is aperiodic.
It cannot be a repitition of a shorter subsequence.
Red 1
Blue 2
Red 1
Blue 2
is not allowed.
- If order D is chosen, the boxes are aperiodic and cannot be a palindrome
of length greater than two.
- If order E is chosen, distinctness H is the same as distinctness G.
One of the following labelling rules applies:
J. Labeled
The balls in the boxes are labeled.
K. Unlabeled
The balls in the boxes are not labeled.
|
Each transform is identified by a 3 letter code, e.g.
BGJ
to represent
linear order with turning over,
each object distinct,
labeled.
An X is a wild card as in
CXK,
unlabeled
necklace
transforms.
AIK is the transform
INVERT.
EGK is the transform
WEIGH.
EIJ is the transform
EXP.
EIK is the transform
EULER.
There are 5×4×2=40 of these transforms.
However, the AHX and EHX transforms
are redundant, leaving 36. Four of them are named. As far as
I know, the other 32 are not.
The new and old sequence listed illustrate the 32 new transforms.
Terminology:
- XXXk means the transform XXX with exactly k boxes.
These are denoted by XXX[k] in the
On-Line Encyclopedia of Integer Sequences.
AIK2 is the transform
CONV.
- Bracelet means necklace that can be turned over.
More information about necklaces.
- Compound windmill is a rooted planar tree where the sub-rooted tree
extending from a node can be rotated independently of the rest of
the tree. Much like some children's toys or carnival rides. Compound windmills
can be dyslexic.
- Dyslexic planar tree is a planar tree where each sub-rooted
tree extending from a node can be read from left to right or right to
left. It can be thought of as viewed by an observer who does not
know left from right or as sub-rooted trees that can be turned
around independent of the rest of the tree.
- Eigensequence
means a sequence that is stable under a given transform or is modified in
some simple way. Eigensequences are covered in detail in:
M. Bernstein & N. J. A. Sloane,
Some canonical sequences of integers,
Linear Algebra and its Applications, 226-228 (1995), 57-72.
A000081,
rooted trees, 1,1,2,4,9,20,48,115... is an eigensequence of the transform
EULER.
because the transformed sequence, 1,2,4,9,20,48,115,286,..., is
the original sequence shifted left one place.
- Identity bracelet means bracelet where every bead is distinguished
by position and color, i.e. a bracelet generated by the transform DHK.
Part 2: Algorithms
an is the input sequence.
bn is the output sequence.
A(x) is the generating function of an.
B(x) is the generating function of bn.
(XXX a)n =
sum{k=1 to n} (XXXk a)n
MÖBIUS · XXX refers to the Möbius
transform of the sequence
transformed by XXX. Similarly for
MÖBIUS-1 · XXX.
However, (MÖBIUS · XXX)k
and (MÖBIUS-1 · XXX)k
are defined as follows:
(MÖBIUS · XXX)kan =
sum{d|k and d|n} (µ(d) × XXXk/dan/d)
(MÖBIUS-1 · XXX)kan =
sum{d|k and d|n} (XXXk/dan/d)
AIK = INVERT
B(x) = A(x) / (1-A(x))
AIKk
B(x) = A(x)k
LPALk (Linear palindrome)
If n, k even:
bn = (AIKk/2a)n/2
If n odd, k even:
bn = 0
If n even, k odd:
bn = sum{i>0 and i<n/2}
(a2i × (AIK(k-1)/2a)n/2-i)
if n,k odd:
bn = sum{i>0 and i<n/2}
(a2i-1 × (AIK(k-1)/2a)(n+1)/2-i)
BIKk
bn = ((AIKka)n +
(LPALka)n) / 2
BHKk
k=1:
bn = an
k>1:
bn = ((AIKka)n -
(LPALka)n) / 2
CHKk
bn = (MÖBIUS · AIK)kan / n
CIK
CIK = MÖBIUS-1 · CHK
CPALk (Circular palindrome)
CPAL1 = IDENTITY
CPAL2 = CIK2
k>2:
If n, k even:
bn = (I+J)/2+K+L+M where:
(No boxes joined)
I=(AIKk/2a)n/2
(2 boxes joined are identical)
J=sum{i=1 to n/2}(AIKk/2-1a)(n-2i)/2
(2 boxes joined are even and different sizes)
K=sum{i,j even, j>i, i+j<n}
(ai × aj ×
(AIKk/2-1a)(n-i-j)/2)
(2 boxes joined are odd and different sizes)
L=sum{i,j odd, j>i, i+j<n}
(ai × aj ×
(AIKk/2-1a)(n-i-j)/2)
(2 boxes joined are the same size and different colors)
M=sum{i>0 and i<n/2}
((ai2-ai)/2 ×
(AIKk/2-1a)(n-2i)/2)
If n odd, k even:
bn = sum{i odd, j even, i+j<n}
(ai × aj ×
((AIKk/2-1a)(n-i-j)/2)
If n even, k odd:
bn = sum{i>0 and i<n/2}
(a2i × (AIK(k-1)/2a)n/2-i)
if n,k odd:
bn = sum{i>0 and i<n/2}
(a2i-1 × (AIK(k-1)/2a)(n+1)/2-i)
DIKk
bn =
((CIKka)n +
(CPALka)n) / 2
DHKk
DHK1 = IDENTITY
DHK2 = CHK2
For k>2:
DHKk = (MÖBIUS ·
(CIK - CPAL)/2)k
If EXX is one of: {EFJ, EFK, EGJ, EGK,
EIJ} then:
AXXk = k! × EXXk
BXXk = max(1,k!/2) × EXXk
CXXk = (k-1!) × EXXk
DXXk = max(1,(k-1)!/2) × EXXk
To calculate (EFXka)n, enumerate
the distinct partitions of n into k parts as terms of the following form:
p1+p2+...+pk
Sum the terms calculated as follows:
EFJk:
prod{i=1 to k}api × n! /
prod{i=1 to k}pi!
EFKk:
prod{i=1 to k}api
EFK can also be calculated as:
B(x)=prod{k=1 to infinity}(1+akxk).
To calculate (AIJka)n,
(BHJka)n,
(CHJka)n or
(EGXka)n, enumerate the partitions of
of n into k parts as terms of the following form:
p1q1+p2q2+...+pjqj
where all the pi's are distinct.
Sum the terms calculated as follows:
AIJk:
prod{i=1 to j}apiqi
× n! × k! /
((prod{i=1 to j}pi!qi) ×
(prod{i=1 to j}qi!))
BHJk:
term1 =
prod{i=1 to j}apiqi
× k! /
(prod{i=1 to j}qi!)
term2 =
prod{i=1 to j}api[qi/2]
× [k/2]! /
(prod{i=1 to j}[qi/2]!)
If more than 1 qi is odd: term3 = term1
otherwise: term3 = term1 - term2
term = term3 × n! /
prod{i=1 to j}pi!qi / 2
CHJk:
term2 =
sum{d|qm for all m} (µ(d) ×
prod{i=1 to j}api[qi/d]
× [k/d]! /
(prod{i=1 to j}[qi/d]!))
term = term2 × n! /
prod{i=1 to j}pi!qi / k
EGJk:
prod{i=1 to j}C(api,qi) × n! /
prod{i=1 to j}pi!qi
EGKk:
prod{i=1 to j}C(api,qi)
DHJ:
Work is in progress.
Part 3: Catalogue of sequences
This table identifies a formula for each sequence,
usually based on one of the transforms.
This should provide a convenient way to browse the
sequences and see how the transforms apply to a broad class of
mathematics.
The base sequences:
These transforms have been applied to one of the base sequences
defined in the following table or to sequences in the
On-line Encyclopedia of Integer Sequences,
identified by number.
s1, s2, s3...
|
sk1 = k, skn=0 for n>1
|
all1, all2, all3,...
|
allkn = k for all n
|
codd (characteristic of odd)
|
coddn = 1 if n is odd, 0 otherwise
|
noone
|
noone1=0, noonen=1 for n>1
|
twoone
|
twoone1=2, twoonen=1 for n>1
|
iden
|
idenn=n
|
odd
|
oddn=2n-1
|
even
|
evenn=2n
|
If T is a transform:
Left(n;k1, k2,..., kn)T
is the
eigensequence
that shifts left n places
under T and has ai=ki
for 1<=i<=n.
M2(n)T is the
eigensequence
that doubles the terms whose indices
are greater than 1 under T.
AFJ sequences
AFK sequences
AGJ sequences
AGK sequences
AIJ sequences
BFJ sequences
BFK sequences
BGJ sequences
BGK sequences
BHJ sequences
BHK sequences
BIJ sequences
BIK sequences
CFJ sequences
CFK sequences
CGJ sequences
CGK sequences
CHJ sequences
CHK sequences
CIJ sequences
CIK sequences
DFJ sequences
DFK sequences
DGJ sequences
DGK sequences
DHJ sequences
DHK sequences
DIJ sequences
DIK sequences
EFJ sequences
EFK sequences
EGJ sequences
|