connections among distant sequences

Wouter Meeussen wouter.meeussen at
Mon Feb 11 00:15:42 CET 2002

in some of the stuff below, it can be argued that
a single "strategy" connects distant sequences.
Maybe arbitrary, maybe original & productive.
(cum grano salis)

Consider all possible combinations of two-argument
functions P,Q and R, wraped around their arguments
a,b,c and d,  as in

P[a, Q[b, R[c, d]]]
P[a, Q[R[b, c], d]]
P[Q[a, b], R[c, d]]
P[Q[a, R[b, c]], d]
P[Q[R[a, b], c], d]

the 5 results represent the five "bracketings"
with 3 sets of brackets (= 3 functions).
(bracketings are counted by Catalans, or binary trees).

Same thing can be done for w=1 ... 6 or more functions
with (w+1) arguments, but calculations get nasty & slow.

And now for some counting.
You'll notice that both functions and arguments remain
"in sequence" (please pardon this cheap pun).

What if we replace the functions with functions A or B,
in all 2^w combinations, 
and, to top that, we present the arguments in any order,
effectively generating all permutations of them.

What can this result be called?
All possible outcomes of applying the functions A and\or B
warped w times on the w+1 arguments a[1] ... a[w+1]

Now, imagine that functions A and B have no special nice properties,
Then every result is different, and we easily count the *different*
results as function of w:     2^w cat[w] (w+1)! 
or {4,48,960,26880,967680, 42577920}=A052714=(2w)!/w! 2^w 

the functions A and B can be given the properties of associativity
and commutativity, or "flat-ness" and "orderless-ness",
the first implying    A[b,A[b,a]]  equals  A[b, b, a]
the second means A[b,a] equals A[a,b] as you all know.

{function A}    {function B}   w={1, 2,3  ,    4}
{nil}           {nil}            {4,48,960,26880}  A052714
{Orderless}     {nil}            {3,27,405, 8505,229635}  A011781
{Orderless}     {Orderless}      {2,12,120, 1680,30240}  A001813 

{Flat}          {nil}            {4,42,744,18480}  do not match anything 
{Flat}          {Orderless}      {3,21,249, 4155}  do not match anything  
{Flat,Orderless}{nil}            {3,25,351, 6901}  do not match anything 
{Flat,Orderless}{Orderless}      {2,10, 86, 1036}  do not match anything 

{Flat}          {Flat}           {4,36,528,10800}  A052716 
{Flat,Orderless}{Flat}           {3,19,195, 2791}  A053554  A048172 
{Flat,Orderless}{Flat,Orderless} {2, 8, 52,  472}  A006351 

A052714 by encyclopedia at, Jan 25 2000
A011781 by killough at (Lee D. Killough)
A001813 by njas & James A. Sellers (sellersj at, May 01 2000
A052716 by encyclopedia at, Jan 25 2000
A053554 by njas, Jan 16 2000
A048172 by njas
A006351 by njas

If we drop the (w+1)! permutations of the arguments,
and only keep the cat[w] parentesizations of the functions,
w instances of A and b, then we get
{nil}           {nil}
{Orderless}     {nil}
{Orderless}     {Orderless}
are all                          {28,40,224,1344,8448,54912} A052701

{Flat}          {nil}
{Flat}          {Orderless}
are all                          {2,7,31,154,820,4575,26398} A007863 

{Flat}          {Flat}           
are both                         {2,6,22,90,394,1806,8558} A006318
                                 =2* A001003
needless to say that fitting to a sequence, using a 4 term match,
should be called "poor & unsafe".
Maybe someone with brains & training could have a peek at this?

"in obscuritate finio"       ;-)
wouter.meeussen at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the SeqFan mailing list