[seqfan] A better solution to Wouter's problem

[Olivier Gerard]

[owner's note: due to a glitch, I send it myself, but the message
is from "Christian G.Bower" <bowerc at usa.net> ]


If you shift the Catalan numbers (A000108, M1459, N0577) right two
places so that you get (starting at index 0)

0 0 1 1 2 5 42 132...

and take the Invert transform, you get:

0 0 1 1 3 7 20 59 184 593...

Wouter's sequence shifted right 2 places.

For a combinatorial interpretation:

Number of linear forests of planted planar trees of n nodes.

(This time we count the roots as nodes.)

By "linear forest" I mean a union of trees ordered in a line from
start to finish. This can also be viewed as a forest where the
trees are labeled, but the nodes are unlabeled.

Simple, not contrived, and I can't believe I didn't see it the first time!

I also have some more general results about shallow diagonals.

If the Catalan triangle is viewed this way (in reverse of the
way Wouter presented it):

 k     1    2    3    4    5   6   7  8 9 10
n
 1     1
 2     1    1
 3     2    2    1
 4    $5    5    3   *1
 5    14   14  $*9    4    1
 6    42  *42   28   14   $5   1
 7 +*132 +132  +90  +48  +20  +6 $+1
 8   429  429  297  165   75  27   7  1
 9  1430 1430 1001  572  275 110  35  8 1
10  4862 4862 3432 2002 1001 429 154 44 9 1

then a(n,k) is the number of linear forests of k planted planar trees
and n non-root nodes.

If I sum across the table (i.e. the +'s) I get the number of
linear forests of planted planar trees having n non-root nodes.

If I sum in a shallow diagonals (i.e. the *'s) I am allowed
one less node for every additional tree. This can be viewed as
counting the nodes and counting the trees together. Such as you
have n dollars to spend and each tree costs 1 + the number of
nodes. In this case, since I deleted the non-root nodes, the
easiest solution is to count the roots again. This method
can be applied to any triangle that represents the number of
ways to have n things in k parts.

If I sum the other shallow diagonal (i.e. the $'s) I am allowed
one more node for each additional tree, or I pay more for
bigger trees. This would be like paying 2k-1 dollars for a
tree with k nodes having n dollars to spend.

Since the Invert transform was used to attain the Catalan triangle,
it can also be used in the calculation of the shallow diagonals.

In the "*" diagonal case, the increased cost of more trees can be
modeled by shifting the base sequence (in this case, the Catalan
numbers already shifted one place right) one place right and applying
the (Invert) transform.

In the "$" diagonal case, the increased cost of larger trees can
be modeled by "stretching out" the base sequence so that 1 is mapped
to 1, 2 to 3, 3 to 5, k to 2k-1.

Indeed the $ diagonal sum, 1,1,2,3,6,10,20,35...
A001405, M0769, N0294 C(n,[n/2]) is the Invert transform of
(starting at 0)
0 1 0 1 0 2 0 5 0 14 0 42 0...
a "stretched out" Catalan numbers.

These arguments also work with the Pascal's triangle example.

Pascal's triangle can be derived from the Invert transform of the
"all ones" sequence in much the same way as the Catalan triangle
can be derived from the Invert transform of the Catalan numbers.

Therefore you should not be surprised to know that the Invert
transform
of 0 0 1 1 1 1 1... is 0 0 1 1 2 3 5 8 13... the twice shifted right
Fibonacci numbers and the Invert transform of
0 1 0 1 0 1 0 1 (the characteristic of the odds) is
0 1 1 2 3 5 8 13 21... the once right shifted Fibonacci numbers.

I applied this technique to a couple of triangles derived from
the Euler transform.

The partition triangle: (ways to partition n into k parts)

1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 9 7 5 3 2 1 1

Has shallow diagonal 1 1 2 2 4 4 7 8 12 14 21 24...
A002865 (M0309, N0113) Partitions of n with no part of size 1.

and other shallow diagonal 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27...
A000009 (M0281, N0100) Partitions of n into distinct parts or
Partitions of n into odd parts.

The rooted tree triangle: (forests of k rooted trees and n nodes)
  1
  1   1
  2   1   1
  4   3   1  1
  9   6   3  1  1
 20  16   7  3  1 1
 48  37  18  7  3 1 1
115  96  44 19  7 3 1 1
286 239 117 46 19 7 3 1 1

Has shallow diagonal 1 1 3 5 13 27 68 160 404 1010...
A005198 (M2491) Forests of planted trees.
And other shallow diagonal 1 1 2 2 4 5 9 11 21 28 50 68 123 173...
EULER transform of 1 0 1 0 4 0 9 0 20 0 48 0 115 0...
A "stretched out" version of rooted trees.

%S A038000 1,1,2,2,4,5,9,11,21,28,50,68,123,173,310,441,789,1147,2044,
%T A038000 2999,5351,7938,14143,21138,37686,56729,101144,153085,273077,
%U A038000 415407,741301,1132373,2021831,3100128,5537782,8519076,15225373
%N A038000 Forests of rooted trees where n dollars are spent and an n-node
tree costs 2n-1 dollars.

I took the Inverse Weigh transform of this and got a fractal sequence
Clark Kimberling would probably appreciate.

(1) <1> (1) [1] (2) <1> (4) 1 (9) <2> (20) [1] (48) <4> (115) 1 (286)
<9> (719) [2] (1842) <20> (4766) 1 (12486) <48> (32973) [4] (87811)

%S A038001 1,1,1,1,2,1,4,1,9,2,20,1,48,4,115,1,286,9,719,2,1842,20,4766,1,
%T A038001 12486,48,32973,4,87811,115,235381,1,634847,286,1721159,9,4688676,
%U A038001 719,12826228,2,35221832,1842,97055181,20,268282855,4766,74372498
%N A038001 A fractal sequence based on A000081.

Incidentally, would you believe Clark Kimberling's famous fractal
sequence A003602 (M0145) is the Inverse Weigh transform of the Euler
transform of (starting at 1) 1,0,2,0,3,0,4,0...

Try it.

Olivier pointed out some time ago, a sequence can unexpectedly
have a digit interpretation. Here's an example I ran into:

I was noticing how the Catalan numbers A000108 are usually even.
In fact, it appears that cat(n) is odd if and only if n+1 is a power of 2.

To confirm this observation, I considered the formula:
cat(n) = C(2n,n)/(n+1) and considered the problem:
What is the greatest n such that 2^n | C(2n,n)?

It turns out to be 1 1 2 1 2 2 3 1 2 2
A000120 (M0105, N0041) Number of 1's in binary expansion of n.

Well Wouter, thanks for an interesting problem.
(and I thought I was going take a break from this for a couple weeks.)

Christian