This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia 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. 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.

• Bracelet means necklace that can be turned over.

• 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
 A032000 AFJ all2 A032001 AFJ twoone A032002 AFJ iden A032003 AFJ odd A032004 Left(1;1)AFJ

AFK sequences
 A032005 AFK all2 A032006 AFK twoone A032007 AFK iden A032008 AFK odd A032009 Left(1;1)AFK A032010 (CFK A032009 )n-1

AGJ sequences
 A032011 AGJ all1 A032012 AGJ codd A032013 AGJ noone A032014 AGJ all2 A032015 AGJ twoone A032016 AGJ iden A032017 AGJ odd A032018 Left(1;1)AGJ A032019 M2(2)AGJ

AGK sequences
 A032020 AGK all1 A032021 AGK codd A032022 AGK noone A032023 AGK all2 A032024 AGK twoone A032025 AGK iden A032026 AGK odd A032027 Left(1;1)AGK A032028 (CGK A032027 )n-1 A032029 Left(2;1,1)AGK A032030 M2(2)AGK

AIJ sequences
 A000142 AIJ s1 A000165 AIJ s2 A032031 AIJ s3 A000670 AIJ all1 A000918 AIJ2 all1 A001117 AIJ3 all1 A000919 AIJ4 all1 A001118 AIJ5 all1 A000920 AIJ6 all1 A006154 AIJ codd A032032 AIJ noone A004123 AIJ all2 A006155 AIJ twoone A032033 AIJ all3 A006153 AIJ iden A000354 AIJ odd A001147 Left(1;1)AIJ A032034 Left(1;2)AIJ A032035 Left(2;1,1)AIJ A032036 Left(3;1,1,1)AIJ A032037 M2(1)AIJ

BFJ sequences
 A032038 BFJ all2 A032039 BFJ twoone A032040 BFJ iden A032041 BFJ odd A032042 Left(1;1)BFJ

BFK sequences
 A032043 BFK all2 A032044 BFK twoone A032045 BFK iden A032046 BFK odd A032047 Left(1;1)BFK A032048 (CFK A032047 )n-1

BGJ sequences
 A032049 BGJ all1 A032050 BGJ codd A032051 BGJ noone A032052 BGJ all2 A032053 BGJ twoone A032054 BGJ iden A032055 BGJ odd A032056 Left(1;1)BGJ A032057 M2(2)BGJ

BGK sequences
 A032058 BGK all1 A032059 BGK codd A032060 BGK noone A032061 BGK all2 A032062 BGK twoone A032063 BGK iden A032064 BGK odd A032065 Left(1;1)BGK A032066 (CGK A032065 )n-1 A032067 Left(2;1,1)BGK A032068 M2(2)BGK

BHJ sequences
 A032069 BHJ s2 A032070 BHJ s3 A032071 BHJ s4 A032072 BHJ s5 A032073 BHJ all1 A032074 BHJ codd A032075 BHJ noone A032076 BHJ all2 A032077 BHJ twoone A032078 BHJ all3 A032079 BHJ iden A032080 BHJ odd A032081 Left(1;1)BHJ A032082 Left(1;2)BHJ A032083 Left(2;1,1)BHJ A032084 M2(2)BHJ

BHK sequences
 A032085 BHK s2 A032086 BHK s3 A032087 BHK s4 A032088 BHK s5 A032089 BHK codd A032090 BHK noone A002620 (BHK3 all1)n+2 A006584 (BHK4 all1)n+2 A032091 BHK5 all1 A032092 BHK6 all1 A032093 BHK7 all1 A032094 BHK8 all1 A032095 (BHKn all1)2n-1 A032096 BHK all2 A032097 BHK twoone A032098 BHK all3 A032099 BHK iden A032100 BHK odd A032101 Left(1;1)BHK A032102 (DHK A032101 )n-1 A032103 Left(1;2)BHK A032104 Left(1;1,1)BHK A032105 M2(2)BHK A032106 (BHKn all1)2n

BIJ sequences
 A001710 BIJ s1 A032107 BIJ s2 A032108 BIJ s3 A032109 BIJ all1 A009568 (-1)n+1 × BIJ codd A032110 BIJ noone A032111 BIJ all2 A032112 BIJ twoone A032113 BIJ all3 A032114 BIJ iden A032115 BIJ odd A032116 Left(1;1)BIJ A032117 Left(1;2)BIJ A032118 Left(2;1,1)BIJ A032119 M2(1)BIJ

BIK sequences
 A005418 (BIK s2)n-1 A005418 BIK all1 A032120 BIK s3 A032121 BIK s4 A032122 BIK s5 A001224 (BIK codd)n+1 A001224 (BIK noone)n+2 A002620 (BIK3 all1)n+1 A005993 (BIK4 all1)n+4 A005994 (BIK5 all1)n+5 A005995 (BIK6 all1)n+6 A018210 (BIK7 all1)n+7 A018211 (BIK8 all1)n+8 A018212 (BIK9 all1)n+9 A018213 (BIK10 all1)n+10 A018214 (BIK11 all1)n+11 A032123 (BIKn all1)2n-1 A005654 (BIKn all1)2n A005656 (BIKn-3 all1)2n-3 A032124 BIK all2 A032125 BIK all3 A005207 BIK twoone A032126 BIK iden A032127 BIK odd A032128 Left(1;1)BIK A032129 (DIK A032128 )n-1 A032130 Left(1;2)BIK A032131 Left(2;1,1)BIK A032132 M2(1)BIK A032133 M2(2)BIK

