This site is supported by donations to The OEIS Foundation.

# 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, maintained by N. J. A. Sloane.

File:BluePinLeft.gif 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.

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.

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

 AFJ all2 AFJ twoone AFJ iden AFJ odd Left(1;1)AFJ

AFK sequences

 AFK all2 AFK twoone AFK iden AFK odd Left(1;1)AFK (CFK A032009 )n-1

AGJ sequences

 AGJ all1 AGJ codd AGJ noone AGJ all2 AGJ twoone AGJ iden AGJ odd Left(1;1)AGJ M2(2)AGJ

AGK sequences

 AGK all1 AGK codd AGK noone AGK all2 AGK twoone AGK iden AGK odd Left(1;1)AGK (CGK A032027 )n-1 Left(2;1,1)AGK M2(2)AGK

AIJ sequences

 AIJ s1 AIJ s2 AIJ s3 AIJ all1 AIJ2 all1 AIJ3 all1 AIJ4 all1 AIJ5 all1 AIJ6 all1 AIJ codd AIJ noone AIJ all2 AIJ twoone AIJ all3 AIJ iden AIJ odd Left(1;1)AIJ Left(1;2)AIJ Left(2;1,1)AIJ Left(3;1,1,1)AIJ M2(1)AIJ

BFJ sequences

 BFJ all2 BFJ twoone BFJ iden BFJ odd Left(1;1)BFJ

BFK sequences

 BFK all2 BFK twoone BFK iden BFK odd Left(1;1)BFK (CFK A032047 )n-1

BGJ sequences

 BGJ all1 BGJ codd BGJ noone BGJ all2 BGJ twoone BGJ iden BGJ odd Left(1;1)BGJ M2(2)BGJ

BGK sequences

 BGK all1 BGK codd BGK noone BGK all2 BGK twoone BGK iden BGK odd Left(1;1)BGK (CGK A032065 )n-1 Left(2;1,1)BGK M2(2)BGK

BHJ sequences

 BHJ s2 BHJ s3 BHJ s4 BHJ s5 BHJ all1 BHJ codd BHJ noone BHJ all2 BHJ twoone BHJ all3 BHJ iden BHJ odd Left(1;1)BHJ Left(1;2)BHJ Left(2;1,1)BHJ M2(2)BHJ

BHK sequences

 BHK s2 BHK s3 BHK s4 BHK s5 BHK codd BHK noone (BHK3 all1)n+2 (BHK4 all1)n+2 BHK5 all1 BHK6 all1 BHK7 all1 BHK8 all1 (BHKn all1)2n-1 BHK all2 BHK twoone BHK all3 BHK iden BHK odd Left(1;1)BHK (DHK A032101 )n-1 Left(1;2)BHK Left(1;1,1)BHK M2(2)BHK (BHKn all1)2n

BIJ sequences

 BIJ s1 BIJ s2 BIJ s3 BIJ all1 (-1)n+1 × BIJ codd BIJ noone BIJ all2 BIJ twoone BIJ all3 BIJ iden BIJ odd Left(1;1)BIJ Left(1;2)BIJ Left(2;1,1)BIJ M2(1)BIJ

BIK sequences

 (BIK s2)n-1 BIK all1 BIK s3 BIK s4 BIK s5 (BIK codd)n+1 (BIK noone)n+2 (BIK3 all1)n+1 (BIK4 all1)n+4 (BIK5 all1)n+5 (BIK6 all1)n+6 (BIK7 all1)n+7 (BIK8 all1)n+8 (BIK9 all1)n+9 (BIK10 all1)n+10 (BIK11 all1)n+11 (BIKn all1)2n-1 (BIKn all1)2n (BIKn-3 all1)2n-3 BIK all2 BIK all3 BIK twoone BIK iden BIK odd Left(1;1)BIK (DIK A032128 )n-1 Left(1;2)BIK Left(2;1,1)BIK M2(1)BIK M2(2)BIK

CFJ sequences

 CFJ all2 CFJ twoone CFJ iden CFJ odd Left(1;1)CFJ

CFK sequences

 CFK all2 CFK twoone CFK iden CFK odd Left(1;1)CFK

CGJ sequences

 CGJ all1 CGJ codd CGJ noone CGJ all2 CGJ twoone CGJ iden CGJ odd Left(1;1)CGJ M2(2)CGJ

CGK sequences

 CGK all1 CGK codd CGK noone CGK all2 CGK twoone CGK iden CGK odd Left(1;1)CGK Left(1;2)CGK Left(2;1,1)CGK M2(2)CGK

CHJ sequences

 CHJ s2 CHJ s3 CHJ s4 CHJ s5 CHJ all1 CHJ codd CHJ noone CHJ all2 CHJ twoone CHJ all3 CHJ iden CHJ odd Left(1;1)CHJ Left(1;2)CHJ Left(2;1,1)CHJ M2(2)CHJ

