Looking for a proof for this counting problem
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
|
show 4 more comments
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 '18 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 '18 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 '18 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 '18 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 '18 at 4:47
|
show 4 more comments
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
combinatorics
edited Dec 2 '18 at 21:46
LutzL
56k42054
56k42054
asked Dec 2 '18 at 17:41
rsadhvika
1,6631228
1,6631228
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 '18 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 '18 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 '18 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 '18 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 '18 at 4:47
|
show 4 more comments
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 '18 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 '18 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 '18 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 '18 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 '18 at 4:47
1
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 '18 at 17:46
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 '18 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 '18 at 17:49
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 '18 at 17:49
1
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 '18 at 17:49
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 '18 at 17:49
1
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 '18 at 0:31
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 '18 at 0:31
1
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 '18 at 4:47
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 '18 at 4:47
|
show 4 more comments
3 Answers
3
active
oldest
votes
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 '18 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 '18 at 18:05
add a comment |
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 '18 at 21:46
add a comment |
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
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%2f3022949%2flooking-for-a-proof-for-this-counting-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 '18 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 '18 at 18:05
add a comment |
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 '18 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 '18 at 18:05
add a comment |
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
edited Dec 2 '18 at 18:06
answered Dec 2 '18 at 17:47
Boshu
705315
705315
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 '18 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 '18 at 18:05
add a comment |
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 '18 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 '18 at 18:05
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 '18 at 18:01
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 '18 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 '18 at 18:05
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 '18 at 18:05
add a comment |
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 '18 at 21:46
add a comment |
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 '18 at 21:46
add a comment |
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
answered Dec 2 '18 at 17:51
John_Wick
1,366111
1,366111
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 '18 at 21:46
add a comment |
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 '18 at 21:46
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 '18 at 21:46
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 '18 at 21:46
add a comment |
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
add a comment |
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
add a comment |
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
edited Dec 2 '18 at 17:58
answered Dec 2 '18 at 17:51
Yves Daoust
124k671221
124k671221
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3022949%2flooking-for-a-proof-for-this-counting-problem%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
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 '18 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 '18 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 '18 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 '18 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 '18 at 4:47