Polynomial expression for $frac 1{2^n} sum_{i=0}^n binom{n}{i}(2i-n)^{2k}$
$begingroup$
Let
$$F (n,k)=frac {1}{2^n}sum_{i=0}^n binom{n}{i}(2i-n)^{2k},$$
where $n,k$ are non-negative integers.
By numerical tests the expression is an integer polynomial in $n $ of order $k $:
$$ F(n,0)=1;
F (n,1)=n;
F (n,2)=n (3n-2),$$
and so on.
Is there a simple general expression for the polynomial?
sequences-and-series combinatorics
asked Dec 9 '18 at 18:08
useruser
3,9051627
$endgroup$
|
show 2 more comments
$begingroup$
Let
$$F (n,k)=frac {1}{2^n}sum_{i=0}^n binom{n}{i}(2i-n)^{2k},$$
where $n,k$ are non-negative integers.
By numerical tests the expression is an integer polynomial in $n $ of order $k $:
$$ F(n,0)=1;
F (n,1)=n;
F (n,2)=n (3n-2),$$
and so on.
Is there a simple general expression for the polynomial?
sequences-and-series combinatorics
asked Dec 9 '18 at 18:08
useruser
3,9051627
$endgroup$
$begingroup$
That is a closed form. The sum is finite. I'd try expanding $(2i-n)^{2k}$ or computing some values and plugging them in into OEIS, in any case.
$endgroup$
– ajotatxe
Dec 9 '18 at 18:10
$begingroup$
@ajotatxe I have edited the question to clarify what I meant by "closed - form expression".
$endgroup$
– user
Dec 9 '18 at 19:30
1
$begingroup$
This expression comes out in Exercise 7 of UMN Fall 2018 Math 5705 Homework set 4, and also in Corollary 2.5 of Stanley's Algebraic Combinatorics (but these two appearances are actually easily seen to be equivalent: a closed walk of length $n$ on the hypercube is uniquely determined by its starting point and the $n$-tuple of "signless step directions", which $n$-tuple is clearly all-even).
$endgroup$
– darij grinberg
Dec 11 '18 at 3:16
1
$begingroup$
If there is a closed form, then Stanley could not find it. On the other hand, the polynomial claim is interesting.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:18
1
$begingroup$
Ah, I see why it is a polynomial. You can count the all-even $k$-tuples in $left[nright]^k$ according to the positions of equal entries (more formally: the set partition of $left[kright]$ that governs which of the entries of the tuple are equal). For any given such choice of positions, the number of tuples is a polynomial in $n$ with degree $k$ (namely, a power of $n$ times a power of $n-1$ times a power of $n-2$ and so on). Feel free to expand on this in an answer -- I am stuck in bed with a flu and not at my most productive.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:45
|
show 2 more comments
$begingroup$
Let
$$F (n,k)=frac {1}{2^n}sum_{i=0}^n binom{n}{i}(2i-n)^{2k},$$
where $n,k$ are non-negative integers.
By numerical tests the expression is an integer polynomial in $n $ of order $k $:
$$ F(n,0)=1;
F (n,1)=n;
F (n,2)=n (3n-2),$$
and so on.
Is there a simple general expression for the polynomial?
sequences-and-series combinatorics
asked Dec 9 '18 at 18:08
useruser
3,9051627
$endgroup$
Let
$$F (n,k)=frac {1}{2^n}sum_{i=0}^n binom{n}{i}(2i-n)^{2k},$$
where $n,k$ are non-negative integers.
By numerical tests the expression is an integer polynomial in $n $ of order $k $:
$$ F(n,0)=1;
F (n,1)=n;
F (n,2)=n (3n-2),$$
and so on.
Is there a simple general expression for the polynomial?
sequences-and-series combinatorics
sequences-and-series combinatorics
asked Dec 9 '18 at 18:08
useruser
3,9051627
asked Dec 9 '18 at 18:08
useruser
3,9051627
edited Dec 13 '18 at 6:06
user
asked Dec 9 '18 at 18:08
useruser
3,9051627
asked Dec 9 '18 at 18:08
useruser
3,9051627
asked Dec 9 '18 at 18:08
useruser
3,9051627
3,9051627
$begingroup$
That is a closed form. The sum is finite. I'd try expanding $(2i-n)^{2k}$ or computing some values and plugging them in into OEIS, in any case.
$endgroup$
– ajotatxe
Dec 9 '18 at 18:10
$begingroup$
@ajotatxe I have edited the question to clarify what I meant by "closed - form expression".
$endgroup$
– user
Dec 9 '18 at 19:30
1
$begingroup$
This expression comes out in Exercise 7 of UMN Fall 2018 Math 5705 Homework set 4, and also in Corollary 2.5 of Stanley's Algebraic Combinatorics (but these two appearances are actually easily seen to be equivalent: a closed walk of length $n$ on the hypercube is uniquely determined by its starting point and the $n$-tuple of "signless step directions", which $n$-tuple is clearly all-even).
$endgroup$
– darij grinberg
Dec 11 '18 at 3:16
1
$begingroup$
If there is a closed form, then Stanley could not find it. On the other hand, the polynomial claim is interesting.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:18
1
$begingroup$
Ah, I see why it is a polynomial. You can count the all-even $k$-tuples in $left[nright]^k$ according to the positions of equal entries (more formally: the set partition of $left[kright]$ that governs which of the entries of the tuple are equal). For any given such choice of positions, the number of tuples is a polynomial in $n$ with degree $k$ (namely, a power of $n$ times a power of $n-1$ times a power of $n-2$ and so on). Feel free to expand on this in an answer -- I am stuck in bed with a flu and not at my most productive.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:45
|
show 2 more comments
$begingroup$
That is a closed form. The sum is finite. I'd try expanding $(2i-n)^{2k}$ or computing some values and plugging them in into OEIS, in any case.
$endgroup$
– ajotatxe
Dec 9 '18 at 18:10
$begingroup$
@ajotatxe I have edited the question to clarify what I meant by "closed - form expression".
$endgroup$
– user
Dec 9 '18 at 19:30
1
$begingroup$
This expression comes out in Exercise 7 of UMN Fall 2018 Math 5705 Homework set 4, and also in Corollary 2.5 of Stanley's Algebraic Combinatorics (but these two appearances are actually easily seen to be equivalent: a closed walk of length $n$ on the hypercube is uniquely determined by its starting point and the $n$-tuple of "signless step directions", which $n$-tuple is clearly all-even).
$endgroup$
– darij grinberg
Dec 11 '18 at 3:16
1
$begingroup$
If there is a closed form, then Stanley could not find it. On the other hand, the polynomial claim is interesting.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:18
1
$begingroup$
Ah, I see why it is a polynomial. You can count the all-even $k$-tuples in $left[nright]^k$ according to the positions of equal entries (more formally: the set partition of $left[kright]$ that governs which of the entries of the tuple are equal). For any given such choice of positions, the number of tuples is a polynomial in $n$ with degree $k$ (namely, a power of $n$ times a power of $n-1$ times a power of $n-2$ and so on). Feel free to expand on this in an answer -- I am stuck in bed with a flu and not at my most productive.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:45
$begingroup$
That is a closed form. The sum is finite. I'd try expanding $(2i-n)^{2k}$ or computing some values and plugging them in into OEIS, in any case.
$endgroup$
– ajotatxe
Dec 9 '18 at 18:10
$begingroup$
That is a closed form. The sum is finite. I'd try expanding $(2i-n)^{2k}$ or computing some values and plugging them in into OEIS, in any case.
$endgroup$
– ajotatxe
Dec 9 '18 at 18:10
$begingroup$
@ajotatxe I have edited the question to clarify what I meant by "closed - form expression".
$endgroup$
– user
Dec 9 '18 at 19:30
$begingroup$
@ajotatxe I have edited the question to clarify what I meant by "closed - form expression".
$endgroup$
– user
Dec 9 '18 at 19:30
1
1
$begingroup$
This expression comes out in Exercise 7 of UMN Fall 2018 Math 5705 Homework set 4, and also in Corollary 2.5 of Stanley's Algebraic Combinatorics (but these two appearances are actually easily seen to be equivalent: a closed walk of length $n$ on the hypercube is uniquely determined by its starting point and the $n$-tuple of "signless step directions", which $n$-tuple is clearly all-even).
$endgroup$
– darij grinberg
Dec 11 '18 at 3:16
$begingroup$
This expression comes out in Exercise 7 of UMN Fall 2018 Math 5705 Homework set 4, and also in Corollary 2.5 of Stanley's Algebraic Combinatorics (but these two appearances are actually easily seen to be equivalent: a closed walk of length $n$ on the hypercube is uniquely determined by its starting point and the $n$-tuple of "signless step directions", which $n$-tuple is clearly all-even).
$endgroup$
– darij grinberg
Dec 11 '18 at 3:16
1
1
$begingroup$
If there is a closed form, then Stanley could not find it. On the other hand, the polynomial claim is interesting.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:18
$begingroup$
If there is a closed form, then Stanley could not find it. On the other hand, the polynomial claim is interesting.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:18
1
1
$begingroup$
Ah, I see why it is a polynomial. You can count the all-even $k$-tuples in $left[nright]^k$ according to the positions of equal entries (more formally: the set partition of $left[kright]$ that governs which of the entries of the tuple are equal). For any given such choice of positions, the number of tuples is a polynomial in $n$ with degree $k$ (namely, a power of $n$ times a power of $n-1$ times a power of $n-2$ and so on). Feel free to expand on this in an answer -- I am stuck in bed with a flu and not at my most productive.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:45
$begingroup$
Ah, I see why it is a polynomial. You can count the all-even $k$-tuples in $left[nright]^k$ according to the positions of equal entries (more formally: the set partition of $left[kright]$ that governs which of the entries of the tuple are equal). For any given such choice of positions, the number of tuples is a polynomial in $n$ with degree $k$ (namely, a power of $n$ times a power of $n-1$ times a power of $n-2$ and so on). Feel free to expand on this in an answer -- I am stuck in bed with a flu and not at my most productive.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:45
|
show 2 more comments
3 Answers
3
active
oldest
votes
$begingroup$
It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
begin{align*}
n![z^n]e^{jz}=j^ntag{1}
end{align*}
We obtain
begin{align*}
color{blue}{frac{1}{2^n}}&color{blue}{sum_{j=0}^nbinom{n}{j}(2j-n)^{2k}}\
&=frac{1}{2^n}sum_{j=0}^nbinom{n}{j}(2k)![z^{2k}]e^{(2j-n)z}tag{2}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}sum_{j=0}^nbinom{n}{j}left(e^{2z}right)^jtag{3}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}left(1+e^{2z}right)^ntag{4}\
&=(2k)![z^{2k}]left(frac{e^{z}+e^{-z}}{2}right)^ntag{5}\
&,,color{blue}{=(2k)![z^{2k}]left(cosh zright)^n}
end{align*}
We see OPs formula is essentially the coefficient of $z^{2k}$ of $left(cosh zright)^n$ which does not have a closed formula as far as I know.
Comment:
In (2) we apply the coefficient of operator according to (1).
In (3) use the linearity of the coefficient of operator.
In (4) we apply the binomial theorem.
In (5) we write the expression somewhat more conveniently.
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
$endgroup$
$begingroup$
I think I have found such a closed polynomial formula. See my answer below.
$endgroup$
– user
Dec 27 '18 at 12:06
$begingroup$
@user: A closed formula means there is no $Sigma$ involved. Somewhat more concrete a closed formula in this context is a function in $n$ with a constant number of terms. When using something like $Sigma_{j=0}^n$ the number of terms is not constant but increases with increasing $n$.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 14:05
$begingroup$
What was meant was a closed formula for the coefficients of the polynomial (which do not depend on $n $).
$endgroup$
– user
Dec 27 '18 at 16:14
$begingroup$
@user: I agree, you're right. (+1) for your nice approach.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 16:27
add a comment |
$begingroup$
I'll play with the cosh and
see if I get
anything other than
the original problem.
$begin{array}\
cosh^n(x)
&=frac1{2^n}(e^x+e^{-x})^n\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}e^ke^{(n-k)x}\
&=frac1{2^n}e^{nx}sum_{k=0}^n binom{n}{k}e^{-2kx}\
&=frac1{2^n}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{k=0}^n binom{n}{k}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}sum_{i=0}^{m} dfrac{(nx)^i}{i!} dfrac{(-2kx)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}x^msum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{k=0}^n binom{n}{k}sum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{i=0}^{m}dfrac{(-2)^{m-i}(n)^i}{(m-i)!i!}sum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{i=0}^{m}binom{m}{i}(-2)^{m-i}n^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{i=0}^{m}binom{m}{i}(-n/2)^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}sum_{i=0}^{m}binom{m}{i}(-n/2)^i k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}(-n/2+k)^m\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{k=0}^n binom{n}{k}(2k-n)^m\
end{array}
$
And this is the OP.
Oh well.
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
$endgroup$
add a comment |
$begingroup$
Let $omega $ be a $n$-dimensional vector with binary components $omega_i=pm1$ and $Omega_n $ be a set of all such vectors, the size of the set obviously being $2^n $. The sum of elements of a vector with $i$
positive and $n-i $ negative components is $2i-n $ and the number of such vectors is $binom {n}{i}$. Thus
$$
F (n,k)=frac {1}{2^n}sum_{omegainOmega_n } left (sum_{i=1}^nomega_i right)^{2k}
=frac {1}{2^n}sum_{omegainOmega_n } sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}prod_i omega_i^{p_i}
=sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}left (frac {1}{2^n}sum_{omegainOmega_n }prod_i omega_i^{p_i}right)
=sum_{p_ige0,;p_i,text {mod},2=0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}.
$$
To proceed further one splits the last sum into partial ones over terms with particular count $l$ of non-zero $p_i$ and ends up with:
$$
F (n,k)=sum_{l=1}^n T (k,l)n^underline{l},tag {1}
$$
where $T (k,l)$ is the number of partitions of a set of size $2k$ into $l$ blocks of even size, and $n^underline{l}$ is falling factorial. $T(k,l)$ can be recognized as the OEIS sequence A156289 with known close-form and recurrence expressions.
Note added: by numerical evidence the polynomial (1) can be expressed in the terms of usual powers as:
$$
F (n,k)=sum_{l=1}^n A (k,l)n^l,tag {2}
$$
with $A (k,l) $ being the OEIS sequence A318146. In other words $F(n,k) $ is in fact the so called Omega polynomial.
answered Dec 26 '18 at 19:53
useruser
3,9051627
$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%2f3032709%2fpolynomial-expression-for-frac-12n-sum-i-0n-binomni2i-n2k%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
$begingroup$
It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
begin{align*}
n![z^n]e^{jz}=j^ntag{1}
end{align*}
We obtain
begin{align*}
color{blue}{frac{1}{2^n}}&color{blue}{sum_{j=0}^nbinom{n}{j}(2j-n)^{2k}}\
&=frac{1}{2^n}sum_{j=0}^nbinom{n}{j}(2k)![z^{2k}]e^{(2j-n)z}tag{2}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}sum_{j=0}^nbinom{n}{j}left(e^{2z}right)^jtag{3}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}left(1+e^{2z}right)^ntag{4}\
&=(2k)![z^{2k}]left(frac{e^{z}+e^{-z}}{2}right)^ntag{5}\
&,,color{blue}{=(2k)![z^{2k}]left(cosh zright)^n}
end{align*}
We see OPs formula is essentially the coefficient of $z^{2k}$ of $left(cosh zright)^n$ which does not have a closed formula as far as I know.
Comment:
In (2) we apply the coefficient of operator according to (1).
In (3) use the linearity of the coefficient of operator.
In (4) we apply the binomial theorem.
In (5) we write the expression somewhat more conveniently.
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
$endgroup$
$begingroup$
I think I have found such a closed polynomial formula. See my answer below.
$endgroup$
– user
Dec 27 '18 at 12:06
$begingroup$
@user: A closed formula means there is no $Sigma$ involved. Somewhat more concrete a closed formula in this context is a function in $n$ with a constant number of terms. When using something like $Sigma_{j=0}^n$ the number of terms is not constant but increases with increasing $n$.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 14:05
$begingroup$
What was meant was a closed formula for the coefficients of the polynomial (which do not depend on $n $).
$endgroup$
– user
Dec 27 '18 at 16:14
$begingroup$
@user: I agree, you're right. (+1) for your nice approach.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 16:27
add a comment |
$begingroup$
It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
begin{align*}
n![z^n]e^{jz}=j^ntag{1}
end{align*}
We obtain
begin{align*}
color{blue}{frac{1}{2^n}}&color{blue}{sum_{j=0}^nbinom{n}{j}(2j-n)^{2k}}\
&=frac{1}{2^n}sum_{j=0}^nbinom{n}{j}(2k)![z^{2k}]e^{(2j-n)z}tag{2}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}sum_{j=0}^nbinom{n}{j}left(e^{2z}right)^jtag{3}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}left(1+e^{2z}right)^ntag{4}\
&=(2k)![z^{2k}]left(frac{e^{z}+e^{-z}}{2}right)^ntag{5}\
&,,color{blue}{=(2k)![z^{2k}]left(cosh zright)^n}
end{align*}
We see OPs formula is essentially the coefficient of $z^{2k}$ of $left(cosh zright)^n$ which does not have a closed formula as far as I know.
Comment:
In (2) we apply the coefficient of operator according to (1).
In (3) use the linearity of the coefficient of operator.
In (4) we apply the binomial theorem.
In (5) we write the expression somewhat more conveniently.
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
$endgroup$
$begingroup$
I think I have found such a closed polynomial formula. See my answer below.
$endgroup$
– user
Dec 27 '18 at 12:06
$begingroup$
@user: A closed formula means there is no $Sigma$ involved. Somewhat more concrete a closed formula in this context is a function in $n$ with a constant number of terms. When using something like $Sigma_{j=0}^n$ the number of terms is not constant but increases with increasing $n$.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 14:05
$begingroup$
What was meant was a closed formula for the coefficients of the polynomial (which do not depend on $n $).
$endgroup$
– user
Dec 27 '18 at 16:14
$begingroup$
@user: I agree, you're right. (+1) for your nice approach.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 16:27
add a comment |
$begingroup$
It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
begin{align*}
n![z^n]e^{jz}=j^ntag{1}
end{align*}
We obtain
begin{align*}
color{blue}{frac{1}{2^n}}&color{blue}{sum_{j=0}^nbinom{n}{j}(2j-n)^{2k}}\
&=frac{1}{2^n}sum_{j=0}^nbinom{n}{j}(2k)![z^{2k}]e^{(2j-n)z}tag{2}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}sum_{j=0}^nbinom{n}{j}left(e^{2z}right)^jtag{3}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}left(1+e^{2z}right)^ntag{4}\
&=(2k)![z^{2k}]left(frac{e^{z}+e^{-z}}{2}right)^ntag{5}\
&,,color{blue}{=(2k)![z^{2k}]left(cosh zright)^n}
end{align*}
We see OPs formula is essentially the coefficient of $z^{2k}$ of $left(cosh zright)^n$ which does not have a closed formula as far as I know.
Comment:
In (2) we apply the coefficient of operator according to (1).
In (3) use the linearity of the coefficient of operator.
In (4) we apply the binomial theorem.
In (5) we write the expression somewhat more conveniently.
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
$endgroup$
It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
begin{align*}
n![z^n]e^{jz}=j^ntag{1}
end{align*}
We obtain
begin{align*}
color{blue}{frac{1}{2^n}}&color{blue}{sum_{j=0}^nbinom{n}{j}(2j-n)^{2k}}\
&=frac{1}{2^n}sum_{j=0}^nbinom{n}{j}(2k)![z^{2k}]e^{(2j-n)z}tag{2}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}sum_{j=0}^nbinom{n}{j}left(e^{2z}right)^jtag{3}\
&=frac{(2k)!}{2^n}[z^{2k}]e^{-nz}left(1+e^{2z}right)^ntag{4}\
&=(2k)![z^{2k}]left(frac{e^{z}+e^{-z}}{2}right)^ntag{5}\
&,,color{blue}{=(2k)![z^{2k}]left(cosh zright)^n}
end{align*}
We see OPs formula is essentially the coefficient of $z^{2k}$ of $left(cosh zright)^n$ which does not have a closed formula as far as I know.
Comment:
In (2) we apply the coefficient of operator according to (1).
In (3) use the linearity of the coefficient of operator.
In (4) we apply the binomial theorem.
In (5) we write the expression somewhat more conveniently.
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
edited Dec 9 '18 at 19:53
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
answered Dec 9 '18 at 19:40
Markus ScheuerMarkus Scheuer
60.8k456145
60.8k456145
$begingroup$
I think I have found such a closed polynomial formula. See my answer below.
$endgroup$
– user
Dec 27 '18 at 12:06
$begingroup$
@user: A closed formula means there is no $Sigma$ involved. Somewhat more concrete a closed formula in this context is a function in $n$ with a constant number of terms. When using something like $Sigma_{j=0}^n$ the number of terms is not constant but increases with increasing $n$.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 14:05
$begingroup$
What was meant was a closed formula for the coefficients of the polynomial (which do not depend on $n $).
$endgroup$
– user
Dec 27 '18 at 16:14
$begingroup$
@user: I agree, you're right. (+1) for your nice approach.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 16:27
add a comment |
$begingroup$
I think I have found such a closed polynomial formula. See my answer below.
$endgroup$
– user
Dec 27 '18 at 12:06
$begingroup$
@user: A closed formula means there is no $Sigma$ involved. Somewhat more concrete a closed formula in this context is a function in $n$ with a constant number of terms. When using something like $Sigma_{j=0}^n$ the number of terms is not constant but increases with increasing $n$.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 14:05
$begingroup$
What was meant was a closed formula for the coefficients of the polynomial (which do not depend on $n $).
$endgroup$
– user
Dec 27 '18 at 16:14
$begingroup$
@user: I agree, you're right. (+1) for your nice approach.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 16:27
$begingroup$
I think I have found such a closed polynomial formula. See my answer below.
$endgroup$
– user
Dec 27 '18 at 12:06
$begingroup$
I think I have found such a closed polynomial formula. See my answer below.
$endgroup$
– user
Dec 27 '18 at 12:06
$begingroup$
@user: A closed formula means there is no $Sigma$ involved. Somewhat more concrete a closed formula in this context is a function in $n$ with a constant number of terms. When using something like $Sigma_{j=0}^n$ the number of terms is not constant but increases with increasing $n$.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 14:05
$begingroup$
@user: A closed formula means there is no $Sigma$ involved. Somewhat more concrete a closed formula in this context is a function in $n$ with a constant number of terms. When using something like $Sigma_{j=0}^n$ the number of terms is not constant but increases with increasing $n$.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 14:05
$begingroup$
What was meant was a closed formula for the coefficients of the polynomial (which do not depend on $n $).
$endgroup$
– user
Dec 27 '18 at 16:14
$begingroup$
What was meant was a closed formula for the coefficients of the polynomial (which do not depend on $n $).
$endgroup$
– user
Dec 27 '18 at 16:14
$begingroup$
@user: I agree, you're right. (+1) for your nice approach.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 16:27
$begingroup$
@user: I agree, you're right. (+1) for your nice approach.
$endgroup$
– Markus Scheuer
Dec 27 '18 at 16:27
add a comment |
$begingroup$
I'll play with the cosh and
see if I get
anything other than
the original problem.
$begin{array}\
cosh^n(x)
&=frac1{2^n}(e^x+e^{-x})^n\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}e^ke^{(n-k)x}\
&=frac1{2^n}e^{nx}sum_{k=0}^n binom{n}{k}e^{-2kx}\
&=frac1{2^n}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{k=0}^n binom{n}{k}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}sum_{i=0}^{m} dfrac{(nx)^i}{i!} dfrac{(-2kx)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}x^msum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{k=0}^n binom{n}{k}sum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{i=0}^{m}dfrac{(-2)^{m-i}(n)^i}{(m-i)!i!}sum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{i=0}^{m}binom{m}{i}(-2)^{m-i}n^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{i=0}^{m}binom{m}{i}(-n/2)^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}sum_{i=0}^{m}binom{m}{i}(-n/2)^i k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}(-n/2+k)^m\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{k=0}^n binom{n}{k}(2k-n)^m\
end{array}
$
And this is the OP.
Oh well.
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
$endgroup$
add a comment |
$begingroup$
I'll play with the cosh and
see if I get
anything other than
the original problem.
$begin{array}\
cosh^n(x)
&=frac1{2^n}(e^x+e^{-x})^n\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}e^ke^{(n-k)x}\
&=frac1{2^n}e^{nx}sum_{k=0}^n binom{n}{k}e^{-2kx}\
&=frac1{2^n}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{k=0}^n binom{n}{k}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}sum_{i=0}^{m} dfrac{(nx)^i}{i!} dfrac{(-2kx)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}x^msum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{k=0}^n binom{n}{k}sum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{i=0}^{m}dfrac{(-2)^{m-i}(n)^i}{(m-i)!i!}sum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{i=0}^{m}binom{m}{i}(-2)^{m-i}n^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{i=0}^{m}binom{m}{i}(-n/2)^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}sum_{i=0}^{m}binom{m}{i}(-n/2)^i k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}(-n/2+k)^m\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{k=0}^n binom{n}{k}(2k-n)^m\
end{array}
$
And this is the OP.
Oh well.
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
$endgroup$
add a comment |
$begingroup$
I'll play with the cosh and
see if I get
anything other than
the original problem.
$begin{array}\
cosh^n(x)
&=frac1{2^n}(e^x+e^{-x})^n\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}e^ke^{(n-k)x}\
&=frac1{2^n}e^{nx}sum_{k=0}^n binom{n}{k}e^{-2kx}\
&=frac1{2^n}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{k=0}^n binom{n}{k}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}sum_{i=0}^{m} dfrac{(nx)^i}{i!} dfrac{(-2kx)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}x^msum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{k=0}^n binom{n}{k}sum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{i=0}^{m}dfrac{(-2)^{m-i}(n)^i}{(m-i)!i!}sum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{i=0}^{m}binom{m}{i}(-2)^{m-i}n^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{i=0}^{m}binom{m}{i}(-n/2)^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}sum_{i=0}^{m}binom{m}{i}(-n/2)^i k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}(-n/2+k)^m\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{k=0}^n binom{n}{k}(2k-n)^m\
end{array}
$
And this is the OP.
Oh well.
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
$endgroup$
I'll play with the cosh and
see if I get
anything other than
the original problem.
$begin{array}\
cosh^n(x)
&=frac1{2^n}(e^x+e^{-x})^n\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}e^ke^{(n-k)x}\
&=frac1{2^n}e^{nx}sum_{k=0}^n binom{n}{k}e^{-2kx}\
&=frac1{2^n}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{k=0}^n binom{n}{k}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{i=0}^{infty} dfrac{(nx)^i}{i!}sum_{j=0}^{infty} dfrac{(-2kx)^j}{j!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}sum_{i=0}^{m} dfrac{(nx)^i}{i!} dfrac{(-2kx)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{k=0}^n binom{n}{k}sum_{m=0}^{infty}x^msum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{k=0}^n binom{n}{k}sum_{i=0}^{m} dfrac{(n)^i}{i!} dfrac{(-2k)^{m-i}}{(m-i)!}\
&=frac1{2^n}sum_{m=0}^{infty}x^msum_{i=0}^{m}dfrac{(-2)^{m-i}(n)^i}{(m-i)!i!}sum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{i=0}^{m}binom{m}{i}(-2)^{m-i}n^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{i=0}^{m}binom{m}{i}(-n/2)^isum_{k=0}^n binom{n}{k} k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}sum_{i=0}^{m}binom{m}{i}(-n/2)^i k^{m-i}\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{(-2)^mx^m}{m!}sum_{k=0}^n binom{n}{k}(-n/2+k)^m\
&=frac1{2^n}sum_{m=0}^{infty}dfrac{x^m}{m!}sum_{k=0}^n binom{n}{k}(2k-n)^m\
end{array}
$
And this is the OP.
Oh well.
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
answered Dec 9 '18 at 21:48
marty cohenmarty cohen
73.2k549128
73.2k549128
add a comment |
add a comment |
$begingroup$
Let $omega $ be a $n$-dimensional vector with binary components $omega_i=pm1$ and $Omega_n $ be a set of all such vectors, the size of the set obviously being $2^n $. The sum of elements of a vector with $i$
positive and $n-i $ negative components is $2i-n $ and the number of such vectors is $binom {n}{i}$. Thus
$$
F (n,k)=frac {1}{2^n}sum_{omegainOmega_n } left (sum_{i=1}^nomega_i right)^{2k}
=frac {1}{2^n}sum_{omegainOmega_n } sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}prod_i omega_i^{p_i}
=sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}left (frac {1}{2^n}sum_{omegainOmega_n }prod_i omega_i^{p_i}right)
=sum_{p_ige0,;p_i,text {mod},2=0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}.
$$
To proceed further one splits the last sum into partial ones over terms with particular count $l$ of non-zero $p_i$ and ends up with:
$$
F (n,k)=sum_{l=1}^n T (k,l)n^underline{l},tag {1}
$$
where $T (k,l)$ is the number of partitions of a set of size $2k$ into $l$ blocks of even size, and $n^underline{l}$ is falling factorial. $T(k,l)$ can be recognized as the OEIS sequence A156289 with known close-form and recurrence expressions.
Note added: by numerical evidence the polynomial (1) can be expressed in the terms of usual powers as:
$$
F (n,k)=sum_{l=1}^n A (k,l)n^l,tag {2}
$$
with $A (k,l) $ being the OEIS sequence A318146. In other words $F(n,k) $ is in fact the so called Omega polynomial.
answered Dec 26 '18 at 19:53
useruser
3,9051627
$endgroup$
add a comment |
$begingroup$
Let $omega $ be a $n$-dimensional vector with binary components $omega_i=pm1$ and $Omega_n $ be a set of all such vectors, the size of the set obviously being $2^n $. The sum of elements of a vector with $i$
positive and $n-i $ negative components is $2i-n $ and the number of such vectors is $binom {n}{i}$. Thus
$$
F (n,k)=frac {1}{2^n}sum_{omegainOmega_n } left (sum_{i=1}^nomega_i right)^{2k}
=frac {1}{2^n}sum_{omegainOmega_n } sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}prod_i omega_i^{p_i}
=sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}left (frac {1}{2^n}sum_{omegainOmega_n }prod_i omega_i^{p_i}right)
=sum_{p_ige0,;p_i,text {mod},2=0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}.
$$
To proceed further one splits the last sum into partial ones over terms with particular count $l$ of non-zero $p_i$ and ends up with:
$$
F (n,k)=sum_{l=1}^n T (k,l)n^underline{l},tag {1}
$$
where $T (k,l)$ is the number of partitions of a set of size $2k$ into $l$ blocks of even size, and $n^underline{l}$ is falling factorial. $T(k,l)$ can be recognized as the OEIS sequence A156289 with known close-form and recurrence expressions.
Note added: by numerical evidence the polynomial (1) can be expressed in the terms of usual powers as:
$$
F (n,k)=sum_{l=1}^n A (k,l)n^l,tag {2}
$$
with $A (k,l) $ being the OEIS sequence A318146. In other words $F(n,k) $ is in fact the so called Omega polynomial.
answered Dec 26 '18 at 19:53
useruser
3,9051627
$endgroup$
add a comment |
$begingroup$
Let $omega $ be a $n$-dimensional vector with binary components $omega_i=pm1$ and $Omega_n $ be a set of all such vectors, the size of the set obviously being $2^n $. The sum of elements of a vector with $i$
positive and $n-i $ negative components is $2i-n $ and the number of such vectors is $binom {n}{i}$. Thus
$$
F (n,k)=frac {1}{2^n}sum_{omegainOmega_n } left (sum_{i=1}^nomega_i right)^{2k}
=frac {1}{2^n}sum_{omegainOmega_n } sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}prod_i omega_i^{p_i}
=sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}left (frac {1}{2^n}sum_{omegainOmega_n }prod_i omega_i^{p_i}right)
=sum_{p_ige0,;p_i,text {mod},2=0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}.
$$
To proceed further one splits the last sum into partial ones over terms with particular count $l$ of non-zero $p_i$ and ends up with:
$$
F (n,k)=sum_{l=1}^n T (k,l)n^underline{l},tag {1}
$$
where $T (k,l)$ is the number of partitions of a set of size $2k$ into $l$ blocks of even size, and $n^underline{l}$ is falling factorial. $T(k,l)$ can be recognized as the OEIS sequence A156289 with known close-form and recurrence expressions.
Note added: by numerical evidence the polynomial (1) can be expressed in the terms of usual powers as:
$$
F (n,k)=sum_{l=1}^n A (k,l)n^l,tag {2}
$$
with $A (k,l) $ being the OEIS sequence A318146. In other words $F(n,k) $ is in fact the so called Omega polynomial.
answered Dec 26 '18 at 19:53
useruser
3,9051627
$endgroup$
Let $omega $ be a $n$-dimensional vector with binary components $omega_i=pm1$ and $Omega_n $ be a set of all such vectors, the size of the set obviously being $2^n $. The sum of elements of a vector with $i$
positive and $n-i $ negative components is $2i-n $ and the number of such vectors is $binom {n}{i}$. Thus
$$
F (n,k)=frac {1}{2^n}sum_{omegainOmega_n } left (sum_{i=1}^nomega_i right)^{2k}
=frac {1}{2^n}sum_{omegainOmega_n } sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}prod_i omega_i^{p_i}
=sum_{p_ige0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}left (frac {1}{2^n}sum_{omegainOmega_n }prod_i omega_i^{p_i}right)
=sum_{p_ige0,;p_i,text {mod},2=0}^{sum_i p_i=2k}binom {2k} {p_1,p_2,dots,p_n}.
$$
To proceed further one splits the last sum into partial ones over terms with particular count $l$ of non-zero $p_i$ and ends up with:
$$
F (n,k)=sum_{l=1}^n T (k,l)n^underline{l},tag {1}
$$
where $T (k,l)$ is the number of partitions of a set of size $2k$ into $l$ blocks of even size, and $n^underline{l}$ is falling factorial. $T(k,l)$ can be recognized as the OEIS sequence A156289 with known close-form and recurrence expressions.
Note added: by numerical evidence the polynomial (1) can be expressed in the terms of usual powers as:
$$
F (n,k)=sum_{l=1}^n A (k,l)n^l,tag {2}
$$
with $A (k,l) $ being the OEIS sequence A318146. In other words $F(n,k) $ is in fact the so called Omega polynomial.
answered Dec 26 '18 at 19:53
useruser
3,9051627
edited Jan 1 at 10:58
answered Dec 26 '18 at 19:53
useruser
3,9051627
answered Dec 26 '18 at 19:53
useruser
3,9051627
answered Dec 26 '18 at 19:53
useruser
3,9051627
3,9051627
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%2f3032709%2fpolynomial-expression-for-frac-12n-sum-i-0n-binomni2i-n2k%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
$begingroup$
That is a closed form. The sum is finite. I'd try expanding $(2i-n)^{2k}$ or computing some values and plugging them in into OEIS, in any case.
$endgroup$
– ajotatxe
Dec 9 '18 at 18:10
$begingroup$
@ajotatxe I have edited the question to clarify what I meant by "closed - form expression".
$endgroup$
– user
Dec 9 '18 at 19:30
1
$begingroup$
This expression comes out in Exercise 7 of UMN Fall 2018 Math 5705 Homework set 4, and also in Corollary 2.5 of Stanley's Algebraic Combinatorics (but these two appearances are actually easily seen to be equivalent: a closed walk of length $n$ on the hypercube is uniquely determined by its starting point and the $n$-tuple of "signless step directions", which $n$-tuple is clearly all-even).
$endgroup$
– darij grinberg
Dec 11 '18 at 3:16
1
$begingroup$
If there is a closed form, then Stanley could not find it. On the other hand, the polynomial claim is interesting.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:18
1
$begingroup$
Ah, I see why it is a polynomial. You can count the all-even $k$-tuples in $left[nright]^k$ according to the positions of equal entries (more formally: the set partition of $left[kright]$ that governs which of the entries of the tuple are equal). For any given such choice of positions, the number of tuples is a polynomial in $n$ with degree $k$ (namely, a power of $n$ times a power of $n-1$ times a power of $n-2$ and so on). Feel free to expand on this in an answer -- I am stuck in bed with a flu and not at my most productive.
$endgroup$
– darij grinberg
Dec 11 '18 at 3:45