CFJ sequences
 A032134 CFJ all2 A032135 CFJ twoone A032136 CFJ iden A032137 CFJ odd A032138 Left(1;1)CFJ

CFK sequences
 A032139 CFK all2 A032140 CFK twoone A032141 CFK iden A032142 CFK odd A032143 Left(1;1)CFK

CGJ sequences
 A032144 CGJ all1 A032145 CGJ codd A032146 CGJ noone A032147 CGJ all2 A032148 CGJ twoone A032149 CGJ iden A032150 CGJ odd A032151 Left(1;1)CGJ A032152 M2(2)CGJ

CGK sequences
 A032153 CGK all1 A032154 CGK codd A032155 CGK noone A032156 CGK all2 A032157 CGK twoone A032158 CGK iden A032159 CGK odd A032160 Left(1;1)CGK A032161 Left(1;2)CGK A032162 Left(2;1,1)CGK A032163 M2(2)CGK

CHJ sequences
 A032321 CHJ s2 A032322 CHJ s3 A032323 CHJ s4 A032324 CHJ s5 A032325 CHJ all1 A032326 CHJ codd A032327 CHJ noone A032328 CHJ all2 A032329 CHJ twoone A032330 CHJ all3 A032331 CHJ iden A032332 CHJ odd A032333 Left(1;1)CHJ A032334 Left(1;2)CHJ A032335 Left(2;1,1)CHJ A032336 M2(2)CHJ

CHK sequences
 A001037 CHK s2 A001037 (CHK all1) + s1 A027376 CHK s3 A027376 (CHK all2) + s1 A027376 (CHK odd) + s2 A027377 CHK s4 A027377 (CHK all3) + s1 A001692 CHK s5 A027378 CHK s5 A032164 CHK s6 A001693 CHK s7 A027379 CHK s7 A027380 CHK s8 A027381 CHK s9 A032165 CHK s10 A032166 CHK s11 A032167 CHK s12 A006206 (CHK codd) + CHAR({2}) A006206 (CHK noone) + s1 A001840 (CHK3 all1)n+4 A006918 (CHK4 all1)n+4 A011795 (CHK5 all1)n+1 A011796 (CHK6 all1)n+6 A011797 (CHK7 all1)n+1 A031164 (CHK8 all1)n+9 A011845 CHK9 all1 A032168 CHK10 all1 A032169 CHK11 all1 A000108 (CHKn+1 all1)2n+1 A022553 (CHKn+1 all1)2n+2 A022553 (CHK A000108 )n-1 A032170 CHK iden A032170 CHK twoone + s1 A032171 Left(1;1)CHK A032172 Left(1;2)CHK A032173 Left(2;1,1)CHK A032174 M2(2)CHK A032175 CHK A004111 A032176 WEIGH A032175 A032177 A032176 - A004111 A032178 WEIGH A032177

CIJ sequences
 A000142 (CIJ s1)n+1 A000165 (CIJ s2)n+1 × 2 A032179 CIJ s3 A000629 CIJ all1 A000225 (CIJ2 all1)n+1 A028243 CIJ3 all1 A028244 CIJ4 all1 A028245 CIJ5 all1 A032180 CIJ6 all1 A003704 (-1)n+1 × (CIJ codd) A032181 CIJ noone A027882 CIJ all2 A032182 CIJ twoone A032183 CIJ all3 A009444 (-1)n+1 × (CIJ iden) A032184 CIJ odd A029768 Left(1;1)CIJ A032185 Left(1;2)CIJ A032186 Left(2;1,1)CIJ A032187 Left(3;1,1,1)CIJ A032188 M2(1)CIJ

CIK sequences
 A000031 CIK s2 A000031 (CIK all1) + all1 A008965 CIK all1 A008965 (CIK s2) - all1 A001867 CIK s3 A001867 (CIK all2) + all1 A001868 CIK s4 A001868 (CIK all3) + all1 A001869 CIK s5 A001869 (CIK all4) + all1 A032189 CIK codd A032190 CIK noone A000358 (CIK noone) + all1 A007997 (CIK3 all1)n+3 A008610 (CIK4 all1)n+4 A008646 (CIK5 all1)n+5 A032191 CIK6 all1 A032192 CIK7 all1 A032193 CIK8 all1 A032194 CIK9 all1 A032195 CIK10 all1 A032196 CIK11 all1 A032197 CIK12 all1 A000108 (CHKn+1 all1)2n+1 A003239 (CIKn-1 all1)2n-2 A003239 (CIK A000108 n-1)n-1 A005594 CIK twoone A032198 CIK iden A032199 CIK odd A032200 Left(1;1)CIK A032201 Left(1;2)CIK A032202 Left(2;1,1)CIK A032203 M2(1)CIK A032204 M2(2)CIK A002861 CIK A000081 A027852 CIK2 A000081 A029852 CIK3 A000081 A029853 CIK4 A000081 A029868 CIK5 A000081 A029869 CIK6 A000081 A029870 CIK7 A000081 A029871 CIK8 A000081 A032205 CIK9 A000081 A032206 CIK10 A000081 A032207 CIK11 A000081 A032208 CIK12 A000081

