[seqfan] Multiset transformations

Richard J. Mathar mathar at mpia-hd.mpg.de
Wed Jul 20 16:51:35 CEST 2016


There is a Multiset transformation defined by using a sequence a(n), n>=1,
which counts object of some size n, and builds rooted forests that can
be summarized in triangles T(n,k), where k is the number of trees in the
forest and n is the number of nodes in the forest, where nodes are
objects counted by a(n).

The concept of shown in

P. Flajolet, R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/book.pdf">Analytic combinatorics</a>, Theorem I.1

and the formula defining the triangle is
T(n,1) = a(n).
T(n,k) = Sum_{c_i*N_i=n,i=1..k} binomial(T(N_i,1)+c_i-1,c_i) for 1<k<=n

Some examples in the OEIS are:
Sequence A000081 generates the triangle A033185.
Sequence A038055 generates the triangle A271878.
Sequence A000079 generates the triangle A209406.
Sequence A000055 generates the triangle A095133.
Sequence A001349 generates the triangle A201922.
Sequence A038059 generates the triangle A271879.

This is merely a call to search for more of these connections and add 
the associated cross-references to the OEIS. It seems for example that the following triangle
generated by A000244 is not yet in the OEIS:

--
Triangle T(n,k) by rows: number of multisets of exactly k ternary words with a total of n letters.

offset 1

Ternary analog of A209406.
This is a Multiset transformation of A000244 (powers of 3)

    3 
    9     6 
   27    27    10 
   81   126    54    15 
  243   486   297    90    21 
  729  1836  1380   540   135    28 
 2187  6561  5994  2763   855   189    36 
 6561 23004 24543 13212  4635  1242   252    45 
19683 78732 96723 59130 23490  6996  1701   324    55 
59049 265842 368874 253719 111609 36828  9846  2232   405    66 


Cf. A000244 (column k=1), A144067 (row sums), A027468 (subdiagonal ?)
--
One may also consider adding the "Motzkin Multipaths" from A001006:

    1 
    2     1 
    4     2     1 
    9     7     2     1 
   21    17     7     2     1 
   51    49    21     7     2     1 
  127   129    61    21     7     2     1 
  323   358   176    66    21     7     2     1 
  835   970   513   192    66    21     7     2     1 
 2188  2679  1471   579   198    66    21     7     2     1 

with row sums 1, 3, 7, 19, 48, 131, 348, 954, 2607, 7212, 19995, 55816, 156246, 439267...
and with 2nd column A275209.

The concept make combinatorial sense if a(n) counts objects that
are in some sense "bound" or "connected", and where T(n,k) shows
how many of the can be placed in multisets "side by side" by putting
a constraint 'n' on the number of objects in the sets and a constraint 'k'
on the number of objects, such that the multiset has a well-defined
meaning of counting the "dis-connected" objects.

RJM

# Count the frequency of n in the list L
# @param L The list of elements.
# @param n The needle to search for.
# @return The number of occurences of n in L.
# @since 2016-03-06
freq := proc(L::list,n::integer)
        local ct,l;
        ct := 0 ;
        for l in L do
                if l = n then
                        ct := ct+1 ;
                end if;
        end do:
        return ct;
end proc:


pickP := proc(C::integer,c::integer)
        binomial(C+c-1,c) ;
end proc:

# A multiset decompositon of L.
# @param L L[1] corresponds to the n>=1 elements in the first column
# @param n row index >=1
# @param f column index >=1 and <=n. If f=1, pick L[f] ;
# @see arxiv.org:1603.00077 equation 22.
MultiSet := proc(L::list,n::integer,f::integer)
        option remember ;
        local c,ct,i,cof,thisp,oldp,thisC;
        if n < 0 then
                return 0;
        elif n = 0 then
                return 1;
        elif f = 1 then
                # refers to element n (and maple index n)
                return op(n,L) ;
        else
                ct := 0 ;
                # cannot use combinat[partition](N,f) here because
                # f would not mean the number of parts...
                for c in combinat[partition](n) do
                        if nops(c) = f then
                                oldp := -1 ;
                                # print("N=",N,"f=",f,"c=",c) ;
                                cof := 1;
                                for i from 1 to nops(c) do
                                        thisp := op(i,c) ;
                                        thisC := procname(L,thisp,1) ;
                                        fr := freq(c,thisp) ;
                                        if thisp <> oldp then
                                                cof := cof*pickP(thisC,fr) ;
                                                oldp := thisp ;
                                        end if;
                                end do:
                                ct := ct+cof ;
                        end if;
                end do:
                ct ;
        end if;
end proc:

MultiSetSum := proc(L::list,n::integer)
        add( MultiSet(L,n,f),f=1..n) ;
end proc:

# RJM


More information about the SeqFan mailing list