This site is supported by donations to The OEIS Foundation.
More Transformations of Integer Sequences
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.
Table of Contents
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) B. Linear with turning over (reversible) C. Circular (necklace) D. Circular with turning over (bracelet) E. None (unordered) |
F. Size G. Element H. Identity I. None (indistinct) |
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 K. Unlabeled |
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
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 |