Mixing
Multinomial Expansion
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Given $x_0 ldots x_k$ and $n$, Define $$f(Q)=sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$. Note that $$sum_Q=0^n*k f(Q)=(sum_i=0^kx_i)^n$$ which comes from the multinomial expansion. I was wondering how to calculate $sum_Q=0^n*k Qcdot f(Q)$.
I've checked several small cases, and it seems that $sum_Q=0^n*k Qcdot f(Q) = n(sum_i=0^kx_i)^n-1(sum_i=0^kix_i)$, but I'm not sure how to prove that.
combinatorics integer-partitions multinomial-coefficients
asked Jul 26 at 16:41
Hang Wu
658
add a comment |Â
up vote
2
down vote
favorite
Given $x_0 ldots x_k$ and $n$, Define $$f(Q)=sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$. Note that $$sum_Q=0^n*k f(Q)=(sum_i=0^kx_i)^n$$ which comes from the multinomial expansion. I was wondering how to calculate $sum_Q=0^n*k Qcdot f(Q)$.
I've checked several small cases, and it seems that $sum_Q=0^n*k Qcdot f(Q) = n(sum_i=0^kx_i)^n-1(sum_i=0^kix_i)$, but I'm not sure how to prove that.
combinatorics integer-partitions multinomial-coefficients
asked Jul 26 at 16:41
Hang Wu
658
Please define value ranges, e.g for $n$ and $Q$.
– user90369
Jul 26 at 16:56
All of them are several million.
– Hang Wu
Jul 26 at 17:08
A comment for future: you've changed your question significantly since I wrote my answer (to the point that it's not the same question at all anymore). This will create a lot of issues for the people who'll visit this page later. Next time, leave the original question as it is. Then either add something like Update or Edit section at the end, expanding on the question. Or open a new question and link it to this one.
– Hamed
Aug 1 at 18:23
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Given $x_0 ldots x_k$ and $n$, Define $$f(Q)=sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$. Note that $$sum_Q=0^n*k f(Q)=(sum_i=0^kx_i)^n$$ which comes from the multinomial expansion. I was wondering how to calculate $sum_Q=0^n*k Qcdot f(Q)$.
I've checked several small cases, and it seems that $sum_Q=0^n*k Qcdot f(Q) = n(sum_i=0^kx_i)^n-1(sum_i=0^kix_i)$, but I'm not sure how to prove that.
combinatorics integer-partitions multinomial-coefficients
asked Jul 26 at 16:41
Hang Wu
658
Given $x_0 ldots x_k$ and $n$, Define $$f(Q)=sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$. Note that $$sum_Q=0^n*k f(Q)=(sum_i=0^kx_i)^n$$ which comes from the multinomial expansion. I was wondering how to calculate $sum_Q=0^n*k Qcdot f(Q)$.
I've checked several small cases, and it seems that $sum_Q=0^n*k Qcdot f(Q) = n(sum_i=0^kx_i)^n-1(sum_i=0^kix_i)$, but I'm not sure how to prove that.
combinatorics integer-partitions multinomial-coefficients
asked Jul 26 at 16:41
Hang Wu
658
edited Jul 30 at 1:45
asked Jul 26 at 16:41
Hang Wu
658
asked Jul 26 at 16:41
Hang Wu
658
asked Jul 26 at 16:41
Hang Wu
658
658
Please define value ranges, e.g for $n$ and $Q$.
– user90369
Jul 26 at 16:56
All of them are several million.
– Hang Wu
Jul 26 at 17:08
A comment for future: you've changed your question significantly since I wrote my answer (to the point that it's not the same question at all anymore). This will create a lot of issues for the people who'll visit this page later. Next time, leave the original question as it is. Then either add something like Update or Edit section at the end, expanding on the question. Or open a new question and link it to this one.
– Hamed
Aug 1 at 18:23
add a comment |Â
Please define value ranges, e.g for $n$ and $Q$.
– user90369
Jul 26 at 16:56
All of them are several million.
– Hang Wu
Jul 26 at 17:08
A comment for future: you've changed your question significantly since I wrote my answer (to the point that it's not the same question at all anymore). This will create a lot of issues for the people who'll visit this page later. Next time, leave the original question as it is. Then either add something like Update or Edit section at the end, expanding on the question. Or open a new question and link it to this one.
– Hamed
Aug 1 at 18:23
Please define value ranges, e.g for $n$ and $Q$.
– user90369
Jul 26 at 16:56
Please define value ranges, e.g for $n$ and $Q$.
– user90369
Jul 26 at 16:56
All of them are several million.
– Hang Wu
Jul 26 at 17:08
All of them are several million.
– Hang Wu
Jul 26 at 17:08
A comment for future: you've changed your question significantly since I wrote my answer (to the point that it's not the same question at all anymore). This will create a lot of issues for the people who'll visit this page later. Next time, leave the original question as it is. Then either add something like Update or Edit section at the end, expanding on the question. Or open a new question and link it to this one.
– Hamed
Aug 1 at 18:23
A comment for future: you've changed your question significantly since I wrote my answer (to the point that it's not the same question at all anymore). This will create a lot of issues for the people who'll visit this page later. Next time, leave the original question as it is. Then either add something like Update or Edit section at the end, expanding on the question. Or open a new question and link it to this one.
– Hamed
Aug 1 at 18:23
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
3
down vote
You can calculate the generating function instead. Define
$$
beginaligned
F(X,Y)&=
sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k\
&=sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_n_0, cdots, n_kgeq 0 frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k
deltaleft(n-sum_j=0^k n_jright)
deltaleft(Q-sum_j=0^k jn_jright)\
&=
sum_n_0, cdots, n_kgeq 0
frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k X^sum_j n_j Y^sum_j jn_j\
&=prod_m=0^k exp(x_m XY^m)
endaligned
$$
where by $delta(Z)$ I mean the Kronecker delta equating $Z=0$. What you are looking for the $n!$ times the coefficient of $X^nY^Q$ in the expansion of $F(X,Y)$ (in other words, $(Q!)^-1partial_X^n partial_Y^Q Fmid_X=Y=0$).
answered Jul 26 at 19:40
Hamed
4,343421
add a comment |Â
up vote
2
down vote
Wikipedia on Bell polynomials:
Likewise, the partial ordinary Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by $$hatB_n,k(x_1,x_2,ldots,x_n-k+1)=sum frack!j_1! j_2! cdots j_n-k+1! x_1^j_1 x_2^j_2 cdots x_n-k+1^j_n-k+1,$$
where the sum runs over all sequences $j_1, j_2, j_3, ldots, j_n−k+1$ of non-negative integers such that $$
j_1 + j_2 + cdots + j_n-k+1 = k, \
j_1 + 2j_2 + cdots + (n-k+1)j_n-k+1 = n.$$
So your sum $$sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2n_2+ldots+kn_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$
is
$$sum_n_0=0^n binomnn_0 x_0^n_0 hatB_Q,n-n_0(x_1, x_2, ldots, x_k)$$
Using $$hat B_n,k(x_1,x_2,ldots ,x_n-k+1)=frac k!n!B_n,k(1!cdot x_1,2!cdot x_2,ldots ,(n-k+1)!cdot x_n-k+1)$$ we have
$$fracn!Q!sum_n_0=0^n fracx_0^n_0n_0! B_Q,n-n_0(1!cdot x_1, 2!cdot x_2, ldots, k!cdot x_k)$$
Then the recurrence relation $$B_n,k=sum_i=1^n-k+1 binomn-1i-1 x_i B_n-i,k-1$$
gives you an evaluation strategy.
answered Jul 27 at 8:04
Peter Taylor
7,69512239
add a comment |Â
up vote
1
down vote
Starting from Hamed's answer, we can give a quick proof that $sum_Qge 0 Qf(Q)$ equals what you think it is. They proved
$$
sum_nge 0sum_qge 0frac1n!f_n(Q)X^nY^q = expBig(sum_m=0^k x_mXY^mBig)
$$
Differentiating both sides with respect to $Y$, and then multiplying by $Y$, you get
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^nY^q = big(sum_k=0^m mx_m XY^mbig)expBig(sum_m=0^k x_mXY^mBig)
$$
Notice that we now have a $Qf_n(Q)$. These need to be summed, so set $Y=1$:
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^n = big(sum_k=0^m mx_m Xbig)expBig(Xsum_m=0^k x_mBig)
$$
Finally, extract the coefficient of $X^n$ of both sides. On the left hand side, $X_n$ has a $frac1n!sum_qge 0QF_n(Q)$ attached to it. On the right, you get the $X^n$ coefficient by multiplying $big(sum_k=0^m mx_mbig)$ with the $X^n-1$ coefficient of $expBig(Xsum_m=0^k x_mBig)$. This implies
$$
frac1n!sum_qge 0QF_n(Q)=big(sum_k=0^m mx_mbig)cdot frac1(n-1)!Big(sum_k=0^m x_mBig)^n-1
$$
which is what you wanted.
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
add a comment |Â
up vote
0
down vote
I'm going to provide a secondary generating function which is probably more relevant to your updated question. Let's recall your definition,
$$
f(Q):=sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq0 \sum_j=0^kjn_j=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
$$
and let us calculate $
G(X):=sum_Q=0^nk f(Q)X^Q
$. Before, we do that note that for any $pgeq 0$, $$boxedsum_Q=0^nk Q^pf(Q)=left.left(XfracddXright)^p G(X)right$$
First of all, note that under the condition $sum_j=0^k n_j = n$ and $n_0, cdots, n_kgeq 0$, one has
$$
nk -sum_j=0^k jn_j=
sum_j=0^k (k-j) n_jgeq 0
$$
As a result, the equation $z-sum_j=0^k jn_j=0$ has exactly one solution for $z$ in the integer range $0leq zleq nk$. Using this, we have
$$
beginaligned
G(X)&=sum_Q=0^nk X^Q
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
deltaleft(Q-sum_j=0^kjn_jright)
\
&=
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kprod_m=0^k (x_mX^m)^n_m=left(sum_m=0^k x_m X^mright)^n
endaligned
$$
So to summarize:
$$
boxed
G(X)=sum_Q=0^nk f(Q) X^Q = left(sum_m=0^k x_m X^mright)^n
$$
This should make the rest obvious.
answered Aug 1 at 19:01
Hamed
4,343421
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
You can calculate the generating function instead. Define
$$
beginaligned
F(X,Y)&=
sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k\
&=sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_n_0, cdots, n_kgeq 0 frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k
deltaleft(n-sum_j=0^k n_jright)
deltaleft(Q-sum_j=0^k jn_jright)\
&=
sum_n_0, cdots, n_kgeq 0
frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k X^sum_j n_j Y^sum_j jn_j\
&=prod_m=0^k exp(x_m XY^m)
endaligned
$$
where by $delta(Z)$ I mean the Kronecker delta equating $Z=0$. What you are looking for the $n!$ times the coefficient of $X^nY^Q$ in the expansion of $F(X,Y)$ (in other words, $(Q!)^-1partial_X^n partial_Y^Q Fmid_X=Y=0$).
answered Jul 26 at 19:40
Hamed
4,343421
add a comment |Â
up vote
3
down vote
You can calculate the generating function instead. Define
$$
beginaligned
F(X,Y)&=
sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k\
&=sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_n_0, cdots, n_kgeq 0 frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k
deltaleft(n-sum_j=0^k n_jright)
deltaleft(Q-sum_j=0^k jn_jright)\
&=
sum_n_0, cdots, n_kgeq 0
frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k X^sum_j n_j Y^sum_j jn_j\
&=prod_m=0^k exp(x_m XY^m)
endaligned
$$
where by $delta(Z)$ I mean the Kronecker delta equating $Z=0$. What you are looking for the $n!$ times the coefficient of $X^nY^Q$ in the expansion of $F(X,Y)$ (in other words, $(Q!)^-1partial_X^n partial_Y^Q Fmid_X=Y=0$).
answered Jul 26 at 19:40
Hamed
4,343421
add a comment |Â
up vote
3
down vote
up vote
3
down vote
You can calculate the generating function instead. Define
$$
beginaligned
F(X,Y)&=
sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k\
&=sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_n_0, cdots, n_kgeq 0 frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k
deltaleft(n-sum_j=0^k n_jright)
deltaleft(Q-sum_j=0^k jn_jright)\
&=
sum_n_0, cdots, n_kgeq 0
frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k X^sum_j n_j Y^sum_j jn_j\
&=prod_m=0^k exp(x_m XY^m)
endaligned
$$
where by $delta(Z)$ I mean the Kronecker delta equating $Z=0$. What you are looking for the $n!$ times the coefficient of $X^nY^Q$ in the expansion of $F(X,Y)$ (in other words, $(Q!)^-1partial_X^n partial_Y^Q Fmid_X=Y=0$).
answered Jul 26 at 19:40
Hamed
4,343421
You can calculate the generating function instead. Define
$$
beginaligned
F(X,Y)&=
sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2*n_2+ldots+k*n_k=Q frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k\
&=sum_n=0^infty X^nsum_Q=0^infty Y^Q
sum_n_0, cdots, n_kgeq 0 frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k
deltaleft(n-sum_j=0^k n_jright)
deltaleft(Q-sum_j=0^k jn_jright)\
&=
sum_n_0, cdots, n_kgeq 0
frac1n_0!n_1!cdots n_k!x_0^n_0ldots x_k^n_k X^sum_j n_j Y^sum_j jn_j\
&=prod_m=0^k exp(x_m XY^m)
endaligned
$$
where by $delta(Z)$ I mean the Kronecker delta equating $Z=0$. What you are looking for the $n!$ times the coefficient of $X^nY^Q$ in the expansion of $F(X,Y)$ (in other words, $(Q!)^-1partial_X^n partial_Y^Q Fmid_X=Y=0$).
answered Jul 26 at 19:40
Hamed
4,343421
answered Jul 26 at 19:40
Hamed
4,343421
answered Jul 26 at 19:40
Hamed
4,343421
answered Jul 26 at 19:40
Hamed
4,343421
4,343421
add a comment |Â
add a comment |Â
up vote
2
down vote
Wikipedia on Bell polynomials:
Likewise, the partial ordinary Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by $$hatB_n,k(x_1,x_2,ldots,x_n-k+1)=sum frack!j_1! j_2! cdots j_n-k+1! x_1^j_1 x_2^j_2 cdots x_n-k+1^j_n-k+1,$$
where the sum runs over all sequences $j_1, j_2, j_3, ldots, j_n−k+1$ of non-negative integers such that $$
j_1 + j_2 + cdots + j_n-k+1 = k, \
j_1 + 2j_2 + cdots + (n-k+1)j_n-k+1 = n.$$
So your sum $$sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2n_2+ldots+kn_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$
is
$$sum_n_0=0^n binomnn_0 x_0^n_0 hatB_Q,n-n_0(x_1, x_2, ldots, x_k)$$
Using $$hat B_n,k(x_1,x_2,ldots ,x_n-k+1)=frac k!n!B_n,k(1!cdot x_1,2!cdot x_2,ldots ,(n-k+1)!cdot x_n-k+1)$$ we have
$$fracn!Q!sum_n_0=0^n fracx_0^n_0n_0! B_Q,n-n_0(1!cdot x_1, 2!cdot x_2, ldots, k!cdot x_k)$$
Then the recurrence relation $$B_n,k=sum_i=1^n-k+1 binomn-1i-1 x_i B_n-i,k-1$$
gives you an evaluation strategy.
answered Jul 27 at 8:04
Peter Taylor
7,69512239
add a comment |Â
up vote
2
down vote
Wikipedia on Bell polynomials:
Likewise, the partial ordinary Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by $$hatB_n,k(x_1,x_2,ldots,x_n-k+1)=sum frack!j_1! j_2! cdots j_n-k+1! x_1^j_1 x_2^j_2 cdots x_n-k+1^j_n-k+1,$$
where the sum runs over all sequences $j_1, j_2, j_3, ldots, j_n−k+1$ of non-negative integers such that $$
j_1 + j_2 + cdots + j_n-k+1 = k, \
j_1 + 2j_2 + cdots + (n-k+1)j_n-k+1 = n.$$
So your sum $$sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2n_2+ldots+kn_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$
is
$$sum_n_0=0^n binomnn_0 x_0^n_0 hatB_Q,n-n_0(x_1, x_2, ldots, x_k)$$
Using $$hat B_n,k(x_1,x_2,ldots ,x_n-k+1)=frac k!n!B_n,k(1!cdot x_1,2!cdot x_2,ldots ,(n-k+1)!cdot x_n-k+1)$$ we have
$$fracn!Q!sum_n_0=0^n fracx_0^n_0n_0! B_Q,n-n_0(1!cdot x_1, 2!cdot x_2, ldots, k!cdot x_k)$$
Then the recurrence relation $$B_n,k=sum_i=1^n-k+1 binomn-1i-1 x_i B_n-i,k-1$$
gives you an evaluation strategy.
answered Jul 27 at 8:04
Peter Taylor
7,69512239
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Wikipedia on Bell polynomials:
Likewise, the partial ordinary Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by $$hatB_n,k(x_1,x_2,ldots,x_n-k+1)=sum frack!j_1! j_2! cdots j_n-k+1! x_1^j_1 x_2^j_2 cdots x_n-k+1^j_n-k+1,$$
where the sum runs over all sequences $j_1, j_2, j_3, ldots, j_n−k+1$ of non-negative integers such that $$
j_1 + j_2 + cdots + j_n-k+1 = k, \
j_1 + 2j_2 + cdots + (n-k+1)j_n-k+1 = n.$$
So your sum $$sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2n_2+ldots+kn_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$
is
$$sum_n_0=0^n binomnn_0 x_0^n_0 hatB_Q,n-n_0(x_1, x_2, ldots, x_k)$$
Using $$hat B_n,k(x_1,x_2,ldots ,x_n-k+1)=frac k!n!B_n,k(1!cdot x_1,2!cdot x_2,ldots ,(n-k+1)!cdot x_n-k+1)$$ we have
$$fracn!Q!sum_n_0=0^n fracx_0^n_0n_0! B_Q,n-n_0(1!cdot x_1, 2!cdot x_2, ldots, k!cdot x_k)$$
Then the recurrence relation $$B_n,k=sum_i=1^n-k+1 binomn-1i-1 x_i B_n-i,k-1$$
gives you an evaluation strategy.
answered Jul 27 at 8:04
Peter Taylor
7,69512239
Wikipedia on Bell polynomials:
Likewise, the partial ordinary Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by $$hatB_n,k(x_1,x_2,ldots,x_n-k+1)=sum frack!j_1! j_2! cdots j_n-k+1! x_1^j_1 x_2^j_2 cdots x_n-k+1^j_n-k+1,$$
where the sum runs over all sequences $j_1, j_2, j_3, ldots, j_n−k+1$ of non-negative integers such that $$
j_1 + j_2 + cdots + j_n-k+1 = k, \
j_1 + 2j_2 + cdots + (n-k+1)j_n-k+1 = n.$$
So your sum $$sum_substackn_0+ldots+n_k=n \ n_0,ldots,n_k >=0 \n_1+2n_2+ldots+kn_k=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k$$
is
$$sum_n_0=0^n binomnn_0 x_0^n_0 hatB_Q,n-n_0(x_1, x_2, ldots, x_k)$$
Using $$hat B_n,k(x_1,x_2,ldots ,x_n-k+1)=frac k!n!B_n,k(1!cdot x_1,2!cdot x_2,ldots ,(n-k+1)!cdot x_n-k+1)$$ we have
$$fracn!Q!sum_n_0=0^n fracx_0^n_0n_0! B_Q,n-n_0(1!cdot x_1, 2!cdot x_2, ldots, k!cdot x_k)$$
Then the recurrence relation $$B_n,k=sum_i=1^n-k+1 binomn-1i-1 x_i B_n-i,k-1$$
gives you an evaluation strategy.
answered Jul 27 at 8:04
Peter Taylor
7,69512239
answered Jul 27 at 8:04
Peter Taylor
7,69512239
answered Jul 27 at 8:04
Peter Taylor
7,69512239
answered Jul 27 at 8:04
Peter Taylor
7,69512239
7,69512239
add a comment |Â
add a comment |Â
up vote
1
down vote
Starting from Hamed's answer, we can give a quick proof that $sum_Qge 0 Qf(Q)$ equals what you think it is. They proved
$$
sum_nge 0sum_qge 0frac1n!f_n(Q)X^nY^q = expBig(sum_m=0^k x_mXY^mBig)
$$
Differentiating both sides with respect to $Y$, and then multiplying by $Y$, you get
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^nY^q = big(sum_k=0^m mx_m XY^mbig)expBig(sum_m=0^k x_mXY^mBig)
$$
Notice that we now have a $Qf_n(Q)$. These need to be summed, so set $Y=1$:
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^n = big(sum_k=0^m mx_m Xbig)expBig(Xsum_m=0^k x_mBig)
$$
Finally, extract the coefficient of $X^n$ of both sides. On the left hand side, $X_n$ has a $frac1n!sum_qge 0QF_n(Q)$ attached to it. On the right, you get the $X^n$ coefficient by multiplying $big(sum_k=0^m mx_mbig)$ with the $X^n-1$ coefficient of $expBig(Xsum_m=0^k x_mBig)$. This implies
$$
frac1n!sum_qge 0QF_n(Q)=big(sum_k=0^m mx_mbig)cdot frac1(n-1)!Big(sum_k=0^m x_mBig)^n-1
$$
which is what you wanted.
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
add a comment |Â
up vote
1
down vote
Starting from Hamed's answer, we can give a quick proof that $sum_Qge 0 Qf(Q)$ equals what you think it is. They proved
$$
sum_nge 0sum_qge 0frac1n!f_n(Q)X^nY^q = expBig(sum_m=0^k x_mXY^mBig)
$$
Differentiating both sides with respect to $Y$, and then multiplying by $Y$, you get
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^nY^q = big(sum_k=0^m mx_m XY^mbig)expBig(sum_m=0^k x_mXY^mBig)
$$
Notice that we now have a $Qf_n(Q)$. These need to be summed, so set $Y=1$:
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^n = big(sum_k=0^m mx_m Xbig)expBig(Xsum_m=0^k x_mBig)
$$
Finally, extract the coefficient of $X^n$ of both sides. On the left hand side, $X_n$ has a $frac1n!sum_qge 0QF_n(Q)$ attached to it. On the right, you get the $X^n$ coefficient by multiplying $big(sum_k=0^m mx_mbig)$ with the $X^n-1$ coefficient of $expBig(Xsum_m=0^k x_mBig)$. This implies
$$
frac1n!sum_qge 0QF_n(Q)=big(sum_k=0^m mx_mbig)cdot frac1(n-1)!Big(sum_k=0^m x_mBig)^n-1
$$
which is what you wanted.
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Starting from Hamed's answer, we can give a quick proof that $sum_Qge 0 Qf(Q)$ equals what you think it is. They proved
$$
sum_nge 0sum_qge 0frac1n!f_n(Q)X^nY^q = expBig(sum_m=0^k x_mXY^mBig)
$$
Differentiating both sides with respect to $Y$, and then multiplying by $Y$, you get
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^nY^q = big(sum_k=0^m mx_m XY^mbig)expBig(sum_m=0^k x_mXY^mBig)
$$
Notice that we now have a $Qf_n(Q)$. These need to be summed, so set $Y=1$:
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^n = big(sum_k=0^m mx_m Xbig)expBig(Xsum_m=0^k x_mBig)
$$
Finally, extract the coefficient of $X^n$ of both sides. On the left hand side, $X_n$ has a $frac1n!sum_qge 0QF_n(Q)$ attached to it. On the right, you get the $X^n$ coefficient by multiplying $big(sum_k=0^m mx_mbig)$ with the $X^n-1$ coefficient of $expBig(Xsum_m=0^k x_mBig)$. This implies
$$
frac1n!sum_qge 0QF_n(Q)=big(sum_k=0^m mx_mbig)cdot frac1(n-1)!Big(sum_k=0^m x_mBig)^n-1
$$
which is what you wanted.
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
Starting from Hamed's answer, we can give a quick proof that $sum_Qge 0 Qf(Q)$ equals what you think it is. They proved
$$
sum_nge 0sum_qge 0frac1n!f_n(Q)X^nY^q = expBig(sum_m=0^k x_mXY^mBig)
$$
Differentiating both sides with respect to $Y$, and then multiplying by $Y$, you get
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^nY^q = big(sum_k=0^m mx_m XY^mbig)expBig(sum_m=0^k x_mXY^mBig)
$$
Notice that we now have a $Qf_n(Q)$. These need to be summed, so set $Y=1$:
$$
sum_nge 0sum_qge 0frac1n!Qf_n(Q)X^n = big(sum_k=0^m mx_m Xbig)expBig(Xsum_m=0^k x_mBig)
$$
Finally, extract the coefficient of $X^n$ of both sides. On the left hand side, $X_n$ has a $frac1n!sum_qge 0QF_n(Q)$ attached to it. On the right, you get the $X^n$ coefficient by multiplying $big(sum_k=0^m mx_mbig)$ with the $X^n-1$ coefficient of $expBig(Xsum_m=0^k x_mBig)$. This implies
$$
frac1n!sum_qge 0QF_n(Q)=big(sum_k=0^m mx_mbig)cdot frac1(n-1)!Big(sum_k=0^m x_mBig)^n-1
$$
which is what you wanted.
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
answered Jul 31 at 14:11
Mike Earnest
14.9k11644
14.9k11644
add a comment |Â
add a comment |Â
up vote
0
down vote
I'm going to provide a secondary generating function which is probably more relevant to your updated question. Let's recall your definition,
$$
f(Q):=sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq0 \sum_j=0^kjn_j=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
$$
and let us calculate $
G(X):=sum_Q=0^nk f(Q)X^Q
$. Before, we do that note that for any $pgeq 0$, $$boxedsum_Q=0^nk Q^pf(Q)=left.left(XfracddXright)^p G(X)right$$
First of all, note that under the condition $sum_j=0^k n_j = n$ and $n_0, cdots, n_kgeq 0$, one has
$$
nk -sum_j=0^k jn_j=
sum_j=0^k (k-j) n_jgeq 0
$$
As a result, the equation $z-sum_j=0^k jn_j=0$ has exactly one solution for $z$ in the integer range $0leq zleq nk$. Using this, we have
$$
beginaligned
G(X)&=sum_Q=0^nk X^Q
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
deltaleft(Q-sum_j=0^kjn_jright)
\
&=
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kprod_m=0^k (x_mX^m)^n_m=left(sum_m=0^k x_m X^mright)^n
endaligned
$$
So to summarize:
$$
boxed
G(X)=sum_Q=0^nk f(Q) X^Q = left(sum_m=0^k x_m X^mright)^n
$$
This should make the rest obvious.
answered Aug 1 at 19:01
Hamed
4,343421
add a comment |Â
up vote
0
down vote
I'm going to provide a secondary generating function which is probably more relevant to your updated question. Let's recall your definition,
$$
f(Q):=sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq0 \sum_j=0^kjn_j=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
$$
and let us calculate $
G(X):=sum_Q=0^nk f(Q)X^Q
$. Before, we do that note that for any $pgeq 0$, $$boxedsum_Q=0^nk Q^pf(Q)=left.left(XfracddXright)^p G(X)right$$
First of all, note that under the condition $sum_j=0^k n_j = n$ and $n_0, cdots, n_kgeq 0$, one has
$$
nk -sum_j=0^k jn_j=
sum_j=0^k (k-j) n_jgeq 0
$$
As a result, the equation $z-sum_j=0^k jn_j=0$ has exactly one solution for $z$ in the integer range $0leq zleq nk$. Using this, we have
$$
beginaligned
G(X)&=sum_Q=0^nk X^Q
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
deltaleft(Q-sum_j=0^kjn_jright)
\
&=
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kprod_m=0^k (x_mX^m)^n_m=left(sum_m=0^k x_m X^mright)^n
endaligned
$$
So to summarize:
$$
boxed
G(X)=sum_Q=0^nk f(Q) X^Q = left(sum_m=0^k x_m X^mright)^n
$$
This should make the rest obvious.
answered Aug 1 at 19:01
Hamed
4,343421
add a comment |Â
up vote
0
down vote
up vote
0
down vote
I'm going to provide a secondary generating function which is probably more relevant to your updated question. Let's recall your definition,
$$
f(Q):=sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq0 \sum_j=0^kjn_j=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
$$
and let us calculate $
G(X):=sum_Q=0^nk f(Q)X^Q
$. Before, we do that note that for any $pgeq 0$, $$boxedsum_Q=0^nk Q^pf(Q)=left.left(XfracddXright)^p G(X)right$$
First of all, note that under the condition $sum_j=0^k n_j = n$ and $n_0, cdots, n_kgeq 0$, one has
$$
nk -sum_j=0^k jn_j=
sum_j=0^k (k-j) n_jgeq 0
$$
As a result, the equation $z-sum_j=0^k jn_j=0$ has exactly one solution for $z$ in the integer range $0leq zleq nk$. Using this, we have
$$
beginaligned
G(X)&=sum_Q=0^nk X^Q
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
deltaleft(Q-sum_j=0^kjn_jright)
\
&=
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kprod_m=0^k (x_mX^m)^n_m=left(sum_m=0^k x_m X^mright)^n
endaligned
$$
So to summarize:
$$
boxed
G(X)=sum_Q=0^nk f(Q) X^Q = left(sum_m=0^k x_m X^mright)^n
$$
This should make the rest obvious.
answered Aug 1 at 19:01
Hamed
4,343421
I'm going to provide a secondary generating function which is probably more relevant to your updated question. Let's recall your definition,
$$
f(Q):=sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq0 \sum_j=0^kjn_j=Q binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
$$
and let us calculate $
G(X):=sum_Q=0^nk f(Q)X^Q
$. Before, we do that note that for any $pgeq 0$, $$boxedsum_Q=0^nk Q^pf(Q)=left.left(XfracddXright)^p G(X)right$$
First of all, note that under the condition $sum_j=0^k n_j = n$ and $n_0, cdots, n_kgeq 0$, one has
$$
nk -sum_j=0^k jn_j=
sum_j=0^k (k-j) n_jgeq 0
$$
As a result, the equation $z-sum_j=0^k jn_j=0$ has exactly one solution for $z$ in the integer range $0leq zleq nk$. Using this, we have
$$
beginaligned
G(X)&=sum_Q=0^nk X^Q
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kx_0^n_0ldots x_k^n_k
deltaleft(Q-sum_j=0^kjn_jright)
\
&=
sum_substacksum_i=0^k n_i=n \ n_0,ldots,n_k geq 0 binomnn_0,cdots,n_kprod_m=0^k (x_mX^m)^n_m=left(sum_m=0^k x_m X^mright)^n
endaligned
$$
So to summarize:
$$
boxed
G(X)=sum_Q=0^nk f(Q) X^Q = left(sum_m=0^k x_m X^mright)^n
$$
This should make the rest obvious.
answered Aug 1 at 19:01
Hamed
4,343421
edited Aug 1 at 19:07
answered Aug 1 at 19:01
Hamed
4,343421
answered Aug 1 at 19:01
Hamed
4,343421
answered Aug 1 at 19:01
Hamed
4,343421
4,343421
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863587%2fmultinomial-expansion%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Please define value ranges, e.g for $n$ and $Q$.
– user90369
Jul 26 at 16:56
All of them are several million.
– Hang Wu
Jul 26 at 17:08
A comment for future: you've changed your question significantly since I wrote my answer (to the point that it's not the same question at all anymore). This will create a lot of issues for the people who'll visit this page later. Next time, leave the original question as it is. Then either add something like Update or Edit section at the end, expanding on the question. Or open a new question and link it to this one.
– Hamed
Aug 1 at 18:23