Number of compositions in parts less equal two equals number of compositions in parts greater equal two.Solving combinatorial problems with symbolic method and generating functionsShowing two generating functions to be equalSum of $prod 1/n_i$ where $n_1,ldots,n_k$ are divisions of $m$ into $k$ parts.Generating Function for Integer CompositionsCompositions of $n$ with $r$ odd parts and $s$ even partsWeak $k$-compositions with each part less than $j$Generating Functions with compositionCompositions and PartitionsShow that the number of parity-preserving subsets of $n$ is equal to the number of odd-compositions of $n+2$How many permutations can there be?Solving combinatorial problems with symbolic method and generating functions
Can I make popcorn with any corn?
Can you lasso down a wizard who is using the Levitate spell?
Infinite past with a beginning?
Why do we use polarized capacitor?
Chess with symmetric move-square
Patience, young "Padovan"
Is it possible to make sharp wind that can cut stuff from afar?
I see my dog run
Copycat chess is back
Do airline pilots ever risk not hearing communication directed to them specifically, from traffic controllers?
What does "enim et" mean?
New order #4: World
Why is this code 6.5x slower with optimizations enabled?
How to make payment on the internet without leaving a money trail?
how to create a data type and make it available in all Databases?
What typically incentivizes a professor to change jobs to a lower ranking university?
What is the offset in a seaplane's hull?
My colleague's body is amazing
What is the command to reset a PC without deleting any files
What Brexit solution does the DUP want?
Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?
"which" command doesn't work / path of Safari?
Can an x86 CPU running in real mode be considered to be basically an 8086 CPU?
Are white and non-white police officers equally likely to kill black suspects?
Number of compositions in parts less equal two equals number of compositions in parts greater equal two.
Solving combinatorial problems with symbolic method and generating functionsShowing two generating functions to be equalSum of $prod 1/n_i$ where $n_1,ldots,n_k$ are divisions of $m$ into $k$ parts.Generating Function for Integer CompositionsCompositions of $n$ with $r$ odd parts and $s$ even partsWeak $k$-compositions with each part less than $j$Generating Functions with compositionCompositions and PartitionsShow that the number of parity-preserving subsets of $n$ is equal to the number of odd-compositions of $n+2$How many permutations can there be?Solving combinatorial problems with symbolic method and generating functions
$begingroup$
Notations/Definitions: A composition of a natural number $n in mathbbN$ (I use $0 notin mathbbN$) is a sequence of natural numbers $n_1,n_2, ..., n_d in mathbbN$ such that $n_1+...+n_d = n$. (repetions are allowed, order matters) Denote the number of compositions of a natural number $n in mathbbN$ consisting only of 1,2 by $k_n$. Denote the number of compositions of $n$, that only consist of terms from $2,3,...$ by $tildek_n$. Let $K(z) := sum_i = 0^infty k_n cdot z^n$ and $tildeK(z) := sum_i = 0^infty tildek_n cdot z^n$.
What I'm trying to prove: The number of compositions of $n in mathbbN$ consisting of parts $leq 2$ equals the number of compositions of (n+2) consisting of parts $geq 2$. Or in my notation: $k_n = tildek_n+2$.
Example: 4 has five compositions consisting of parts $leq 2$ (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2) and 6 has five compositions of parts $geq 2$ (2+2+2, 3+3, 6, 4+2, 2+4).
Proof:
I'm trying to prove the statement above by using generating functions. As the compositions of $n$ only consist of numbers from $1,2$ the generating function of $k_n$ is given by
$$
K(z) = frac11-GF(1,2) = frac11-(z+z^2).
$$
As the compositions of $n$ only consist of numbers from $2,3,...$ the generating function of $tildek_n$ is given by
$$
tildeK(z) = frac11-GF(2,3,...) = frac11-(z^2+z^3+...) = frac1frac-z^2-z+11-z.
$$
My idea to achieve my desired result ($tildek_n+2 = k_n$) was to show $$sum_i = 0^infty tildek_n+2 cdot z^n = fractildeK(z) - tildek_0 - tildek_1 cdot zz^2 overset!= K(z)$$
but the last equality doesn't seem to hold. (I think $tildek_0 = tildek_1 = 0$, is this correct?)
One more thing I realized is that $K(z) = frac11-z cdot tildeK(z)$ yields
$$ k_n = sum_i = 0^n tildek_i,$$
which I think shouldn't be correct.
Because of the last two points I think at least one of the generating functions is not correct, but I cannot find a mistake. Thank you in advance for any help!
combinatorics generating-functions
edited Mar 22 at 11:49
lioness99a
3,9012727
asked Mar 22 at 11:23
liouvilleliouville
233
$endgroup$
add a comment |
$begingroup$
Notations/Definitions: A composition of a natural number $n in mathbbN$ (I use $0 notin mathbbN$) is a sequence of natural numbers $n_1,n_2, ..., n_d in mathbbN$ such that $n_1+...+n_d = n$. (repetions are allowed, order matters) Denote the number of compositions of a natural number $n in mathbbN$ consisting only of 1,2 by $k_n$. Denote the number of compositions of $n$, that only consist of terms from $2,3,...$ by $tildek_n$. Let $K(z) := sum_i = 0^infty k_n cdot z^n$ and $tildeK(z) := sum_i = 0^infty tildek_n cdot z^n$.
What I'm trying to prove: The number of compositions of $n in mathbbN$ consisting of parts $leq 2$ equals the number of compositions of (n+2) consisting of parts $geq 2$. Or in my notation: $k_n = tildek_n+2$.
Example: 4 has five compositions consisting of parts $leq 2$ (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2) and 6 has five compositions of parts $geq 2$ (2+2+2, 3+3, 6, 4+2, 2+4).
Proof:
I'm trying to prove the statement above by using generating functions. As the compositions of $n$ only consist of numbers from $1,2$ the generating function of $k_n$ is given by
$$
K(z) = frac11-GF(1,2) = frac11-(z+z^2).
$$
As the compositions of $n$ only consist of numbers from $2,3,...$ the generating function of $tildek_n$ is given by
$$
tildeK(z) = frac11-GF(2,3,...) = frac11-(z^2+z^3+...) = frac1frac-z^2-z+11-z.
$$
My idea to achieve my desired result ($tildek_n+2 = k_n$) was to show $$sum_i = 0^infty tildek_n+2 cdot z^n = fractildeK(z) - tildek_0 - tildek_1 cdot zz^2 overset!= K(z)$$
but the last equality doesn't seem to hold. (I think $tildek_0 = tildek_1 = 0$, is this correct?)
One more thing I realized is that $K(z) = frac11-z cdot tildeK(z)$ yields
$$ k_n = sum_i = 0^n tildek_i,$$
which I think shouldn't be correct.
Because of the last two points I think at least one of the generating functions is not correct, but I cannot find a mistake. Thank you in advance for any help!
combinatorics generating-functions
edited Mar 22 at 11:49
lioness99a
3,9012727
asked Mar 22 at 11:23
liouvilleliouville
233
$endgroup$
2
$begingroup$
Someone asked this same problem here. Your mistake is with $tilde k_0$; you should have $tilde k_0=1$, as there is the empty composition.
$endgroup$
– Mike Earnest
Mar 22 at 16:57
$begingroup$
Thank you for your help. I haven't seen the other post, should I delete mine? If I use $tildek_0 = 1$ and $tildek_1 = 0$ i get the result I wanted to show. The last thing I don't fully understand is: Why does the empty composition matter for $tildek_0$ but not for $tildek_1$?
$endgroup$
– liouville
Mar 29 at 13:40
$begingroup$
The empty composition has zero parts, so it contributes to $tilde k_0$. There are zero compositions with $1$ part summing to $1$; any composition with one part must sum to at least $2$. Therefore, $tilde k_1=0$.
$endgroup$
– Mike Earnest
Mar 29 at 15:12
add a comment |
$begingroup$
Notations/Definitions: A composition of a natural number $n in mathbbN$ (I use $0 notin mathbbN$) is a sequence of natural numbers $n_1,n_2, ..., n_d in mathbbN$ such that $n_1+...+n_d = n$. (repetions are allowed, order matters) Denote the number of compositions of a natural number $n in mathbbN$ consisting only of 1,2 by $k_n$. Denote the number of compositions of $n$, that only consist of terms from $2,3,...$ by $tildek_n$. Let $K(z) := sum_i = 0^infty k_n cdot z^n$ and $tildeK(z) := sum_i = 0^infty tildek_n cdot z^n$.
What I'm trying to prove: The number of compositions of $n in mathbbN$ consisting of parts $leq 2$ equals the number of compositions of (n+2) consisting of parts $geq 2$. Or in my notation: $k_n = tildek_n+2$.
Example: 4 has five compositions consisting of parts $leq 2$ (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2) and 6 has five compositions of parts $geq 2$ (2+2+2, 3+3, 6, 4+2, 2+4).
Proof:
I'm trying to prove the statement above by using generating functions. As the compositions of $n$ only consist of numbers from $1,2$ the generating function of $k_n$ is given by
$$
K(z) = frac11-GF(1,2) = frac11-(z+z^2).
$$
As the compositions of $n$ only consist of numbers from $2,3,...$ the generating function of $tildek_n$ is given by
$$
tildeK(z) = frac11-GF(2,3,...) = frac11-(z^2+z^3+...) = frac1frac-z^2-z+11-z.
$$
My idea to achieve my desired result ($tildek_n+2 = k_n$) was to show $$sum_i = 0^infty tildek_n+2 cdot z^n = fractildeK(z) - tildek_0 - tildek_1 cdot zz^2 overset!= K(z)$$
but the last equality doesn't seem to hold. (I think $tildek_0 = tildek_1 = 0$, is this correct?)
One more thing I realized is that $K(z) = frac11-z cdot tildeK(z)$ yields
$$ k_n = sum_i = 0^n tildek_i,$$
which I think shouldn't be correct.
Because of the last two points I think at least one of the generating functions is not correct, but I cannot find a mistake. Thank you in advance for any help!
combinatorics generating-functions
edited Mar 22 at 11:49
lioness99a
3,9012727
asked Mar 22 at 11:23
liouvilleliouville
233
$endgroup$
Notations/Definitions: A composition of a natural number $n in mathbbN$ (I use $0 notin mathbbN$) is a sequence of natural numbers $n_1,n_2, ..., n_d in mathbbN$ such that $n_1+...+n_d = n$. (repetions are allowed, order matters) Denote the number of compositions of a natural number $n in mathbbN$ consisting only of 1,2 by $k_n$. Denote the number of compositions of $n$, that only consist of terms from $2,3,...$ by $tildek_n$. Let $K(z) := sum_i = 0^infty k_n cdot z^n$ and $tildeK(z) := sum_i = 0^infty tildek_n cdot z^n$.
What I'm trying to prove: The number of compositions of $n in mathbbN$ consisting of parts $leq 2$ equals the number of compositions of (n+2) consisting of parts $geq 2$. Or in my notation: $k_n = tildek_n+2$.
Example: 4 has five compositions consisting of parts $leq 2$ (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2) and 6 has five compositions of parts $geq 2$ (2+2+2, 3+3, 6, 4+2, 2+4).
Proof:
I'm trying to prove the statement above by using generating functions. As the compositions of $n$ only consist of numbers from $1,2$ the generating function of $k_n$ is given by
$$
K(z) = frac11-GF(1,2) = frac11-(z+z^2).
$$
As the compositions of $n$ only consist of numbers from $2,3,...$ the generating function of $tildek_n$ is given by
$$
tildeK(z) = frac11-GF(2,3,...) = frac11-(z^2+z^3+...) = frac1frac-z^2-z+11-z.
$$
My idea to achieve my desired result ($tildek_n+2 = k_n$) was to show $$sum_i = 0^infty tildek_n+2 cdot z^n = fractildeK(z) - tildek_0 - tildek_1 cdot zz^2 overset!= K(z)$$
but the last equality doesn't seem to hold. (I think $tildek_0 = tildek_1 = 0$, is this correct?)
One more thing I realized is that $K(z) = frac11-z cdot tildeK(z)$ yields
$$ k_n = sum_i = 0^n tildek_i,$$
which I think shouldn't be correct.
Because of the last two points I think at least one of the generating functions is not correct, but I cannot find a mistake. Thank you in advance for any help!
combinatorics generating-functions
combinatorics generating-functions
edited Mar 22 at 11:49
lioness99a
3,9012727
asked Mar 22 at 11:23
liouvilleliouville
233
edited Mar 22 at 11:49
lioness99a
3,9012727
asked Mar 22 at 11:23
liouvilleliouville
233
edited Mar 22 at 11:49
lioness99a
3,9012727
edited Mar 22 at 11:49
lioness99a
3,9012727
edited Mar 22 at 11:49
lioness99a
3,9012727
3,9012727
asked Mar 22 at 11:23
liouvilleliouville
233
asked Mar 22 at 11:23
liouvilleliouville
233
asked Mar 22 at 11:23
liouvilleliouville
233
233
2
$begingroup$
Someone asked this same problem here. Your mistake is with $tilde k_0$; you should have $tilde k_0=1$, as there is the empty composition.
$endgroup$
– Mike Earnest
Mar 22 at 16:57
$begingroup$
Thank you for your help. I haven't seen the other post, should I delete mine? If I use $tildek_0 = 1$ and $tildek_1 = 0$ i get the result I wanted to show. The last thing I don't fully understand is: Why does the empty composition matter for $tildek_0$ but not for $tildek_1$?
$endgroup$
– liouville
Mar 29 at 13:40
$begingroup$
The empty composition has zero parts, so it contributes to $tilde k_0$. There are zero compositions with $1$ part summing to $1$; any composition with one part must sum to at least $2$. Therefore, $tilde k_1=0$.
$endgroup$
– Mike Earnest
Mar 29 at 15:12
add a comment |
2
$begingroup$
Someone asked this same problem here. Your mistake is with $tilde k_0$; you should have $tilde k_0=1$, as there is the empty composition.
$endgroup$
– Mike Earnest
Mar 22 at 16:57
$begingroup$
Thank you for your help. I haven't seen the other post, should I delete mine? If I use $tildek_0 = 1$ and $tildek_1 = 0$ i get the result I wanted to show. The last thing I don't fully understand is: Why does the empty composition matter for $tildek_0$ but not for $tildek_1$?
$endgroup$
– liouville
Mar 29 at 13:40
$begingroup$
The empty composition has zero parts, so it contributes to $tilde k_0$. There are zero compositions with $1$ part summing to $1$; any composition with one part must sum to at least $2$. Therefore, $tilde k_1=0$.
$endgroup$
– Mike Earnest
Mar 29 at 15:12
2
2
$begingroup$
Someone asked this same problem here. Your mistake is with $tilde k_0$; you should have $tilde k_0=1$, as there is the empty composition.
$endgroup$
– Mike Earnest
Mar 22 at 16:57
$begingroup$
Someone asked this same problem here. Your mistake is with $tilde k_0$; you should have $tilde k_0=1$, as there is the empty composition.
$endgroup$
– Mike Earnest
Mar 22 at 16:57
$begingroup$
Thank you for your help. I haven't seen the other post, should I delete mine? If I use $tildek_0 = 1$ and $tildek_1 = 0$ i get the result I wanted to show. The last thing I don't fully understand is: Why does the empty composition matter for $tildek_0$ but not for $tildek_1$?
$endgroup$
– liouville
Mar 29 at 13:40
$begingroup$
Thank you for your help. I haven't seen the other post, should I delete mine? If I use $tildek_0 = 1$ and $tildek_1 = 0$ i get the result I wanted to show. The last thing I don't fully understand is: Why does the empty composition matter for $tildek_0$ but not for $tildek_1$?
$endgroup$
– liouville
Mar 29 at 13:40
$begingroup$
The empty composition has zero parts, so it contributes to $tilde k_0$. There are zero compositions with $1$ part summing to $1$; any composition with one part must sum to at least $2$. Therefore, $tilde k_1=0$.
$endgroup$
– Mike Earnest
Mar 29 at 15:12
$begingroup$
The empty composition has zero parts, so it contributes to $tilde k_0$. There are zero compositions with $1$ part summing to $1$; any composition with one part must sum to at least $2$. Therefore, $tilde k_1=0$.
$endgroup$
– Mike Earnest
Mar 29 at 15:12
add a comment |
0
active
oldest
votes
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%2f3158027%2fnumber-of-compositions-in-parts-less-equal-two-equals-number-of-compositions-in%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3158027%2fnumber-of-compositions-in-parts-less-equal-two-equals-number-of-compositions-in%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
2
$begingroup$
Someone asked this same problem here. Your mistake is with $tilde k_0$; you should have $tilde k_0=1$, as there is the empty composition.
$endgroup$
– Mike Earnest
Mar 22 at 16:57
$begingroup$
Thank you for your help. I haven't seen the other post, should I delete mine? If I use $tildek_0 = 1$ and $tildek_1 = 0$ i get the result I wanted to show. The last thing I don't fully understand is: Why does the empty composition matter for $tildek_0$ but not for $tildek_1$?
$endgroup$
– liouville
Mar 29 at 13:40
$begingroup$
The empty composition has zero parts, so it contributes to $tilde k_0$. There are zero compositions with $1$ part summing to $1$; any composition with one part must sum to at least $2$. Therefore, $tilde k_1=0$.
$endgroup$
– Mike Earnest
Mar 29 at 15:12