Mixing
Stuck at finding coefficients of generating functions.
$begingroup$
Problem statement:
Show that the number of r-combinations of specification $2^m1^{n-2m}$ is $$sum_k {{m}choose {k}}{{n-m-k}choose{r-2k}}$$
I have found the generating function which is $(1+t+t^2)^m(1+t)^{n-2m}$, but I cannot proceed further to find the general coefficient.
I know the combinatorial proof for this question, I am specifically wanting to practice using generating functions. Any hint will also suffice.
I have tried using the geometric series formula and then Taylor expansion but could not proceed further.
Edit: The particular specification given here means there are objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
combinatorics generating-functions
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
$endgroup$
|
show 1 more comment
$begingroup$
Problem statement:
Show that the number of r-combinations of specification $2^m1^{n-2m}$ is $$sum_k {{m}choose {k}}{{n-m-k}choose{r-2k}}$$
I have found the generating function which is $(1+t+t^2)^m(1+t)^{n-2m}$, but I cannot proceed further to find the general coefficient.
I know the combinatorial proof for this question, I am specifically wanting to practice using generating functions. Any hint will also suffice.
I have tried using the geometric series formula and then Taylor expansion but could not proceed further.
Edit: The particular specification given here means there are objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
combinatorics generating-functions
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
$endgroup$
2
$begingroup$
Actually, I am not sure what you mean by "r-combinations of specification $2^m1^{n-2m}$" (This may very well be due to my limited knowledge). Can you please pose the combinatorial question in words?
$endgroup$
– Anubhab Ghosal
Jan 14 at 14:35
$begingroup$
@AnubhabGhosal 'r-combinations' means combinations of r elements and the particular specfication given here means objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:40
$begingroup$
What do you mean when you say "objects of m kind with 2 of each kind"? Do you mean that there are 2m objects where each object has an identical partner?
$endgroup$
– Cardioid_Ass_22
Jan 14 at 14:52
$begingroup$
@Cardioid_Ass_22 yes
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:54
$begingroup$
Maybe use $1+t+t^2=(1-t^3)/(1-t)$?
$endgroup$
– marty cohen
Jan 14 at 14:59
|
show 1 more comment
$begingroup$
Problem statement:
Show that the number of r-combinations of specification $2^m1^{n-2m}$ is $$sum_k {{m}choose {k}}{{n-m-k}choose{r-2k}}$$
I have found the generating function which is $(1+t+t^2)^m(1+t)^{n-2m}$, but I cannot proceed further to find the general coefficient.
I know the combinatorial proof for this question, I am specifically wanting to practice using generating functions. Any hint will also suffice.
I have tried using the geometric series formula and then Taylor expansion but could not proceed further.
Edit: The particular specification given here means there are objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
combinatorics generating-functions
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
$endgroup$
Problem statement:
Show that the number of r-combinations of specification $2^m1^{n-2m}$ is $$sum_k {{m}choose {k}}{{n-m-k}choose{r-2k}}$$
I have found the generating function which is $(1+t+t^2)^m(1+t)^{n-2m}$, but I cannot proceed further to find the general coefficient.
I know the combinatorial proof for this question, I am specifically wanting to practice using generating functions. Any hint will also suffice.
I have tried using the geometric series formula and then Taylor expansion but could not proceed further.
Edit: The particular specification given here means there are objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
combinatorics generating-functions
combinatorics generating-functions
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
edited Jan 14 at 14:42
Shubhraneel Pal
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
asked Jan 14 at 13:59
Shubhraneel PalShubhraneel Pal
45939
45939
2
$begingroup$
Actually, I am not sure what you mean by "r-combinations of specification $2^m1^{n-2m}$" (This may very well be due to my limited knowledge). Can you please pose the combinatorial question in words?
$endgroup$
– Anubhab Ghosal
Jan 14 at 14:35
$begingroup$
@AnubhabGhosal 'r-combinations' means combinations of r elements and the particular specfication given here means objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:40
$begingroup$
What do you mean when you say "objects of m kind with 2 of each kind"? Do you mean that there are 2m objects where each object has an identical partner?
$endgroup$
– Cardioid_Ass_22
Jan 14 at 14:52
$begingroup$
@Cardioid_Ass_22 yes
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:54
$begingroup$
Maybe use $1+t+t^2=(1-t^3)/(1-t)$?
$endgroup$
– marty cohen
Jan 14 at 14:59
|
show 1 more comment
2
$begingroup$
Actually, I am not sure what you mean by "r-combinations of specification $2^m1^{n-2m}$" (This may very well be due to my limited knowledge). Can you please pose the combinatorial question in words?
$endgroup$
– Anubhab Ghosal
Jan 14 at 14:35
$begingroup$
@AnubhabGhosal 'r-combinations' means combinations of r elements and the particular specfication given here means objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:40
$begingroup$
What do you mean when you say "objects of m kind with 2 of each kind"? Do you mean that there are 2m objects where each object has an identical partner?
$endgroup$
– Cardioid_Ass_22
Jan 14 at 14:52
$begingroup$
@Cardioid_Ass_22 yes
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:54
$begingroup$
Maybe use $1+t+t^2=(1-t^3)/(1-t)$?
$endgroup$
– marty cohen
Jan 14 at 14:59
2
2
$begingroup$
Actually, I am not sure what you mean by "r-combinations of specification $2^m1^{n-2m}$" (This may very well be due to my limited knowledge). Can you please pose the combinatorial question in words?
$endgroup$
– Anubhab Ghosal
Jan 14 at 14:35
$begingroup$
Actually, I am not sure what you mean by "r-combinations of specification $2^m1^{n-2m}$" (This may very well be due to my limited knowledge). Can you please pose the combinatorial question in words?
$endgroup$
– Anubhab Ghosal
Jan 14 at 14:35
$begingroup$
@AnubhabGhosal 'r-combinations' means combinations of r elements and the particular specfication given here means objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:40
$begingroup$
@AnubhabGhosal 'r-combinations' means combinations of r elements and the particular specfication given here means objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:40
$begingroup$
What do you mean when you say "objects of m kind with 2 of each kind"? Do you mean that there are 2m objects where each object has an identical partner?
$endgroup$
– Cardioid_Ass_22
Jan 14 at 14:52
$begingroup$
What do you mean when you say "objects of m kind with 2 of each kind"? Do you mean that there are 2m objects where each object has an identical partner?
$endgroup$
– Cardioid_Ass_22
Jan 14 at 14:52
$begingroup$
@Cardioid_Ass_22 yes
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:54
$begingroup$
@Cardioid_Ass_22 yes
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:54
$begingroup$
Maybe use $1+t+t^2=(1-t^3)/(1-t)$?
$endgroup$
– marty cohen
Jan 14 at 14:59
$begingroup$
Maybe use $1+t+t^2=(1-t^3)/(1-t)$?
$endgroup$
– marty cohen
Jan 14 at 14:59
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
Here we use the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^n
end{align*}
We obtain for non-negative integers $ngeq 2m$ and $rgeq 0$:
begin{align*}
color{blue}{sum_{k=0}^m}&color{blue}{binom{m}{k}binom{n-m-k}{r-2k}}\
&=sum_{k=0}^mbinom{m}{k}[x^{r-2k}](1+x)^{n-m-k}tag{1}\
&=[x^r](1+x)^{n-m}sum_{k=0}^mbinom{m}{k}left(frac{x^2}{1+x}right)^ktag{2}\
&=[x^r](1+x)^{n-m}left(1+frac{x^2}{1+x}right)^mtag{3}\
&,,color{blue}{=[x^r](1+x)^{n-2m}left(1+x+x^2right)^m}
end{align*}
and we conclude
begin{align*}
sum_{r=0}^inftyleft(sum_{k=0}^mbinom{m}{k}binom{n-m-k}{r-2k}right)x^r
=(1+x)^{n-2m}left(1+x+x^2right)^m
end{align*}
Comment:
In (1) we apply the coefficient of operator.
In (2) we factor out terms independent of $k$ by using the linearity of the coefficient of operator and applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.
In (3) we apply the binomial theorem.
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
$endgroup$
add a comment |
$begingroup$
On one hand $$(1+t+t^2)^m=sum_{i=0}^mbinom{m}{i}(1+t)^i(t^2)^{m-i}=sum_{i=0}^mbinom{m}{i}Biggl(sum _{j=0}^ibinom{i}{j}t^j1^{i-j}Biggr)t^{2m-2i}=\sum_{i=0}^msum _{j=0}^ibinom{m}{i}binom{i}{j}t^{j+2m-2i}$$
On the other $$(1+t)^{n-2m}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k1^{n-2m-k}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k$$
Now, let's look at the sum representation we found for $(1+t+t^2)^m$ first (since it's the scarier looking one) and try to simplify it. Suppose we can rewrite this sum as $$sum_pa_pt^p$$ That would be very convenient as this is a nice single sum rather than a double sum. To do that, we need to find $a_p$ in general. Looking at the original double sum we can see that we can find $a_p$ by finding all pairs of $j$ and $i$ such that $jleq i$ and $j+2m-2i=p$- then, calculate for each pair, $binom{m}{i}binom{i}{j}$, and sum all of these binomial products up. Suppose for our (fixed) $p$ we also fixed $i$ at some value between $0$ and $m$. Well, in that case $j$ could take on at most one value- that would be $p+2i-2m$. We say "at most" because $j$ also needs to be $leq i$, i.e., $p+2i-2mleq iimplies ileq 2m-p$. Don't forget though that $j$ also has to be $geq 0$- this means $p+2i-2mgeq 0implies igeq m-frac{p}{2}$ ($j$ will always be an integer so we won't worry about that). So if we vary $i$ between $0$ and $m$, $i$ contributes to the coefficient, $a_p$, iff $m-frac{p}{2}leq ileq 2m-p$, and when that is the case, $i$ contributes exactly $binom{m}{i}binom{i}{p+2i-2m}$ to $a_p$.
In other words, $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
What are the possible values $p$ can take? Well, for each $p$ there must exist $i$ and $j$ in the original double sum's index so that $p=j+2m-2i$ so $p=j+2m-2ileq i+2m-2i=2m-ileq 2m$. Also $p=j+2m-2igeq 0+2m-2i=2m-2igeq 2m-2m=0$. So $p$ ranges from $0$ to $2m$.
Overall we have that $$(1+t+t^2)^m=sum_{p=0}^{2m}a_pt^p$$ where, for each $p$ $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
Time to tackle the big boi.
Now we need to find a nice single sum representation for $(1+t+t^2)^m(1+t)^{n-2m}$. Well, we have a nice(ish) single sum for each of the terms individually- let's try smashing them together.
$$(1+t+t^2)^m(1+t)^{n-2m}=Biggl(sum_{p=0}^{2m}a_pt^pBiggr)Biggl(sum_{k=0}^{n-2m}binom{n-2m}{k}t^kBiggr)=sum_{p=0}^{2m}sum_{k=0}^{n-2m}a_pbinom{n-2m}{k}t^{p+k}$$
Now, we run the same trick again and suppose that this double sum has some single sum expression like $$sum_qb_qt^q$$
To find $b_q$ here, we need find pairs of $p$ and $k$ such that $p+k=q$, $0leq pleq 2m$, and $0leq kleq n-2m$. Now, suppose we fix some $p$ between $0$ and $2m$. Then $k$, again, has at most one value, i.e, $q-p$, and this one value is only valid if $0leq kleq n-2m implies 0leq q-p leq n-2m implies q-n-2mleq pleq q$. This gives us that $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
Again, we can refer to the initial double sum to see that $p+k$ will always vary between $0$ and $n$, so $q$ varies between $0$ and $n$.
This all means: $$(1+t+t^2)^m(1+t)^{n-2m}=sum_{q=0}^nb_qt^q$$
where, for each $q$ $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
The $b_q$ are the coefficients we desire. To simplify (it's really just making things messier) plug in the general single sum expression for $a_p$ $$b_q=sum_{p=q-n-2m}^qBiggl(sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}Biggr)binom{n-2m}{q-p}=\sum_{p=q-n-2m}^qsum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}binom{n-2m}{q-p}$$
After some checking now, I'm pretty sure the working is correct but given the number of mistakes I made writing this, there's still a good chance I messed up somewhere. Regardless, this is basically how you can find the coefficients in general. You'll always end up with a double sum, like the final expression for $b_q$, so you'll probably need to pull out some nifty binomial identities or something to simplify it down to the single sum your question asks for. Or just look at Markus' way simpler answer.
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3073258%2fstuck-at-finding-coefficients-of-generating-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here we use the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^n
end{align*}
We obtain for non-negative integers $ngeq 2m$ and $rgeq 0$:
begin{align*}
color{blue}{sum_{k=0}^m}&color{blue}{binom{m}{k}binom{n-m-k}{r-2k}}\
&=sum_{k=0}^mbinom{m}{k}[x^{r-2k}](1+x)^{n-m-k}tag{1}\
&=[x^r](1+x)^{n-m}sum_{k=0}^mbinom{m}{k}left(frac{x^2}{1+x}right)^ktag{2}\
&=[x^r](1+x)^{n-m}left(1+frac{x^2}{1+x}right)^mtag{3}\
&,,color{blue}{=[x^r](1+x)^{n-2m}left(1+x+x^2right)^m}
end{align*}
and we conclude
begin{align*}
sum_{r=0}^inftyleft(sum_{k=0}^mbinom{m}{k}binom{n-m-k}{r-2k}right)x^r
=(1+x)^{n-2m}left(1+x+x^2right)^m
end{align*}
Comment:
In (1) we apply the coefficient of operator.
In (2) we factor out terms independent of $k$ by using the linearity of the coefficient of operator and applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.
In (3) we apply the binomial theorem.
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
$endgroup$
add a comment |
$begingroup$
Here we use the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^n
end{align*}
We obtain for non-negative integers $ngeq 2m$ and $rgeq 0$:
begin{align*}
color{blue}{sum_{k=0}^m}&color{blue}{binom{m}{k}binom{n-m-k}{r-2k}}\
&=sum_{k=0}^mbinom{m}{k}[x^{r-2k}](1+x)^{n-m-k}tag{1}\
&=[x^r](1+x)^{n-m}sum_{k=0}^mbinom{m}{k}left(frac{x^2}{1+x}right)^ktag{2}\
&=[x^r](1+x)^{n-m}left(1+frac{x^2}{1+x}right)^mtag{3}\
&,,color{blue}{=[x^r](1+x)^{n-2m}left(1+x+x^2right)^m}
end{align*}
and we conclude
begin{align*}
sum_{r=0}^inftyleft(sum_{k=0}^mbinom{m}{k}binom{n-m-k}{r-2k}right)x^r
=(1+x)^{n-2m}left(1+x+x^2right)^m
end{align*}
Comment:
In (1) we apply the coefficient of operator.
In (2) we factor out terms independent of $k$ by using the linearity of the coefficient of operator and applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.
In (3) we apply the binomial theorem.
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
$endgroup$
add a comment |
$begingroup$
Here we use the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^n
end{align*}
We obtain for non-negative integers $ngeq 2m$ and $rgeq 0$:
begin{align*}
color{blue}{sum_{k=0}^m}&color{blue}{binom{m}{k}binom{n-m-k}{r-2k}}\
&=sum_{k=0}^mbinom{m}{k}[x^{r-2k}](1+x)^{n-m-k}tag{1}\
&=[x^r](1+x)^{n-m}sum_{k=0}^mbinom{m}{k}left(frac{x^2}{1+x}right)^ktag{2}\
&=[x^r](1+x)^{n-m}left(1+frac{x^2}{1+x}right)^mtag{3}\
&,,color{blue}{=[x^r](1+x)^{n-2m}left(1+x+x^2right)^m}
end{align*}
and we conclude
begin{align*}
sum_{r=0}^inftyleft(sum_{k=0}^mbinom{m}{k}binom{n-m-k}{r-2k}right)x^r
=(1+x)^{n-2m}left(1+x+x^2right)^m
end{align*}
Comment:
In (1) we apply the coefficient of operator.
In (2) we factor out terms independent of $k$ by using the linearity of the coefficient of operator and applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.
In (3) we apply the binomial theorem.
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
$endgroup$
Here we use the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^n
end{align*}
We obtain for non-negative integers $ngeq 2m$ and $rgeq 0$:
begin{align*}
color{blue}{sum_{k=0}^m}&color{blue}{binom{m}{k}binom{n-m-k}{r-2k}}\
&=sum_{k=0}^mbinom{m}{k}[x^{r-2k}](1+x)^{n-m-k}tag{1}\
&=[x^r](1+x)^{n-m}sum_{k=0}^mbinom{m}{k}left(frac{x^2}{1+x}right)^ktag{2}\
&=[x^r](1+x)^{n-m}left(1+frac{x^2}{1+x}right)^mtag{3}\
&,,color{blue}{=[x^r](1+x)^{n-2m}left(1+x+x^2right)^m}
end{align*}
and we conclude
begin{align*}
sum_{r=0}^inftyleft(sum_{k=0}^mbinom{m}{k}binom{n-m-k}{r-2k}right)x^r
=(1+x)^{n-2m}left(1+x+x^2right)^m
end{align*}
Comment:
In (1) we apply the coefficient of operator.
In (2) we factor out terms independent of $k$ by using the linearity of the coefficient of operator and applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.
In (3) we apply the binomial theorem.
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
edited Jan 14 at 17:08
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
answered Jan 14 at 16:53
Markus ScheuerMarkus Scheuer
61.7k457147
61.7k457147
add a comment |
add a comment |
$begingroup$
On one hand $$(1+t+t^2)^m=sum_{i=0}^mbinom{m}{i}(1+t)^i(t^2)^{m-i}=sum_{i=0}^mbinom{m}{i}Biggl(sum _{j=0}^ibinom{i}{j}t^j1^{i-j}Biggr)t^{2m-2i}=\sum_{i=0}^msum _{j=0}^ibinom{m}{i}binom{i}{j}t^{j+2m-2i}$$
On the other $$(1+t)^{n-2m}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k1^{n-2m-k}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k$$
Now, let's look at the sum representation we found for $(1+t+t^2)^m$ first (since it's the scarier looking one) and try to simplify it. Suppose we can rewrite this sum as $$sum_pa_pt^p$$ That would be very convenient as this is a nice single sum rather than a double sum. To do that, we need to find $a_p$ in general. Looking at the original double sum we can see that we can find $a_p$ by finding all pairs of $j$ and $i$ such that $jleq i$ and $j+2m-2i=p$- then, calculate for each pair, $binom{m}{i}binom{i}{j}$, and sum all of these binomial products up. Suppose for our (fixed) $p$ we also fixed $i$ at some value between $0$ and $m$. Well, in that case $j$ could take on at most one value- that would be $p+2i-2m$. We say "at most" because $j$ also needs to be $leq i$, i.e., $p+2i-2mleq iimplies ileq 2m-p$. Don't forget though that $j$ also has to be $geq 0$- this means $p+2i-2mgeq 0implies igeq m-frac{p}{2}$ ($j$ will always be an integer so we won't worry about that). So if we vary $i$ between $0$ and $m$, $i$ contributes to the coefficient, $a_p$, iff $m-frac{p}{2}leq ileq 2m-p$, and when that is the case, $i$ contributes exactly $binom{m}{i}binom{i}{p+2i-2m}$ to $a_p$.
In other words, $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
What are the possible values $p$ can take? Well, for each $p$ there must exist $i$ and $j$ in the original double sum's index so that $p=j+2m-2i$ so $p=j+2m-2ileq i+2m-2i=2m-ileq 2m$. Also $p=j+2m-2igeq 0+2m-2i=2m-2igeq 2m-2m=0$. So $p$ ranges from $0$ to $2m$.
Overall we have that $$(1+t+t^2)^m=sum_{p=0}^{2m}a_pt^p$$ where, for each $p$ $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
Time to tackle the big boi.
Now we need to find a nice single sum representation for $(1+t+t^2)^m(1+t)^{n-2m}$. Well, we have a nice(ish) single sum for each of the terms individually- let's try smashing them together.
$$(1+t+t^2)^m(1+t)^{n-2m}=Biggl(sum_{p=0}^{2m}a_pt^pBiggr)Biggl(sum_{k=0}^{n-2m}binom{n-2m}{k}t^kBiggr)=sum_{p=0}^{2m}sum_{k=0}^{n-2m}a_pbinom{n-2m}{k}t^{p+k}$$
Now, we run the same trick again and suppose that this double sum has some single sum expression like $$sum_qb_qt^q$$
To find $b_q$ here, we need find pairs of $p$ and $k$ such that $p+k=q$, $0leq pleq 2m$, and $0leq kleq n-2m$. Now, suppose we fix some $p$ between $0$ and $2m$. Then $k$, again, has at most one value, i.e, $q-p$, and this one value is only valid if $0leq kleq n-2m implies 0leq q-p leq n-2m implies q-n-2mleq pleq q$. This gives us that $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
Again, we can refer to the initial double sum to see that $p+k$ will always vary between $0$ and $n$, so $q$ varies between $0$ and $n$.
This all means: $$(1+t+t^2)^m(1+t)^{n-2m}=sum_{q=0}^nb_qt^q$$
where, for each $q$ $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
The $b_q$ are the coefficients we desire. To simplify (it's really just making things messier) plug in the general single sum expression for $a_p$ $$b_q=sum_{p=q-n-2m}^qBiggl(sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}Biggr)binom{n-2m}{q-p}=\sum_{p=q-n-2m}^qsum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}binom{n-2m}{q-p}$$
After some checking now, I'm pretty sure the working is correct but given the number of mistakes I made writing this, there's still a good chance I messed up somewhere. Regardless, this is basically how you can find the coefficients in general. You'll always end up with a double sum, like the final expression for $b_q$, so you'll probably need to pull out some nifty binomial identities or something to simplify it down to the single sum your question asks for. Or just look at Markus' way simpler answer.
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
$endgroup$
add a comment |
$begingroup$
On one hand $$(1+t+t^2)^m=sum_{i=0}^mbinom{m}{i}(1+t)^i(t^2)^{m-i}=sum_{i=0}^mbinom{m}{i}Biggl(sum _{j=0}^ibinom{i}{j}t^j1^{i-j}Biggr)t^{2m-2i}=\sum_{i=0}^msum _{j=0}^ibinom{m}{i}binom{i}{j}t^{j+2m-2i}$$
On the other $$(1+t)^{n-2m}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k1^{n-2m-k}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k$$
Now, let's look at the sum representation we found for $(1+t+t^2)^m$ first (since it's the scarier looking one) and try to simplify it. Suppose we can rewrite this sum as $$sum_pa_pt^p$$ That would be very convenient as this is a nice single sum rather than a double sum. To do that, we need to find $a_p$ in general. Looking at the original double sum we can see that we can find $a_p$ by finding all pairs of $j$ and $i$ such that $jleq i$ and $j+2m-2i=p$- then, calculate for each pair, $binom{m}{i}binom{i}{j}$, and sum all of these binomial products up. Suppose for our (fixed) $p$ we also fixed $i$ at some value between $0$ and $m$. Well, in that case $j$ could take on at most one value- that would be $p+2i-2m$. We say "at most" because $j$ also needs to be $leq i$, i.e., $p+2i-2mleq iimplies ileq 2m-p$. Don't forget though that $j$ also has to be $geq 0$- this means $p+2i-2mgeq 0implies igeq m-frac{p}{2}$ ($j$ will always be an integer so we won't worry about that). So if we vary $i$ between $0$ and $m$, $i$ contributes to the coefficient, $a_p$, iff $m-frac{p}{2}leq ileq 2m-p$, and when that is the case, $i$ contributes exactly $binom{m}{i}binom{i}{p+2i-2m}$ to $a_p$.
In other words, $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
What are the possible values $p$ can take? Well, for each $p$ there must exist $i$ and $j$ in the original double sum's index so that $p=j+2m-2i$ so $p=j+2m-2ileq i+2m-2i=2m-ileq 2m$. Also $p=j+2m-2igeq 0+2m-2i=2m-2igeq 2m-2m=0$. So $p$ ranges from $0$ to $2m$.
Overall we have that $$(1+t+t^2)^m=sum_{p=0}^{2m}a_pt^p$$ where, for each $p$ $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
Time to tackle the big boi.
Now we need to find a nice single sum representation for $(1+t+t^2)^m(1+t)^{n-2m}$. Well, we have a nice(ish) single sum for each of the terms individually- let's try smashing them together.
$$(1+t+t^2)^m(1+t)^{n-2m}=Biggl(sum_{p=0}^{2m}a_pt^pBiggr)Biggl(sum_{k=0}^{n-2m}binom{n-2m}{k}t^kBiggr)=sum_{p=0}^{2m}sum_{k=0}^{n-2m}a_pbinom{n-2m}{k}t^{p+k}$$
Now, we run the same trick again and suppose that this double sum has some single sum expression like $$sum_qb_qt^q$$
To find $b_q$ here, we need find pairs of $p$ and $k$ such that $p+k=q$, $0leq pleq 2m$, and $0leq kleq n-2m$. Now, suppose we fix some $p$ between $0$ and $2m$. Then $k$, again, has at most one value, i.e, $q-p$, and this one value is only valid if $0leq kleq n-2m implies 0leq q-p leq n-2m implies q-n-2mleq pleq q$. This gives us that $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
Again, we can refer to the initial double sum to see that $p+k$ will always vary between $0$ and $n$, so $q$ varies between $0$ and $n$.
This all means: $$(1+t+t^2)^m(1+t)^{n-2m}=sum_{q=0}^nb_qt^q$$
where, for each $q$ $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
The $b_q$ are the coefficients we desire. To simplify (it's really just making things messier) plug in the general single sum expression for $a_p$ $$b_q=sum_{p=q-n-2m}^qBiggl(sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}Biggr)binom{n-2m}{q-p}=\sum_{p=q-n-2m}^qsum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}binom{n-2m}{q-p}$$
After some checking now, I'm pretty sure the working is correct but given the number of mistakes I made writing this, there's still a good chance I messed up somewhere. Regardless, this is basically how you can find the coefficients in general. You'll always end up with a double sum, like the final expression for $b_q$, so you'll probably need to pull out some nifty binomial identities or something to simplify it down to the single sum your question asks for. Or just look at Markus' way simpler answer.
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
$endgroup$
add a comment |
$begingroup$
On one hand $$(1+t+t^2)^m=sum_{i=0}^mbinom{m}{i}(1+t)^i(t^2)^{m-i}=sum_{i=0}^mbinom{m}{i}Biggl(sum _{j=0}^ibinom{i}{j}t^j1^{i-j}Biggr)t^{2m-2i}=\sum_{i=0}^msum _{j=0}^ibinom{m}{i}binom{i}{j}t^{j+2m-2i}$$
On the other $$(1+t)^{n-2m}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k1^{n-2m-k}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k$$
Now, let's look at the sum representation we found for $(1+t+t^2)^m$ first (since it's the scarier looking one) and try to simplify it. Suppose we can rewrite this sum as $$sum_pa_pt^p$$ That would be very convenient as this is a nice single sum rather than a double sum. To do that, we need to find $a_p$ in general. Looking at the original double sum we can see that we can find $a_p$ by finding all pairs of $j$ and $i$ such that $jleq i$ and $j+2m-2i=p$- then, calculate for each pair, $binom{m}{i}binom{i}{j}$, and sum all of these binomial products up. Suppose for our (fixed) $p$ we also fixed $i$ at some value between $0$ and $m$. Well, in that case $j$ could take on at most one value- that would be $p+2i-2m$. We say "at most" because $j$ also needs to be $leq i$, i.e., $p+2i-2mleq iimplies ileq 2m-p$. Don't forget though that $j$ also has to be $geq 0$- this means $p+2i-2mgeq 0implies igeq m-frac{p}{2}$ ($j$ will always be an integer so we won't worry about that). So if we vary $i$ between $0$ and $m$, $i$ contributes to the coefficient, $a_p$, iff $m-frac{p}{2}leq ileq 2m-p$, and when that is the case, $i$ contributes exactly $binom{m}{i}binom{i}{p+2i-2m}$ to $a_p$.
In other words, $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
What are the possible values $p$ can take? Well, for each $p$ there must exist $i$ and $j$ in the original double sum's index so that $p=j+2m-2i$ so $p=j+2m-2ileq i+2m-2i=2m-ileq 2m$. Also $p=j+2m-2igeq 0+2m-2i=2m-2igeq 2m-2m=0$. So $p$ ranges from $0$ to $2m$.
Overall we have that $$(1+t+t^2)^m=sum_{p=0}^{2m}a_pt^p$$ where, for each $p$ $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
Time to tackle the big boi.
Now we need to find a nice single sum representation for $(1+t+t^2)^m(1+t)^{n-2m}$. Well, we have a nice(ish) single sum for each of the terms individually- let's try smashing them together.
$$(1+t+t^2)^m(1+t)^{n-2m}=Biggl(sum_{p=0}^{2m}a_pt^pBiggr)Biggl(sum_{k=0}^{n-2m}binom{n-2m}{k}t^kBiggr)=sum_{p=0}^{2m}sum_{k=0}^{n-2m}a_pbinom{n-2m}{k}t^{p+k}$$
Now, we run the same trick again and suppose that this double sum has some single sum expression like $$sum_qb_qt^q$$
To find $b_q$ here, we need find pairs of $p$ and $k$ such that $p+k=q$, $0leq pleq 2m$, and $0leq kleq n-2m$. Now, suppose we fix some $p$ between $0$ and $2m$. Then $k$, again, has at most one value, i.e, $q-p$, and this one value is only valid if $0leq kleq n-2m implies 0leq q-p leq n-2m implies q-n-2mleq pleq q$. This gives us that $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
Again, we can refer to the initial double sum to see that $p+k$ will always vary between $0$ and $n$, so $q$ varies between $0$ and $n$.
This all means: $$(1+t+t^2)^m(1+t)^{n-2m}=sum_{q=0}^nb_qt^q$$
where, for each $q$ $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
The $b_q$ are the coefficients we desire. To simplify (it's really just making things messier) plug in the general single sum expression for $a_p$ $$b_q=sum_{p=q-n-2m}^qBiggl(sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}Biggr)binom{n-2m}{q-p}=\sum_{p=q-n-2m}^qsum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}binom{n-2m}{q-p}$$
After some checking now, I'm pretty sure the working is correct but given the number of mistakes I made writing this, there's still a good chance I messed up somewhere. Regardless, this is basically how you can find the coefficients in general. You'll always end up with a double sum, like the final expression for $b_q$, so you'll probably need to pull out some nifty binomial identities or something to simplify it down to the single sum your question asks for. Or just look at Markus' way simpler answer.
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
$endgroup$
On one hand $$(1+t+t^2)^m=sum_{i=0}^mbinom{m}{i}(1+t)^i(t^2)^{m-i}=sum_{i=0}^mbinom{m}{i}Biggl(sum _{j=0}^ibinom{i}{j}t^j1^{i-j}Biggr)t^{2m-2i}=\sum_{i=0}^msum _{j=0}^ibinom{m}{i}binom{i}{j}t^{j+2m-2i}$$
On the other $$(1+t)^{n-2m}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k1^{n-2m-k}=sum_{k=0}^{n-2m}binom{n-2m}{k}t^k$$
Now, let's look at the sum representation we found for $(1+t+t^2)^m$ first (since it's the scarier looking one) and try to simplify it. Suppose we can rewrite this sum as $$sum_pa_pt^p$$ That would be very convenient as this is a nice single sum rather than a double sum. To do that, we need to find $a_p$ in general. Looking at the original double sum we can see that we can find $a_p$ by finding all pairs of $j$ and $i$ such that $jleq i$ and $j+2m-2i=p$- then, calculate for each pair, $binom{m}{i}binom{i}{j}$, and sum all of these binomial products up. Suppose for our (fixed) $p$ we also fixed $i$ at some value between $0$ and $m$. Well, in that case $j$ could take on at most one value- that would be $p+2i-2m$. We say "at most" because $j$ also needs to be $leq i$, i.e., $p+2i-2mleq iimplies ileq 2m-p$. Don't forget though that $j$ also has to be $geq 0$- this means $p+2i-2mgeq 0implies igeq m-frac{p}{2}$ ($j$ will always be an integer so we won't worry about that). So if we vary $i$ between $0$ and $m$, $i$ contributes to the coefficient, $a_p$, iff $m-frac{p}{2}leq ileq 2m-p$, and when that is the case, $i$ contributes exactly $binom{m}{i}binom{i}{p+2i-2m}$ to $a_p$.
In other words, $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
What are the possible values $p$ can take? Well, for each $p$ there must exist $i$ and $j$ in the original double sum's index so that $p=j+2m-2i$ so $p=j+2m-2ileq i+2m-2i=2m-ileq 2m$. Also $p=j+2m-2igeq 0+2m-2i=2m-2igeq 2m-2m=0$. So $p$ ranges from $0$ to $2m$.
Overall we have that $$(1+t+t^2)^m=sum_{p=0}^{2m}a_pt^p$$ where, for each $p$ $$a_p=sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}$$
Time to tackle the big boi.
Now we need to find a nice single sum representation for $(1+t+t^2)^m(1+t)^{n-2m}$. Well, we have a nice(ish) single sum for each of the terms individually- let's try smashing them together.
$$(1+t+t^2)^m(1+t)^{n-2m}=Biggl(sum_{p=0}^{2m}a_pt^pBiggr)Biggl(sum_{k=0}^{n-2m}binom{n-2m}{k}t^kBiggr)=sum_{p=0}^{2m}sum_{k=0}^{n-2m}a_pbinom{n-2m}{k}t^{p+k}$$
Now, we run the same trick again and suppose that this double sum has some single sum expression like $$sum_qb_qt^q$$
To find $b_q$ here, we need find pairs of $p$ and $k$ such that $p+k=q$, $0leq pleq 2m$, and $0leq kleq n-2m$. Now, suppose we fix some $p$ between $0$ and $2m$. Then $k$, again, has at most one value, i.e, $q-p$, and this one value is only valid if $0leq kleq n-2m implies 0leq q-p leq n-2m implies q-n-2mleq pleq q$. This gives us that $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
Again, we can refer to the initial double sum to see that $p+k$ will always vary between $0$ and $n$, so $q$ varies between $0$ and $n$.
This all means: $$(1+t+t^2)^m(1+t)^{n-2m}=sum_{q=0}^nb_qt^q$$
where, for each $q$ $$b_q=sum_{p=q-n-2m}^qa_pbinom{n-2m}{q-p}$$
The $b_q$ are the coefficients we desire. To simplify (it's really just making things messier) plug in the general single sum expression for $a_p$ $$b_q=sum_{p=q-n-2m}^qBiggl(sum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}Biggr)binom{n-2m}{q-p}=\sum_{p=q-n-2m}^qsum_{i=m-lfloorfrac{p}{2}rfloor}^{2m-p}binom{m}{i}binom{i}{p+2i-2m}binom{n-2m}{q-p}$$
After some checking now, I'm pretty sure the working is correct but given the number of mistakes I made writing this, there's still a good chance I messed up somewhere. Regardless, this is basically how you can find the coefficients in general. You'll always end up with a double sum, like the final expression for $b_q$, so you'll probably need to pull out some nifty binomial identities or something to simplify it down to the single sum your question asks for. Or just look at Markus' way simpler answer.
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
answered Jan 14 at 18:24
Cardioid_Ass_22Cardioid_Ass_22
38814
38814
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3073258%2fstuck-at-finding-coefficients-of-generating-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Actually, I am not sure what you mean by "r-combinations of specification $2^m1^{n-2m}$" (This may very well be due to my limited knowledge). Can you please pose the combinatorial question in words?
$endgroup$
– Anubhab Ghosal
Jan 14 at 14:35
$begingroup$
@AnubhabGhosal 'r-combinations' means combinations of r elements and the particular specfication given here means objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:40
$begingroup$
What do you mean when you say "objects of m kind with 2 of each kind"? Do you mean that there are 2m objects where each object has an identical partner?
$endgroup$
– Cardioid_Ass_22
Jan 14 at 14:52
$begingroup$
@Cardioid_Ass_22 yes
$endgroup$
– Shubhraneel Pal
Jan 14 at 14:54
$begingroup$
Maybe use $1+t+t^2=(1-t^3)/(1-t)$?
$endgroup$
– marty cohen
Jan 14 at 14:59