CHK sequences

 CHK s2 (CHK all1) + s1 CHK s3 (CHK all2) + s1 (CHK odd) + s2 CHK s4 (CHK all3) + s1 CHK s5 CHK s5 CHK s6 CHK s7 CHK s7 CHK s8 CHK s9 CHK s10 CHK s11 CHK s12 (CHK codd) + CHAR({2}) (CHK noone) + s1 (CHK3 all1)n+4 (CHK4 all1)n+4 (CHK5 all1)n+1 (CHK6 all1)n+6 (CHK7 all1)n+1 (CHK8 all1)n+9 CHK9 all1 CHK10 all1 CHK11 all1 (CHKn+1 all1)2n+1 (CHKn+1 all1)2n+2 (CHK A000108 )n-1 CHK iden CHK twoone + s1 Left(1;1)CHK Left(1;2)CHK Left(2;1,1)CHK M2(2)CHK CHK A004111 WEIGH A032175 WEIGH A032177

CIJ sequences

 (CIJ s1)n+1 (CIJ s2)n+1 × 2 CIJ s3 CIJ all1 (CIJ2 all1)n+1 CIJ3 all1 CIJ4 all1 CIJ5 all1 CIJ6 all1 (-1)n+1 × (CIJ codd) CIJ noone CIJ all2 CIJ twoone CIJ all3 (-1)n+1 × (CIJ iden) CIJ odd Left(1;1)CIJ Left(1;2)CIJ Left(2;1,1)CIJ Left(3;1,1,1)CIJ M2(1)CIJ

CIK sequences

 CIK s2 (CIK all1) + all1 CIK all1 (CIK s2) - all1 CIK s3 (CIK all2) + all1 CIK s4 (CIK all3) + all1 CIK s5 (CIK all4) + all1 CIK codd CIK noone (CIK noone) + all1 (CIK3 all1)n+3 (CIK4 all1)n+4 (CIK5 all1)n+5 CIK6 all1 CIK7 all1 CIK8 all1 CIK9 all1 CIK10 all1 CIK11 all1 CIK12 all1 (CHKn+1 all1)2n+1 (CIKn-1 all1)2n-2 (CIK A000108 n-1)n-1 CIK twoone CIK iden CIK odd Left(1;1)CIK Left(1;2)CIK Left(2;1,1)CIK M2(1)CIK M2(2)CIK CIK A000081 CIK2 A000081 CIK3 A000081 CIK4 A000081 CIK5 A000081 CIK6 A000081 CIK7 A000081 CIK8 A000081 CIK9 A000081 CIK10 A000081 CIK11 A000081 CIK12 A000081

DFJ sequences

 DFJ all2 DFJ twoone DFJ iden DFJ odd Left(1;1)DFJ

DFK sequences

 DFK all2 DFK twoone DFK iden DFK odd Left(1;1)DFK

DGJ sequences

 DGJ all1 DGJ codd DGJ noone DGJ all2 DGJ twoone DGJ iden DGJ odd Left(1;1)DGJ M2(2)DGJ

DGK sequences

 DGK all1 DGK codd DGK noone DGK all2 DGK twoone DGK iden DGK odd Left(1;1)DGK Left(1;2)DGK Left(2;1,1)DGK M2(2)DGK

DHJ sequences

 DHJ s2 DHJ s3 DHJ s4 DHJ s5

DHK sequences

 DHK s2 DHK s3 DHK s4 DHK s5 DHK codd DHK noone DHK all1 (DHK3 all1)n+6 (DHK3 all1)n+6 (DHK3 all1)n+3 (DHK4 all1)n+7 DHK5 all1 DHK6 all1 DHK7 all1 DHK8 all1 (DHKn all1)2n DHK all2 DHK twoone DHK all3 DHK iden DHK odd Left(1;1)DHK Left(1;2)DHK Left(2;1,1)DHK M2(2)DHK (DHKn all1)2n-1

DIJ sequences

 (DIJ s1)n+1 (DIJ s2)n+1 - s2 DIJ s3 DIJ all1 (DIJ2 all1)n+1 DIJ3 all1 DIJ4 all1 DIJ codd DIJ noone DIJ all2 DIJ twoone DIJ all3 DIJ iden DIJ odd Left(1;1)DIJ Left(1;2)DIJ Left(2;1,1)DIJ M2(1)DIJ

DIK sequences

 DIK s2 (DIK all1) + all1 DIK s3 DIK s4 DIK s5 DIK codd DIK noone (DIK3 all1)n+3 (DIK3 all1)n+3 DIK3 all1 DIK4 all1 DIK5 all1 DIK6 all1 DIK7 all1 DIK8 all1 DIK9 all1 DIK10 all1 DIK11 all1 DIK12 all1 (DIKn all1)2n (DIKn all1)2n-1 DIK all2 DIK all3 DIK all4 DIK all5 DIK twoone DIK iden DIK odd Left(1;1)DIK Left(1;2)DIK Left(2;1,1)DIK M2(1)DIK M2(2)DIK MÖBIUS A000029 MÖBIUS A027671 MÖBIUS A032275 MÖBIUS A032276

EFJ sequences

 EFJ all2 EFJ twoone EFJ iden EFJ odd Left(1;1)EFJ

EFK sequences

 EFK all2 EFK twoone EFK iden EFK odd Left(1;1)EFK Left(1;2)EFK Left(2;1,1)EFK EFK all3 EFK even

EGJ sequences

 EGJ all1 EGJ codd EGJ noone EGJ all2 EGJ twone EGJ all3 EGJ iden EGJ odd Left(1;1)EGJ Left(1;2)EGJ Left(2;1,1)EGJ M2(2)EGJ