Simple complicated combinatorial problem
Jürgen Will
for a problem from practice, I have to solve the following combinatorial
problem.
Let c[1], c[2], ..., c[n], k[1], k[2], ..., k[n], n be given non-negative
integers, and a[0] , a[1], ..., a[n] empty variables.
Furthermore, it is A = (a[0] + a[1])^k[1] * (a[0] + a[1] + a[2])^k[2] *
(a[0] + a[1] + a[2] + a[3])^k [3] * ... * (a[0] + a[1] + ... + a[n])^k[n].
By which expression / which formula the coefficient of the given term
a[0]^c[0] * a[1]^c [1] * a[2]^c [2] * ... * a[n]^c [n] in A could be
calculated? The expression should be expressed, if possible, immediately in
the form of combinatorial formulas or by using combinatorial numbers, for
example by using multinomial coefficients, partitions, compositions, partial
ordinary Bell polynomials or cycle indices of composed permutation groups.
The single factors (a[0] + a[1] + ... + a[m])^k[m] can be expanded by the
multinomial theorem. This gives a stock of single parts. But how can I
determine from the given c[i], which of the single parts have to be combined
to construct the given term?
I 'm not a mathematician.
Thank you.
shallot
a[n])^k[n]
item's 'coefficient' like this:
S[n,k[1],k[2],...,k[n]]=S[n-1,k[1],k[2],...,k[n-1]]*C(k[n],c[n])*a[n]^c[n]*(a[0]+...+a[n-1])^(k[n]-c[n])
=S[n-1,k[1],k[2],...,(k[n-1]+k[n]-c[n]]*C(k[n],c[n])*a[n]^c[n]
We set the array {p[n]} as following:
p[n]=k[n]; p[i]=k[i]+...+k[n]-c[i+1]-...-c[n] (1<=i<n) (p[i]
must be larger than zero)
From this recursion formula, we can get:
S[n,k[1],k[2],...,k[n]]=S[n-1,k[1],k[2],...,p[n-1]]*C(p[n],c[n])*a[n]^c[n]
=S[n-2,k[1],k[2],...,p[n-2]]*C(p[n-1],c[n-1])*C(p[n],c[n])*a[n-1]^c[n-1]*a[n]^c[n]
=.....
=S[1,p[1])*C(p[2],c[2])*...C(p[n],c[n])*a[2]^c[2]*...*a[n]^c[n]
={C(p[1],c[1])*...*C(p[n],c[n])} *
{a[0]^(p[1]-c[1])*a[1]^c[1]*...*a[n]^c[n])
So c[0]=p[1]-c[1]=k[1]+..+k[n]-c[1]-...-c[n]. i.e.
c[0]+...c[n]=k[0]+...k[n].
The coefficient is C(p[1],c[1])*...*C(p[n],c[n]).
"Jürgen Will" <jw...@onlinehome.de>
??????:iequls$o42$02$1...@news.t-online.com...
--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---
Bastian Erdnuess
> We set S[n,k[1],k[2],...,k[n]]=(a[0] + a[1])^k[1] * (a[0] + a[1] +
> a[2])^k[2] * (a[0] + a[1] + a[2] + a[3])^k [3] * ... * (a[0] + a[1] + ... +
> a[n])^k[n]
> Consider the item including a[n]^c[n]. From the final item, we can get this
> item's 'coefficient' like this:
> S[n,k[1],k[2],...,k[n]]=S[n-1,k[1],k[2],...,k[n-1]]*C(k[n],c[n])*a[n]^c[n]*(a[0]+...+a[n-1])^(k[n]-c[n])
> =S[n-1,k[1],k[2],...,(k[n-1]+k[n]-c[n]]*C(k[n],c[n])*a[n]^c[n]
> We set the array {p[n]} as following:
> p[n]=k[n]; p[i]=k[i]+...+k[n]-c[i+1]-...-c[n] (1<=i<n) (p[i]
> must be larger than zero)
> From this recursion formula, we can get:
> S[n,k[1],k[2],...,k[n]]=S[n-1,k[1],k[2],...,p[n-1]]*C(p[n],c[n])*a[n]^c[n]
> =S[n-2,k[1],k[2],...,p[n-2]]*C(p[n-1],c[n-1])*C(p[n],c[n])*a[n-1]^c[n-1]*a[n]^c[n]
> =.....
> =S[1,p[1])*C(p[2],c[2])*...C(p[n],c[n])*a[2]^c[2]*...*a[n]^c[n]
> ={C(p[1],c[1])*...*C(p[n],c[n])} *
> {a[0]^(p[1]-c[1])*a[1]^c[1]*...*a[n]^c[n])
> So c[0]=p[1]-c[1]=k[1]+..+k[n]-c[1]-...-c[n]. i.e.
> c[0]+...c[n]=k[0]+...k[n].
> The coefficient is C(p[1],c[1])*...*C(p[n],c[n]).
cool.
Jürgen Will
news:ierp3s$1e0f$1...@adenine.netfront.net...
> The coefficient is C(p[1],c[1])*...*C(p[n],c[n]).
I think that is what I need.
Thank you.
I need it for a new fundamental method in mathematics that I develop for
some time.
I work with the combinatorics of unrestricted and restricted integer
partitions.
Jürgen Will
news:ierp3s$1e0f$1...@adenine.netfront.net...
My problem is more complicated, so shallot's approach with bracketing out
the highest element is not applicable.
The multinomial A in my task contains further variables g[]. I write here
again the complete task with the extended multinomial A.
Let c[0], c[1], c[2], ..., c[n], d[0], d[1], d[2], ..., d[n], k[1], k[2],
..., k[n], n be given non-negative integers, and a[0] , a[1], ..., a[n],
b[0] , b[1], ..., b[n] empty variables.
Furthermore, it is A = (a[0]b[1]+ a[1]b[0])^k[1] * (a[0]b[2] + a[1]b[1] +
a[2]b[0])^k[2] * (a[0]b[3] + a[1]b[2] + a[2]b[1] + a[3]b[0])^k[3] * ... *
(a[0]b[n] + a[1]b[n-1] + ... + a[n]b[0])^k[n].
By which expression / which formula the coefficient of the given term
a[0]^c[0]*a[1]^c[1]*a[2]^c[2]* ... *
a[n]^c[n]*b[0]^d[0]*b[1]^d[1]*b[2]^d[2]* ... * b[n]^d[n in A could be
calculated? The expression should be expressed, if possible, immediately in
the form of combinatorial formulas or by using combinatorial numbers, for
example by using multinomial coefficients, partitions, compositions, partial
ordinary Bell polynomials or cycle indices of composed permutation groups.
The single factors (a[0]b[i] + a[1]b[i-1] + ... + a[i]b[0])^k[i] can be
expanded by the multinomial theorem. This gives a stock of single parts. But
how can I determine from the given c[] and d[], which of the single parts
have to be combined to construct the given term?
A factor (a[0]b[i] + a[1]b [i-1] + ... + a[i]b[0])^k[i] gives with the
multinomial theorem the single members (a[0]b[i])^t[i, 0] *
(a[1]b[i-1])^t[i,1] * ... * (a[i]b[0])^t[i,i]. It is
t[i,0]+t[i,1]+...+t[i,i] = k[i].
The tuples [t[i,0],t[i,1 ],...,t[i,i]] are the compositions (permutations of
the number of partitions of 0) to i+1 parts of k[i].
The single tuples of the individual factors must be combined and added so
that the given exponent tupel [c[0],c[1 ],...,c[n],d[0],d[1],...,d[n]]
results.
I can indeed generate and calculate the desired coefficient in this way, but
I do not know how I can write the sought coefficient as an expression of
combinatorial numbers.
There are Diophantine equations to solve, or, in other words, partitions
assembled by sub-partitions.
Could perhaps permutation groups help?
Could perhaps Pólya counting or Partition Analysis of MacMahon help?
Does anyone have any idea?