double enumeration

[George Beck]

Dear seqcomp members,

I wrote to Peter Luschny who invited me to join this group
and post this idea of double enumeration.

First let me introduce myself. I work for Wolfram Research
as the editor for The Mathematica Journal and technical
reviewer for the Demonstrations project,
http://demonstrations.wolfram.com. On the side I am an
amateur mathematician.

I recently wrote a demonstration
http://demonstrations.wolfram.com/EulerianNumbersVersusStirlingNumbersOfTheFirstKind/.
What I find most interesting here is the symmetry of the
first rows except one quarter of the time.

The idea of Eulerian Numbers versus Stirling Numbers of the
First Kind is that when something--n! in that case--can be
counted in two ways, make a matrix that counts the objects
in both ways. To be more specific (but still general!), say
we have a function f[n,k] that counts from n objects those
objects x for which ff[x] = k, and similarly for g. Then the
matrix fg[i, j] would count those objects x for which ff[x]
= i and gg[x] = j. The sum of the row sums will be equal to
the sum of the column sums.

I applied this idea to the number triangle A080510 and
Stirling numbers of the second kind, with sum of sums the
Bell numbers. (This was in analogy to partitions into k
parts or with maximum part k, which isn't so interesting
because the matrix is symmetric!) It seems again there is
some combinatorial significance: for instance, consider the
numbers along the diagonal from the bottom left entry to the
top right entry; those diagonals from a triangle with row
sums A000325 2^n - n. These matrices seem to have a lot of
arithmetic structure. For instance, look at
StirlingS2Square[11], which gives

{
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 462, 330, 165, 55, 11, 0},
{0, 0, 0, 5775, 12936, 6930, 2310, 495, 55, 0, 0},
{0, 0, 15400, 75075, 41580, 11550, 1980, 165, 0, 0, 0},
{0, 0, 102025, 109725, 30030, 4620, 330, 0, 0, 0, 0},
{0, 10395, 115500, 46200, 6930, 462, 0, 0, 0, 0, 0},
{0, 17325, 39270, 6930, 462, 0, 0, 0, 0, 0, 0},
{0, 6930, 4620, 330, 0, 0, 0, 0, 0, 0, 0},
{0, 990, 165, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 55, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
}

The idea of double enumeration seems like a natural
extension of the principle of counting a thing in two
different ways.

cheers,
George

PS here is the Mathematica program:

StirlingS2Square[n_] :=
Module[{sn, sk, maxl, tr, vpos, m},
sn = SetPartitions[n];
sk = Length /@ sn;
maxl = Max[Length /@ #] & /@ sn;
tr = Transpose@{sk, maxl};
vpos = {Length@#, First@#} & /@ Split@Sort@tr;
m = Table[0, {i, n}, {j, n}];
Map[(m[[#[[2, 1]], #[[2, 2]]]] = #[[1]]) &, vpos];
m]

[Peter Luschny]

Dear George,

welcome to the group!

(Note that I changed the linear order of your sentences.)

> The idea of double enumeration seems like a natural extension
> of the principle of counting a thing in two different ways.

Yes, I agree.

> To be more specific (but still general!),
> say we have a function f[n,k] that counts from n objects those
> objects x for which ff[x] = k, and similarly for g. Then the matrix
> fg[i, j] would count those objects x for which ff[x] = i and gg[x] = j.
> The sum of the row sums will be equal to the sum of the column sums.

Yes.

> The idea of Eulerian Numbers versus Stirling Numbers of the
> First Kind is that when something--n! in that case--can
> be counted in two ways, make a matrix that counts the objects
> in both ways.

This is a nice example! As you write in your demonstration,
the idea is based on an enumeration of permutations, counting
the number of ascents respectively the number of cycles.

A similar double enumeration, perhaps even simpler, is: Take
a tree, then enumerate one time with respect to the width of the
tree and the other time with respect to the height of the tree.

But we can do even better. We can write permutations as trees!
Then we can enumerate the 'permutation trees' by width or by
height. What do we get? Your double enumeration? Not quite!
However, even the Stirling part is hidden in the tree. So have
have indeed three double enumerations hidden in this example!
All this is very beautiful and you can explore the details here [1].

[By the way, I do not know a reference describing 'permutation trees'.
If someone can give me a hint I would be grateful. The fact that
A179454, A179455, A179456 and A179457 are all new is really
surprising given that this is a standard topic in combinatorics.]

When time permits I will look at the second part of your post.
Cheers, Peter

[1] http://oeis.org/wiki/User:Peter_Luschny/PermutationTrees

[Peter Luschny]

> A similar double enumeration, perhaps even simpler, is: Take
> a tree, then enumerate one time with respect to the width of the
> tree and the other time with respect to the height of the tree.

I have now elaborated on this:
http://oeis.org/wiki/User:Peter_Luschny/DoubleEnumeration