Closed form expression for a recursion relation with binomial coefficients
$begingroup$
I am interested in the following sequence: $$ T_n = sumlimits^{n-1}_{k=0} begin{pmatrix} n \ k end{pmatrix} T_{k}, T_0 = C in mathbb{N} $$
I would like to express it as a function of n, but none of the method I have tried work.
Asymptotically, I can tell that $T_n = mathcal{O}(2^{frac{k^2}{2}})$.
One method that failed was to see $T_n$ as the $n$-th term in a series, but those terms grow to fast for it to work.
Do you know how to solve it, or have an intuition regarding how it might get solved?
Thank you.
co.combinatorics sequences-and-series binomial-coefficients integer-sequences
edited 13 hours ago
Carlo Beenakker
76.8k9180284
asked 15 hours ago
SharkySharky
311
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I am interested in the following sequence: $$ T_n = sumlimits^{n-1}_{k=0} begin{pmatrix} n \ k end{pmatrix} T_{k}, T_0 = C in mathbb{N} $$
I would like to express it as a function of n, but none of the method I have tried work.
Asymptotically, I can tell that $T_n = mathcal{O}(2^{frac{k^2}{2}})$.
One method that failed was to see $T_n$ as the $n$-th term in a series, but those terms grow to fast for it to work.
Do you know how to solve it, or have an intuition regarding how it might get solved?
Thank you.
co.combinatorics sequences-and-series binomial-coefficients integer-sequences
edited 13 hours ago
Carlo Beenakker
76.8k9180284
asked 15 hours ago
SharkySharky
311
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
5
$begingroup$
Here is a recipe:sage: T = lambda n: x if n == 0 else sum(binomial(n,k)*T(k) for k in range(n))sage: T = cached_function(T)sage: [T(n) for n in range(5)][x, x, 3*x, 13*x, 75*x]sage: oeis([T(n)/x for n in range(20)])0: A000670: Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].
$endgroup$
– Martin Rubey
14 hours ago
add a comment |
$begingroup$
I am interested in the following sequence: $$ T_n = sumlimits^{n-1}_{k=0} begin{pmatrix} n \ k end{pmatrix} T_{k}, T_0 = C in mathbb{N} $$
I would like to express it as a function of n, but none of the method I have tried work.
Asymptotically, I can tell that $T_n = mathcal{O}(2^{frac{k^2}{2}})$.
One method that failed was to see $T_n$ as the $n$-th term in a series, but those terms grow to fast for it to work.
Do you know how to solve it, or have an intuition regarding how it might get solved?
Thank you.
co.combinatorics sequences-and-series binomial-coefficients integer-sequences
edited 13 hours ago
Carlo Beenakker
76.8k9180284
asked 15 hours ago
SharkySharky
311
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I am interested in the following sequence: $$ T_n = sumlimits^{n-1}_{k=0} begin{pmatrix} n \ k end{pmatrix} T_{k}, T_0 = C in mathbb{N} $$
I would like to express it as a function of n, but none of the method I have tried work.
Asymptotically, I can tell that $T_n = mathcal{O}(2^{frac{k^2}{2}})$.
One method that failed was to see $T_n$ as the $n$-th term in a series, but those terms grow to fast for it to work.
Do you know how to solve it, or have an intuition regarding how it might get solved?
Thank you.
co.combinatorics sequences-and-series binomial-coefficients integer-sequences
co.combinatorics sequences-and-series binomial-coefficients integer-sequences
edited 13 hours ago
Carlo Beenakker
76.8k9180284
asked 15 hours ago
SharkySharky
311
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 13 hours ago
Carlo Beenakker
76.8k9180284
asked 15 hours ago
SharkySharky
311
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 13 hours ago
Carlo Beenakker
76.8k9180284
edited 13 hours ago
Carlo Beenakker
76.8k9180284
edited 13 hours ago
Carlo Beenakker
76.8k9180284
76.8k9180284
asked 15 hours ago
SharkySharky
311
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 15 hours ago
SharkySharky
311
asked 15 hours ago
SharkySharky
311
311
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Sharky is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
5
$begingroup$
Here is a recipe:sage: T = lambda n: x if n == 0 else sum(binomial(n,k)*T(k) for k in range(n))sage: T = cached_function(T)sage: [T(n) for n in range(5)][x, x, 3*x, 13*x, 75*x]sage: oeis([T(n)/x for n in range(20)])0: A000670: Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].
$endgroup$
– Martin Rubey
14 hours ago
add a comment |
5
$begingroup$
Here is a recipe:sage: T = lambda n: x if n == 0 else sum(binomial(n,k)*T(k) for k in range(n))sage: T = cached_function(T)sage: [T(n) for n in range(5)][x, x, 3*x, 13*x, 75*x]sage: oeis([T(n)/x for n in range(20)])0: A000670: Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].
$endgroup$
– Martin Rubey
14 hours ago
5
5
$begingroup$
Here is a recipe:
sage: T = lambda n: x if n == 0 else sum(binomial(n,k)*T(k) for k in range(n)) sage: T = cached_function(T) sage: [T(n) for n in range(5)] [x, x, 3*x, 13*x, 75*x] sage: oeis([T(n)/x for n in range(20)]) 0: A000670: Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].$endgroup$
– Martin Rubey
14 hours ago
$begingroup$
Here is a recipe:
sage: T = lambda n: x if n == 0 else sum(binomial(n,k)*T(k) for k in range(n)) sage: T = cached_function(T) sage: [T(n) for n in range(5)] [x, x, 3*x, 13*x, 75*x] sage: oeis([T(n)/x for n in range(20)]) 0: A000670: Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].$endgroup$
– Martin Rubey
14 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The $T_n$'s are equal to the product of $C$ and the Fubini numbers: number of ordered partitions of $n$, also known as ordered Bell numbers. The generating function is $(2-e^x)^{-1}$ and the large-$n$ asymptotics is
$$T_nsim C frac{n!}{2(ln 2)^{n+1}}.$$
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
$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: "504"
};
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
});
}
});
Sharky is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2fmathoverflow.net%2fquestions%2f323499%2fclosed-form-expression-for-a-recursion-relation-with-binomial-coefficients%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The $T_n$'s are equal to the product of $C$ and the Fubini numbers: number of ordered partitions of $n$, also known as ordered Bell numbers. The generating function is $(2-e^x)^{-1}$ and the large-$n$ asymptotics is
$$T_nsim C frac{n!}{2(ln 2)^{n+1}}.$$
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
$endgroup$
add a comment |
$begingroup$
The $T_n$'s are equal to the product of $C$ and the Fubini numbers: number of ordered partitions of $n$, also known as ordered Bell numbers. The generating function is $(2-e^x)^{-1}$ and the large-$n$ asymptotics is
$$T_nsim C frac{n!}{2(ln 2)^{n+1}}.$$
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
$endgroup$
add a comment |
$begingroup$
The $T_n$'s are equal to the product of $C$ and the Fubini numbers: number of ordered partitions of $n$, also known as ordered Bell numbers. The generating function is $(2-e^x)^{-1}$ and the large-$n$ asymptotics is
$$T_nsim C frac{n!}{2(ln 2)^{n+1}}.$$
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
$endgroup$
The $T_n$'s are equal to the product of $C$ and the Fubini numbers: number of ordered partitions of $n$, also known as ordered Bell numbers. The generating function is $(2-e^x)^{-1}$ and the large-$n$ asymptotics is
$$T_nsim C frac{n!}{2(ln 2)^{n+1}}.$$
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
answered 14 hours ago
Carlo BeenakkerCarlo Beenakker
76.8k9180284
76.8k9180284
add a comment |
add a comment |
Sharky is a new contributor. Be nice, and check out our Code of Conduct.
Sharky is a new contributor. Be nice, and check out our Code of Conduct.
Sharky is a new contributor. Be nice, and check out our Code of Conduct.
Sharky is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to MathOverflow!
- 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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2fmathoverflow.net%2fquestions%2f323499%2fclosed-form-expression-for-a-recursion-relation-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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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
5
$begingroup$
Here is a recipe:
sage: T = lambda n: x if n == 0 else sum(binomial(n,k)*T(k) for k in range(n))sage: T = cached_function(T)sage: [T(n) for n in range(5)][x, x, 3*x, 13*x, 75*x]sage: oeis([T(n)/x for n in range(20)])0: A000670: Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].$endgroup$
– Martin Rubey
14 hours ago