DFJ sequences
 A032209 DFJ all2 A032210 DFJ twoone A032211 DFJ iden A032212 DFJ odd A032213 Left(1;1)DFJ

DFK sequences
 A032214 DFK all2 A032215 DFK twoone A032216 DFK iden A032217 DFK odd A032218 Left(1;1)DFK

DGJ sequences
 A032219 DGJ all1 A032220 DGJ codd A032221 DGJ noone A032222 DGJ all2 A032223 DGJ twoone A032224 DGJ iden A032225 DGJ odd A032226 Left(1;1)DGJ A032227 M2(2)DGJ

DGK sequences
 A032228 DGK all1 A032229 DGK codd A032230 DGK noone A032231 DGK all2 A032232 DGK twoone A032233 DGK iden A032234 DGK odd A032235 Left(1;1)DGK A032236 Left(1;2)DGK A032237 Left(2;1,1)DGK A032238 M2(2)DGK

DHJ sequences
 A032337 DHJ s2 A032338 DHJ s3 A032339 DHJ s4 A032340 DHJ s5

DHK sequences
 A032239 DHK s2 A032240 DHK s3 A032241 DHK s4 A032242 DHK s5 A032243 DHK codd A032244 DHK noone A032245 DHK all1 A001399 (DHK3 all1)n+6 A018845 (DHK3 all1)n+6 A026809 (DHK3 all1)n+3 A008804 (DHK4 all1)n+7 A032246 DHK5 all1 A032247 DHK6 all1 A032248 DHK7 all1 A032249 DHK8 all1 A032250 (DHKn all1)2n A032251 DHK all2 A032252 DHK twoone A032253 DHK all3 A032254 DHK iden A032255 DHK odd A032256 Left(1;1)DHK A032257 Left(1;2)DHK A032258 Left(2;1,1)DHK A032259 M2(2)DHK A032260 (DHKn all1)2n-1

DIJ sequences
 A001710 (DIJ s1)n+1 A000165 (DIJ s2)n+1 - s2 A032261 DIJ s3 A032262 DIJ all1 A000225 (DIJ2 all1)n+1 A000392 DIJ3 all1 A032263 DIJ4 all1 A032264 DIJ codd A032265 DIJ noone A032266 DIJ all2 A032267 DIJ twoone A032268 DIJ all3 A032269 DIJ iden A032270 DIJ odd A032271 Left(1;1)DIJ A032272 Left(1;2)DIJ A032273 Left(2;1,1)DIJ A032274 M2(1)DIJ

DIK sequences
 A000029 DIK s2 A000029 (DIK all1) + all1 A027671 DIK s3 A032275 DIK s4 A032276 DIK s5 A032277 DIK codd A032278 DIK noone A001399 (DIK3 all1)n+3 A018845 (DIK3 all1)n+3 A026809 DIK3 all1 A005232 DIK4 all1 A032279 DIK5 all1 A005513 DIK6 all1 A032280 DIK7 all1 A005514 DIK8 all1 A032281 DIK9 all1 A005515 DIK10 all1 A032282 DIK11 all1 A005516 DIK12 all1 A005648 (DIKn all1)2n A007123 (DIKn all1)2n-1 A032283 DIK all2 A032284 DIK all3 A032285 DIK all4 A032286 DIK all5 A005595 DIK twoone A032287 DIK iden A032288 DIK odd A032289 Left(1;1)DIK A032290 Left(1;2)DIK A032291 Left(2;1,1)DIK A032292 M2(1)DIK A032293 M2(2)DIK A001371 MÖBIUS A000029 A032294 MÖBIUS A027671 A032295 MÖBIUS A032275 A032296 MÖBIUS A032276

EFJ sequences
 A032297 EFJ all2 A032298 EFJ twoone A032299 EFJ iden A032300 EFJ odd A032301 Left(1;1)EFJ

EFK sequences
 A032302 EFK all2 A032303 EFK twoone A022629 EFK iden A032304 EFK odd A032305 Left(1;1)EFK A032306 Left(1;2)EFK A032307 Left(2;1,1)EFK A032308 EFK all3 A032309 EFK even

EGJ sequences
 A007837 EGJ all1 A032310 EGJ codd A032311 EGJ noone A032312 EGJ all2 A032313 EGJ twone A032314 EGJ all3 A032315 EGJ iden A032316 EGJ odd A032317 Left(1;1)EGJ A032318 Left(1;2)EGJ A032319 Left(2;1,1)EGJ A032320 M2(2)EGJ

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 23 07:11 EDT 2019. Contains 328336 sequences. (Running on oeis4.)