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 {a_n;n>=1} represents the number of colors a box holding n balls can be. The transformed sequence {b_n;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.

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.

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:

• XXX_k means the transform XXX with exactly k boxes.
  These are denoted by XXX[k] in the On-Line Encyclopedia of Integer Sequences.
  AIK₂ 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

a_n is the input sequence.

b_n is the output sequence.

A(x) is the generating function of a_n.

B(x) is the generating function of b_n.

(XXX a)_n = sum{k=1 to n} (XXX_k 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)_ka_n = sum{d|k and d|n} (µ(d) × XXX_k/da_n/d)

(MÖBIUS^-1 · XXX)_ka_n = sum{d|k and d|n} (XXX_k/da_n/d)

AIK = INVERT
B(x) = A(x) / (1-A(x))

AIK_k
B(x) = A(x)^k

LPAL_k (Linear palindrome)
If n, k even: b_n = (AIK_k/2a)_n/2
If n odd, k even: b_n = 0
If n even, k odd: b_n = sum{i>0 and i<n/2} (a_2i × (AIK_(k-1)/2a)_n/2-i)
if n,k odd: b_n = sum{i>0 and i<n/2} (a_2i-1 × (AIK_(k-1)/2a)_(n+1)/2-i)

BIK_k
b_n = ((AIK_ka)_n + (LPAL_ka)_n) / 2

BHK_k
k=1: b_n = a_n
k>1: b_n = ((AIK_ka)_n - (LPAL_ka)_n) / 2

CHK_k
b_n = (MÖBIUS · AIK)_ka_n / n

CIK
CIK = MÖBIUS^-1 · CHK

CPAL_k (Circular palindrome)
CPAL₁ = IDENTITY
CPAL₂ = CIK₂
k>2:
If n, k even: b_n = (I+J)/2+K+L+M where:
(No boxes joined)
I=(AIK_k/2a)_n/2
(2 boxes joined are identical)
J=sum{i=1 to n/2}(AIK_k/2-1a)_(n-2i)/2
(2 boxes joined are even and different sizes)
K=sum{i,j even, j>i, i+j<n} (a_i × a_j × (AIK_k/2-1a)_(n-i-j)/2)
(2 boxes joined are odd and different sizes)
L=sum{i,j odd, j>i, i+j<n} (a_i × a_j × (AIK_k/2-1a)_(n-i-j)/2)
(2 boxes joined are the same size and different colors)
M=sum{i>0 and i<n/2} ((a_i²-a_i)/2 × (AIK_k/2-1a)_(n-2i)/2)
If n odd, k even:
b_n = sum{i odd, j even, i+j<n} (a_i × a_j × ((AIK_k/2-1a)_(n-i-j)/2)
If n even, k odd:
b_n = sum{i>0 and i<n/2} (a_2i × (AIK_(k-1)/2a)_n/2-i)
if n,k odd:
b_n = sum{i>0 and i<n/2} (a_2i-1 × (AIK_(k-1)/2a)_(n+1)/2-i)

DIK_k
b_n = ((CIK_ka)_n + (CPAL_ka)_n) / 2

DHK_k
DHK₁ = IDENTITY
DHK₂ = CHK₂
For k>2:
DHK_k = (MÖBIUS · (CIK - CPAL)/2)_k

If EXX is one of: {EFJ, EFK, EGJ, EGK, EIJ} then:
AXX_k = k! × EXX_k
BXX_k = max(1,k!/2) × EXX_k
CXX_k = (k-1!) × EXX_k
DXX_k = max(1,(k-1)!/2) × EXX_k

To calculate (EFX_ka)_n, enumerate the distinct partitions of n into k parts as terms of the following form:
p₁+p₂+...+p_k
Sum the terms calculated as follows:
EFJ_k: prod{i=1 to k}a_pi × n! / prod{i=1 to k}p_i!
EFK_k: prod{i=1 to k}a_pi

EFK can also be calculated as:
B(x)=prod{k=1 to infinity}(1+a_kx^k).

To calculate (AIJ_ka)_n, (BHJ_ka)_n, (CHJ_ka)_n or (EGX_ka)_n, enumerate the partitions of of n into k parts as terms of the following form:
p₁q₁+p₂q₂+...+p_jq_j where all the p_i's are distinct.
Sum the terms calculated as follows:
AIJ_k: prod{i=1 to j}a_pi^q_i × n! × k! / ((prod{i=1 to j}p_i!q_i) × (prod{i=1 to j}q_i!))
BHJ_k:
term₁ = prod{i=1 to j}a_pi^q_i × k! / (prod{i=1 to j}q_i!)
term₂ = prod{i=1 to j}a_pi^[q_i/2] × [k/2]! / (prod{i=1 to j}[q_i/2]!)
If more than 1 q_i is odd: term₃ = term₁
otherwise: term₃ = term₁ - term₂
term = term₃ × n! / prod{i=1 to j}p_i!q_i / 2
CHJ_k:
term₂ = sum{d|q_m for all m} (µ(d) × prod{i=1 to j}a_pi^[q_i/d] × [k/d]! / (prod{i=1 to j}[q_i/d]!))
term = term₂ × n! / prod{i=1 to j}p_i!q_i / k
EGJ_k: prod{i=1 to j}C(a_pi,q_i) × n! / prod{i=1 to j}p_i!q_i
EGK_k: prod{i=1 to j}C(a_pi,q_i)

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.

If T is a transform:

Left(n;k₁, k₂,..., k_n)T is the eigensequence that shifts left n places under T and has a_i=k_i 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