login

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

  1. Definition.
  2. Algorithms.
  3. Catalogue of Sequences.
  4. 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.

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:


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