[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