Estimating sum with binomial coefficients Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Sum involving integer compositions and binomial coefficientsIdentity for central binomial coefficientsEvaluating a sum with binomial coefficients: $sum_k=1^n n choose k frac1k^r a^k b^n-k$Strehl identity for the sum of cubes of binomial coefficientsSum of Binomials times LogarithmsFind the closed expression for binomial sumFinite sum with three binomial coefficientsSum of Lacunary Series of Binomial Coefficients with Rising Upper ParameterAnother summation identity with binomial coefficientsIs there a closed form for the sum of the cubes of the binomial coefficients?
How would a mousetrap for use in space work?
Why are both D and D# fitting into my E minor key?
また usage in a dictionary
Can you use the Shield Master feat to shove someone before you make an attack by using a Readied action?
How can I use the Python library networkx from Mathematica?
Is there such thing as an Availability Group failover trigger?
Fantasy story; one type of magic grows in power with use, but the more powerful they are, they more they are drawn to travel to their source
Would "destroying" Wurmcoil Engine prevent its tokens from being created?
Trademark violation for app?
8 Prisoners wearing hats
What is the meaning of the new sigil in Game of Thrones Season 8 intro?
How come Sam didn't become Lord of Horn Hill?
Wu formula for manifolds with boundary
If a contract sometimes uses the wrong name, is it still valid?
Generate an RGB colour grid
Should I use a zero-interest credit card for a large one-time purchase?
Compare a given version number in the form major.minor.build.patch and see if one is less than the other
Withdrew £2800, but only £2000 shows as withdrawn on online banking; what are my obligations?
How to find all the available tools in mac terminal?
What would be the ideal power source for a cybernetic eye?
For a new assistant professor in CS, how to build/manage a publication pipeline
What is homebrew?
Is CEO the profession with the most psychopaths?
If my PI received research grants from a company to be able to pay my postdoc salary, did I have a potential conflict interest too?
Estimating sum with binomial coefficients
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Sum involving integer compositions and binomial coefficientsIdentity for central binomial coefficientsEvaluating a sum with binomial coefficients: $sum_k=1^n n choose k frac1k^r a^k b^n-k$Strehl identity for the sum of cubes of binomial coefficientsSum of Binomials times LogarithmsFind the closed expression for binomial sumFinite sum with three binomial coefficientsSum of Lacunary Series of Binomial Coefficients with Rising Upper ParameterAnother summation identity with binomial coefficientsIs there a closed form for the sum of the cubes of the binomial coefficients?
$begingroup$
Lately when I was estimating complexity of some algorithm I came across this sum:
$$sum_k=0^n binom nk binom n-kk$$
Is it possible to find a closed-form expression for this sum, or at least estimate this with some more known functions? I know that it is somewhere between $2^n$ and $3^n$ but I wonder if maybe some better estimation is possible.
summation binomial-coefficients
asked Oct 1 '14 at 7:41
xanxan
937724
$endgroup$
add a comment |
$begingroup$
Lately when I was estimating complexity of some algorithm I came across this sum:
$$sum_k=0^n binom nk binom n-kk$$
Is it possible to find a closed-form expression for this sum, or at least estimate this with some more known functions? I know that it is somewhere between $2^n$ and $3^n$ but I wonder if maybe some better estimation is possible.
summation binomial-coefficients
asked Oct 1 '14 at 7:41
xanxan
937724
$endgroup$
$begingroup$
@bof: aah, you're right. Apologies. But what is $C^1_n-1$ supposed to mean (second term when $k=n-1$) ?
$endgroup$
– Alexandre Halm
Oct 1 '14 at 7:55
$begingroup$
@AlexH. I guess it's zero. $binom xk=x(x-1)(x-2)cdots(x-k+1)/k!$ is zero for $x=0,1,2,dots,k-1$.
$endgroup$
– bof
Oct 1 '14 at 8:03
$begingroup$
I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining.
$endgroup$
– Gautam Shenoy
Oct 1 '14 at 8:05
$begingroup$
Looks like you got a couple of pretty good answers to your question. What don't you like about them?
$endgroup$
– bof
Oct 7 '14 at 2:57
add a comment |
$begingroup$
Lately when I was estimating complexity of some algorithm I came across this sum:
$$sum_k=0^n binom nk binom n-kk$$
Is it possible to find a closed-form expression for this sum, or at least estimate this with some more known functions? I know that it is somewhere between $2^n$ and $3^n$ but I wonder if maybe some better estimation is possible.
summation binomial-coefficients
asked Oct 1 '14 at 7:41
xanxan
937724
$endgroup$
Lately when I was estimating complexity of some algorithm I came across this sum:
$$sum_k=0^n binom nk binom n-kk$$
Is it possible to find a closed-form expression for this sum, or at least estimate this with some more known functions? I know that it is somewhere between $2^n$ and $3^n$ but I wonder if maybe some better estimation is possible.
summation binomial-coefficients
summation binomial-coefficients
asked Oct 1 '14 at 7:41
xanxan
937724
asked Oct 1 '14 at 7:41
xanxan
937724
asked Oct 1 '14 at 7:41
xanxan
937724
asked Oct 1 '14 at 7:41
xanxan
937724
asked Oct 1 '14 at 7:41
xanxan
937724
937724
$begingroup$
@bof: aah, you're right. Apologies. But what is $C^1_n-1$ supposed to mean (second term when $k=n-1$) ?
$endgroup$
– Alexandre Halm
Oct 1 '14 at 7:55
$begingroup$
@AlexH. I guess it's zero. $binom xk=x(x-1)(x-2)cdots(x-k+1)/k!$ is zero for $x=0,1,2,dots,k-1$.
$endgroup$
– bof
Oct 1 '14 at 8:03
$begingroup$
I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining.
$endgroup$
– Gautam Shenoy
Oct 1 '14 at 8:05
$begingroup$
Looks like you got a couple of pretty good answers to your question. What don't you like about them?
$endgroup$
– bof
Oct 7 '14 at 2:57
add a comment |
$begingroup$
@bof: aah, you're right. Apologies. But what is $C^1_n-1$ supposed to mean (second term when $k=n-1$) ?
$endgroup$
– Alexandre Halm
Oct 1 '14 at 7:55
$begingroup$
@AlexH. I guess it's zero. $binom xk=x(x-1)(x-2)cdots(x-k+1)/k!$ is zero for $x=0,1,2,dots,k-1$.
$endgroup$
– bof
Oct 1 '14 at 8:03
$begingroup$
I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining.
$endgroup$
– Gautam Shenoy
Oct 1 '14 at 8:05
$begingroup$
Looks like you got a couple of pretty good answers to your question. What don't you like about them?
$endgroup$
– bof
Oct 7 '14 at 2:57
$begingroup$
@bof: aah, you're right. Apologies. But what is $C^1_n-1$ supposed to mean (second term when $k=n-1$) ?
$endgroup$
– Alexandre Halm
Oct 1 '14 at 7:55
$begingroup$
@bof: aah, you're right. Apologies. But what is $C^1_n-1$ supposed to mean (second term when $k=n-1$) ?
$endgroup$
– Alexandre Halm
Oct 1 '14 at 7:55
$begingroup$
@AlexH. I guess it's zero. $binom xk=x(x-1)(x-2)cdots(x-k+1)/k!$ is zero for $x=0,1,2,dots,k-1$.
$endgroup$
– bof
Oct 1 '14 at 8:03
$begingroup$
@AlexH. I guess it's zero. $binom xk=x(x-1)(x-2)cdots(x-k+1)/k!$ is zero for $x=0,1,2,dots,k-1$.
$endgroup$
– bof
Oct 1 '14 at 8:03
$begingroup$
I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining.
$endgroup$
– Gautam Shenoy
Oct 1 '14 at 8:05
$begingroup$
I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining.
$endgroup$
– Gautam Shenoy
Oct 1 '14 at 8:05
$begingroup$
Looks like you got a couple of pretty good answers to your question. What don't you like about them?
$endgroup$
– bof
Oct 7 '14 at 2:57
$begingroup$
Looks like you got a couple of pretty good answers to your question. What don't you like about them?
$endgroup$
– bof
Oct 7 '14 at 2:57
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I calculated the sums for $nle6$ and plugged the sequence of values into The On-Line Encyclopedia of Integer Sequences (OEIS) It turns out to be sequence A002426, titled "Central trinomial coefficients: largest coefficient of (1+x+x^2)^n". Many interpretations, formulas, and references at the link.
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
$endgroup$
add a comment |
$begingroup$
A closed form is given by W/A as
$$
sum_k=0^n binom nk!! binom n-kk=_2F_1 left(-fracn-12 ,-fracn2 ;1;4 right)
$$
Maybe this can help for some estimation.
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
$endgroup$
add a comment |
$begingroup$
For every positive integer $n$,
$$sum_k=0^n binom nk binom n-kk = biggllfloorBigl(1+3^n+frac13^nBigl)^n biggrrfloor - 3^n biggllfloorBigl(frac13+3^n-1+frac13^n+1Bigl)^n biggrrfloor$$
answered Mar 27 at 5:50
nczksvnczksv
1931111
$endgroup$
add a comment |
Your Answer
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%2f953714%2festimating-sum-with-binomial-coefficients%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$
I calculated the sums for $nle6$ and plugged the sequence of values into The On-Line Encyclopedia of Integer Sequences (OEIS) It turns out to be sequence A002426, titled "Central trinomial coefficients: largest coefficient of (1+x+x^2)^n". Many interpretations, formulas, and references at the link.
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
$endgroup$
add a comment |
$begingroup$
I calculated the sums for $nle6$ and plugged the sequence of values into The On-Line Encyclopedia of Integer Sequences (OEIS) It turns out to be sequence A002426, titled "Central trinomial coefficients: largest coefficient of (1+x+x^2)^n". Many interpretations, formulas, and references at the link.
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
$endgroup$
add a comment |
$begingroup$
I calculated the sums for $nle6$ and plugged the sequence of values into The On-Line Encyclopedia of Integer Sequences (OEIS) It turns out to be sequence A002426, titled "Central trinomial coefficients: largest coefficient of (1+x+x^2)^n". Many interpretations, formulas, and references at the link.
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
$endgroup$
I calculated the sums for $nle6$ and plugged the sequence of values into The On-Line Encyclopedia of Integer Sequences (OEIS) It turns out to be sequence A002426, titled "Central trinomial coefficients: largest coefficient of (1+x+x^2)^n". Many interpretations, formulas, and references at the link.
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
answered Oct 1 '14 at 8:17
bofbof
52.6k559121
52.6k559121
add a comment |
add a comment |
$begingroup$
A closed form is given by W/A as
$$
sum_k=0^n binom nk!! binom n-kk=_2F_1 left(-fracn-12 ,-fracn2 ;1;4 right)
$$
Maybe this can help for some estimation.
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
$endgroup$
add a comment |
$begingroup$
A closed form is given by W/A as
$$
sum_k=0^n binom nk!! binom n-kk=_2F_1 left(-fracn-12 ,-fracn2 ;1;4 right)
$$
Maybe this can help for some estimation.
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
$endgroup$
add a comment |
$begingroup$
A closed form is given by W/A as
$$
sum_k=0^n binom nk!! binom n-kk=_2F_1 left(-fracn-12 ,-fracn2 ;1;4 right)
$$
Maybe this can help for some estimation.
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
$endgroup$
A closed form is given by W/A as
$$
sum_k=0^n binom nk!! binom n-kk=_2F_1 left(-fracn-12 ,-fracn2 ;1;4 right)
$$
Maybe this can help for some estimation.
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
answered Oct 1 '14 at 9:33
J. KeplerJ. Kepler
113
113
add a comment |
add a comment |
$begingroup$
For every positive integer $n$,
$$sum_k=0^n binom nk binom n-kk = biggllfloorBigl(1+3^n+frac13^nBigl)^n biggrrfloor - 3^n biggllfloorBigl(frac13+3^n-1+frac13^n+1Bigl)^n biggrrfloor$$
answered Mar 27 at 5:50
nczksvnczksv
1931111
$endgroup$
add a comment |
$begingroup$
For every positive integer $n$,
$$sum_k=0^n binom nk binom n-kk = biggllfloorBigl(1+3^n+frac13^nBigl)^n biggrrfloor - 3^n biggllfloorBigl(frac13+3^n-1+frac13^n+1Bigl)^n biggrrfloor$$
answered Mar 27 at 5:50
nczksvnczksv
1931111
$endgroup$
add a comment |
$begingroup$
For every positive integer $n$,
$$sum_k=0^n binom nk binom n-kk = biggllfloorBigl(1+3^n+frac13^nBigl)^n biggrrfloor - 3^n biggllfloorBigl(frac13+3^n-1+frac13^n+1Bigl)^n biggrrfloor$$
answered Mar 27 at 5:50
nczksvnczksv
1931111
$endgroup$
For every positive integer $n$,
$$sum_k=0^n binom nk binom n-kk = biggllfloorBigl(1+3^n+frac13^nBigl)^n biggrrfloor - 3^n biggllfloorBigl(frac13+3^n-1+frac13^n+1Bigl)^n biggrrfloor$$
answered Mar 27 at 5:50
nczksvnczksv
1931111
answered Mar 27 at 5:50
nczksvnczksv
1931111
answered Mar 27 at 5:50
nczksvnczksv
1931111
answered Mar 27 at 5:50
nczksvnczksv
1931111
1931111
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%2f953714%2festimating-sum-with-binomial-coefficients%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$
@bof: aah, you're right. Apologies. But what is $C^1_n-1$ supposed to mean (second term when $k=n-1$) ?
$endgroup$
– Alexandre Halm
Oct 1 '14 at 7:55
$begingroup$
@AlexH. I guess it's zero. $binom xk=x(x-1)(x-2)cdots(x-k+1)/k!$ is zero for $x=0,1,2,dots,k-1$.
$endgroup$
– bof
Oct 1 '14 at 8:03
$begingroup$
I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining.
$endgroup$
– Gautam Shenoy
Oct 1 '14 at 8:05
$begingroup$
Looks like you got a couple of pretty good answers to your question. What don't you like about them?
$endgroup$
– bof
Oct 7 '14 at 2:57