Thursday 22 August 2019

Binomial Transforms

My diurnal age today was 25706 and one of the properties of this number, as listed in the Online Encyclopaedia of Integer Sequences (OEIS), is that it belongs to OEIS A101509:  binomial transform of tau(n) (see A000005). Now \( \tau (n) \) is the divisor function and returns the number of divisors for any given number \(n\). OEIS A000005 gives the members of this sequence, beginning with \(n=1\):
1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 6, 6, 4, 8, 2, 10, 5, 4, 2, 12, 4, 4, 4, 8, 2, 12, 4, 6, 4, 4, 4, 12, 2, 6, 6, 9, 2, 8, 2, 8, ...
The binomial transform when applied to OEIS A000005 produces OEIS A101509:
1, 3, 7, 16, 35, 75, 159, 334, 696, 1442, 2976, 6123, 12562, 25706, 52492, 107014, 217877, 443061, 899957, 1826078, 3701783, 7498261, 15178255, 30706320, 62085915, 125465715, 253415981, 511608490, 1032427637, 2082680887, 4199956101, 8467124805, 17064784905, 34382825363, 69256687719, 139465867773, ...
As can be seen, the terms of the second sequence get large fairly quickly as each term in the first sequence is mapped an increasingly larger term in the second. In particular, the 13th term (2) in the first gets mapped to 25706 in the second. But what is a binomial transform?

To quote from Wikipedia:
In combinatorics, the binomial transform is a sequence transformation (i.e., a transform of a sequence) that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to the sequence associated with its ordinary generating function.

The binomial transform, \(T\), of a sequence, {\(a_n\)}, is the sequence {\(s_n\)} defined by:$$s_n = \sum_{k=0}^n {n\choose k} a_k$$ 
Figure 1 shows some SageMath code that accepts the terms of a sequence as input and outputs the terms arising from the binomial transform of the input terms:

Figure 1: source

Figure 2 shows the above code applied to two different sequences, firstly the sequence of divisors of the natural numbers and then the sequence consisting only of 1's.

Figure 2

I'd like to find some practical applications of binomial transforms and also investigate the Euler transform in more depth.

No comments:

Post a Comment