Inverting the binomial convolution of sequences
$begingroup$
let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
$$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
Is there a way to recover $a_{n}b_{n}$ via something akin to :
$$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$
combinatorics
$endgroup$
add a comment |
$begingroup$
let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
$$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
Is there a way to recover $a_{n}b_{n}$ via something akin to :
$$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$
combinatorics
$endgroup$
add a comment |
$begingroup$
let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
$$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
Is there a way to recover $a_{n}b_{n}$ via something akin to :
$$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$
combinatorics
$endgroup$
let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
$$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
Is there a way to recover $a_{n}b_{n}$ via something akin to :
$$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$
combinatorics
combinatorics
asked Dec 20 '18 at 13:11
Mohammad Al JamalMohammad Al Jamal
174321
174321
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Let
$a_n=1$,
$b_n=1$,
$tilde a_n=2^n$, and
$tilde b_0=1$, $tilde b_n=0$ for all $n>0$.
Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.
$endgroup$
add a comment |
$begingroup$
Edit: this does not answer the question (see comments.)
Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
$$
(Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
$$
What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
$$
a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
$$
$endgroup$
$begingroup$
I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
$endgroup$
– Mike Earnest
Dec 20 '18 at 18:15
$begingroup$
I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
$endgroup$
– Julián Aguirre
Dec 20 '18 at 19:02
add a comment |
$begingroup$
Given
$$
c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
$$
then notice that the e.g.f.'s are in the following relation
$$
eqalign{
& C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
= ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
& = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
& = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
& = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
& = ,A(z)B(z) cr}
$$
That premised, and passing for simplicity to the ordinary g.f.
$$
C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
= ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
$$
if I understand properly your question and comment, you need to compute $D(z)$
$$
D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
$$
knowing $A(z)$ and $B(z)$ .
Then, assuming that these are convergent in a domain of non-null measure, you can use the
duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
reads as
$$
D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
$$
refer to last entry of the table in this Wikipedia Article
$endgroup$
1
$begingroup$
yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
$endgroup$
– Mohammad Al Jamal
Dec 20 '18 at 21:42
$begingroup$
@MohammadAlJamal: added possible solution: don't know if I caught exactly your question
$endgroup$
– G Cab
Dec 21 '18 at 0:41
2
$begingroup$
$sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
$endgroup$
– reuns
Dec 21 '18 at 1:20
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%2f3047527%2finverting-the-binomial-convolution-of-sequences%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$
Let
$a_n=1$,
$b_n=1$,
$tilde a_n=2^n$, and
$tilde b_0=1$, $tilde b_n=0$ for all $n>0$.
Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.
$endgroup$
add a comment |
$begingroup$
Let
$a_n=1$,
$b_n=1$,
$tilde a_n=2^n$, and
$tilde b_0=1$, $tilde b_n=0$ for all $n>0$.
Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.
$endgroup$
add a comment |
$begingroup$
Let
$a_n=1$,
$b_n=1$,
$tilde a_n=2^n$, and
$tilde b_0=1$, $tilde b_n=0$ for all $n>0$.
Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.
$endgroup$
Let
$a_n=1$,
$b_n=1$,
$tilde a_n=2^n$, and
$tilde b_0=1$, $tilde b_n=0$ for all $n>0$.
Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.
answered Dec 22 '18 at 5:25
Mike EarnestMike Earnest
23.3k12051
23.3k12051
add a comment |
add a comment |
$begingroup$
Edit: this does not answer the question (see comments.)
Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
$$
(Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
$$
What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
$$
a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
$$
$endgroup$
$begingroup$
I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
$endgroup$
– Mike Earnest
Dec 20 '18 at 18:15
$begingroup$
I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
$endgroup$
– Julián Aguirre
Dec 20 '18 at 19:02
add a comment |
$begingroup$
Edit: this does not answer the question (see comments.)
Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
$$
(Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
$$
What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
$$
a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
$$
$endgroup$
$begingroup$
I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
$endgroup$
– Mike Earnest
Dec 20 '18 at 18:15
$begingroup$
I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
$endgroup$
– Julián Aguirre
Dec 20 '18 at 19:02
add a comment |
$begingroup$
Edit: this does not answer the question (see comments.)
Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
$$
(Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
$$
What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
$$
a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
$$
$endgroup$
Edit: this does not answer the question (see comments.)
Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
$$
(Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
$$
What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
$$
a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
$$
edited Dec 20 '18 at 19:03
answered Dec 20 '18 at 14:52
Julián AguirreJulián Aguirre
69k24096
69k24096
$begingroup$
I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
$endgroup$
– Mike Earnest
Dec 20 '18 at 18:15
$begingroup$
I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
$endgroup$
– Julián Aguirre
Dec 20 '18 at 19:02
add a comment |
$begingroup$
I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
$endgroup$
– Mike Earnest
Dec 20 '18 at 18:15
$begingroup$
I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
$endgroup$
– Julián Aguirre
Dec 20 '18 at 19:02
$begingroup$
I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
$endgroup$
– Mike Earnest
Dec 20 '18 at 18:15
$begingroup$
I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
$endgroup$
– Mike Earnest
Dec 20 '18 at 18:15
$begingroup$
I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
$endgroup$
– Julián Aguirre
Dec 20 '18 at 19:02
$begingroup$
I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
$endgroup$
– Julián Aguirre
Dec 20 '18 at 19:02
add a comment |
$begingroup$
Given
$$
c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
$$
then notice that the e.g.f.'s are in the following relation
$$
eqalign{
& C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
= ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
& = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
& = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
& = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
& = ,A(z)B(z) cr}
$$
That premised, and passing for simplicity to the ordinary g.f.
$$
C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
= ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
$$
if I understand properly your question and comment, you need to compute $D(z)$
$$
D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
$$
knowing $A(z)$ and $B(z)$ .
Then, assuming that these are convergent in a domain of non-null measure, you can use the
duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
reads as
$$
D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
$$
refer to last entry of the table in this Wikipedia Article
$endgroup$
1
$begingroup$
yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
$endgroup$
– Mohammad Al Jamal
Dec 20 '18 at 21:42
$begingroup$
@MohammadAlJamal: added possible solution: don't know if I caught exactly your question
$endgroup$
– G Cab
Dec 21 '18 at 0:41
2
$begingroup$
$sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
$endgroup$
– reuns
Dec 21 '18 at 1:20
add a comment |
$begingroup$
Given
$$
c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
$$
then notice that the e.g.f.'s are in the following relation
$$
eqalign{
& C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
= ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
& = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
& = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
& = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
& = ,A(z)B(z) cr}
$$
That premised, and passing for simplicity to the ordinary g.f.
$$
C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
= ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
$$
if I understand properly your question and comment, you need to compute $D(z)$
$$
D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
$$
knowing $A(z)$ and $B(z)$ .
Then, assuming that these are convergent in a domain of non-null measure, you can use the
duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
reads as
$$
D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
$$
refer to last entry of the table in this Wikipedia Article
$endgroup$
1
$begingroup$
yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
$endgroup$
– Mohammad Al Jamal
Dec 20 '18 at 21:42
$begingroup$
@MohammadAlJamal: added possible solution: don't know if I caught exactly your question
$endgroup$
– G Cab
Dec 21 '18 at 0:41
2
$begingroup$
$sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
$endgroup$
– reuns
Dec 21 '18 at 1:20
add a comment |
$begingroup$
Given
$$
c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
$$
then notice that the e.g.f.'s are in the following relation
$$
eqalign{
& C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
= ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
& = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
& = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
& = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
& = ,A(z)B(z) cr}
$$
That premised, and passing for simplicity to the ordinary g.f.
$$
C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
= ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
$$
if I understand properly your question and comment, you need to compute $D(z)$
$$
D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
$$
knowing $A(z)$ and $B(z)$ .
Then, assuming that these are convergent in a domain of non-null measure, you can use the
duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
reads as
$$
D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
$$
refer to last entry of the table in this Wikipedia Article
$endgroup$
Given
$$
c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
$$
then notice that the e.g.f.'s are in the following relation
$$
eqalign{
& C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
= ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
& = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
& = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
& = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
& = ,A(z)B(z) cr}
$$
That premised, and passing for simplicity to the ordinary g.f.
$$
C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
= ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
$$
if I understand properly your question and comment, you need to compute $D(z)$
$$
D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
$$
knowing $A(z)$ and $B(z)$ .
Then, assuming that these are convergent in a domain of non-null measure, you can use the
duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
reads as
$$
D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
$$
refer to last entry of the table in this Wikipedia Article
edited Dec 21 '18 at 0:39
answered Dec 20 '18 at 20:01
G CabG Cab
19.5k31238
19.5k31238
1
$begingroup$
yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
$endgroup$
– Mohammad Al Jamal
Dec 20 '18 at 21:42
$begingroup$
@MohammadAlJamal: added possible solution: don't know if I caught exactly your question
$endgroup$
– G Cab
Dec 21 '18 at 0:41
2
$begingroup$
$sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
$endgroup$
– reuns
Dec 21 '18 at 1:20
add a comment |
1
$begingroup$
yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
$endgroup$
– Mohammad Al Jamal
Dec 20 '18 at 21:42
$begingroup$
@MohammadAlJamal: added possible solution: don't know if I caught exactly your question
$endgroup$
– G Cab
Dec 21 '18 at 0:41
2
$begingroup$
$sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
$endgroup$
– reuns
Dec 21 '18 at 1:20
1
1
$begingroup$
yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
$endgroup$
– Mohammad Al Jamal
Dec 20 '18 at 21:42
$begingroup$
yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
$endgroup$
– Mohammad Al Jamal
Dec 20 '18 at 21:42
$begingroup$
@MohammadAlJamal: added possible solution: don't know if I caught exactly your question
$endgroup$
– G Cab
Dec 21 '18 at 0:41
$begingroup$
@MohammadAlJamal: added possible solution: don't know if I caught exactly your question
$endgroup$
– G Cab
Dec 21 '18 at 0:41
2
2
$begingroup$
$sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
$endgroup$
– reuns
Dec 21 '18 at 1:20
$begingroup$
$sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
$endgroup$
– reuns
Dec 21 '18 at 1:20
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%2f3047527%2finverting-the-binomial-convolution-of-sequences%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