In how many ways can I write $0$ as a sum of $n; 0s, 1s ;text{and}; -1s?$
In how many ways can I write $0$ as a sum of $n; 0s, 1s ;text{or}; -1s?$ (Taking the order into account).
I suspect there is no closed formula to express the result, but I'd like someone to confirm it, or deny it.
Edit:
e.g., if $n=3$
$$begin{aligned}0&=;;;0+0+0,\ 0&=;;;1-1+0,\ 0&=;;;1+0-1,\ 0&=;;;0+1-1,\ 0&=-1+1+0,\ 0&=-1+0+1,\ 0&=;;;0-1+1.end{aligned}$$
So for $n=3;$ there are $7$ ways.
combinatorics
edited 14 mins ago
user376343
2,7982822
asked 5 hours ago
Lucio Tanzini
17514
|
show 1 more comment
In how many ways can I write $0$ as a sum of $n; 0s, 1s ;text{or}; -1s?$ (Taking the order into account).
I suspect there is no closed formula to express the result, but I'd like someone to confirm it, or deny it.
Edit:
e.g., if $n=3$
$$begin{aligned}0&=;;;0+0+0,\ 0&=;;;1-1+0,\ 0&=;;;1+0-1,\ 0&=;;;0+1-1,\ 0&=-1+1+0,\ 0&=-1+0+1,\ 0&=;;;0-1+1.end{aligned}$$
So for $n=3;$ there are $7$ ways.
combinatorics
edited 14 mins ago
user376343
2,7982822
asked 5 hours ago
Lucio Tanzini
17514
1
Set up a recurrence perhaps.
– paw88789
5 hours ago
do you mean n each or a total of n?
– player100
5 hours ago
Sorry I meant that in total, the number of 0's, 1's and -1's is n
– Lucio Tanzini
5 hours ago
@MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer!
– timtfj
5 hours ago
I'd start here: for each $n$, we can choose how many times $0$ occurs ,and how many times $1$ occurs. $-1$ then has to match $1$. So if $0$ is used $r$ times and $1$ is used $s$ times, $r=n-2s$.Then for each choice of $r$ and $s$ you've got a defined permutation problem, with $r, s$ and $s$ items..
– timtfj
4 hours ago
|
show 1 more comment
In how many ways can I write $0$ as a sum of $n; 0s, 1s ;text{or}; -1s?$ (Taking the order into account).
I suspect there is no closed formula to express the result, but I'd like someone to confirm it, or deny it.
Edit:
e.g., if $n=3$
$$begin{aligned}0&=;;;0+0+0,\ 0&=;;;1-1+0,\ 0&=;;;1+0-1,\ 0&=;;;0+1-1,\ 0&=-1+1+0,\ 0&=-1+0+1,\ 0&=;;;0-1+1.end{aligned}$$
So for $n=3;$ there are $7$ ways.
combinatorics
edited 14 mins ago
user376343
2,7982822
asked 5 hours ago
Lucio Tanzini
17514
In how many ways can I write $0$ as a sum of $n; 0s, 1s ;text{or}; -1s?$ (Taking the order into account).
I suspect there is no closed formula to express the result, but I'd like someone to confirm it, or deny it.
Edit:
e.g., if $n=3$
$$begin{aligned}0&=;;;0+0+0,\ 0&=;;;1-1+0,\ 0&=;;;1+0-1,\ 0&=;;;0+1-1,\ 0&=-1+1+0,\ 0&=-1+0+1,\ 0&=;;;0-1+1.end{aligned}$$
So for $n=3;$ there are $7$ ways.
combinatorics
combinatorics
edited 14 mins ago
user376343
2,7982822
asked 5 hours ago
Lucio Tanzini
17514
edited 14 mins ago
user376343
2,7982822
asked 5 hours ago
Lucio Tanzini
17514
edited 14 mins ago
user376343
2,7982822
edited 14 mins ago
user376343
2,7982822
edited 14 mins ago
user376343
2,7982822
2,7982822
asked 5 hours ago
Lucio Tanzini
17514
asked 5 hours ago
Lucio Tanzini
17514
asked 5 hours ago
Lucio Tanzini
17514
17514
1
Set up a recurrence perhaps.
– paw88789
5 hours ago
do you mean n each or a total of n?
– player100
5 hours ago
Sorry I meant that in total, the number of 0's, 1's and -1's is n
– Lucio Tanzini
5 hours ago
@MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer!
– timtfj
5 hours ago
I'd start here: for each $n$, we can choose how many times $0$ occurs ,and how many times $1$ occurs. $-1$ then has to match $1$. So if $0$ is used $r$ times and $1$ is used $s$ times, $r=n-2s$.Then for each choice of $r$ and $s$ you've got a defined permutation problem, with $r, s$ and $s$ items..
– timtfj
4 hours ago
|
show 1 more comment
1
Set up a recurrence perhaps.
– paw88789
5 hours ago
do you mean n each or a total of n?
– player100
5 hours ago
Sorry I meant that in total, the number of 0's, 1's and -1's is n
– Lucio Tanzini
5 hours ago
@MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer!
– timtfj
5 hours ago
I'd start here: for each $n$, we can choose how many times $0$ occurs ,and how many times $1$ occurs. $-1$ then has to match $1$. So if $0$ is used $r$ times and $1$ is used $s$ times, $r=n-2s$.Then for each choice of $r$ and $s$ you've got a defined permutation problem, with $r, s$ and $s$ items..
– timtfj
4 hours ago
1
1
Set up a recurrence perhaps.
– paw88789
5 hours ago
Set up a recurrence perhaps.
– paw88789
5 hours ago
do you mean n each or a total of n?
– player100
5 hours ago
do you mean n each or a total of n?
– player100
5 hours ago
Sorry I meant that in total, the number of 0's, 1's and -1's is n
– Lucio Tanzini
5 hours ago
Sorry I meant that in total, the number of 0's, 1's and -1's is n
– Lucio Tanzini
5 hours ago
@MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer!
– timtfj
5 hours ago
@MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer!
– timtfj
5 hours ago
I'd start here: for each $n$, we can choose how many times $0$ occurs ,and how many times $1$ occurs. $-1$ then has to match $1$. So if $0$ is used $r$ times and $1$ is used $s$ times, $r=n-2s$.Then for each choice of $r$ and $s$ you've got a defined permutation problem, with $r, s$ and $s$ items..
– timtfj
4 hours ago
I'd start here: for each $n$, we can choose how many times $0$ occurs ,and how many times $1$ occurs. $-1$ then has to match $1$. So if $0$ is used $r$ times and $1$ is used $s$ times, $r=n-2s$.Then for each choice of $r$ and $s$ you've got a defined permutation problem, with $r, s$ and $s$ items..
– timtfj
4 hours ago
|
show 1 more comment
2 Answers
2
active
oldest
votes
$s(n) = sum_{k=0}^{n/2} binom{n}{n-2k} cdot binom{2k}{k}$ The first term is the number of ways to arrange the zeroes, and then the second term arranges the parities. Now, we can simplify further:
$s(n) = sum_{k=0}^{n/2} frac{2k!}{2k!} cdot frac{n!}{(n-2k)!(k!)(k!)} = sum_{k=0}^{n/2} frac{n!}{(n-2k)!(k!)(k!)}$
Edit: put a few values into the OIES and came across trinomial coeffecients. In particular, s(n) is the n-th central trinomial coefficient, which has several closed forms, which you can find in the second link.
answered 3 hours ago
Zachary Hunter
595
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$.
– timtfj
3 hours ago
Whoops yeah I forgot a term
– Zachary Hunter
3 hours ago
Yes, I got the same formula. Do you think It can be simplified into a closed formula?
– Lucio Tanzini
2 hours ago
@LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it.
– Zachary Hunter
2 hours ago
Update: found closed form.
– Zachary Hunter
1 hour ago
add a comment |
The number of $0s, 1s$ and $-1s$ possible for a particular $n$ can be seen by the number of solutions to:
$$2p+q=n| p,q in Bbb Z^+$$
This can be done in $frac{n+1}{2}$ ways for odd $n$ and $frac{n+2}{2}$ ways for even $n$
You'll just need to account for positioning after this.
answered 5 hours ago
Rhys Hughes
4,7961327
Yes, but I'm afraid positioning is the main problem Indeed
– Lucio Tanzini
4 hours ago
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%2f3056013%2fin-how-many-ways-can-i-write-0-as-a-sum-of-n-0s-1s-textand-1s%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$s(n) = sum_{k=0}^{n/2} binom{n}{n-2k} cdot binom{2k}{k}$ The first term is the number of ways to arrange the zeroes, and then the second term arranges the parities. Now, we can simplify further:
$s(n) = sum_{k=0}^{n/2} frac{2k!}{2k!} cdot frac{n!}{(n-2k)!(k!)(k!)} = sum_{k=0}^{n/2} frac{n!}{(n-2k)!(k!)(k!)}$
Edit: put a few values into the OIES and came across trinomial coeffecients. In particular, s(n) is the n-th central trinomial coefficient, which has several closed forms, which you can find in the second link.
answered 3 hours ago
Zachary Hunter
595
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$.
– timtfj
3 hours ago
Whoops yeah I forgot a term
– Zachary Hunter
3 hours ago
Yes, I got the same formula. Do you think It can be simplified into a closed formula?
– Lucio Tanzini
2 hours ago
@LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it.
– Zachary Hunter
2 hours ago
Update: found closed form.
– Zachary Hunter
1 hour ago
add a comment |
$s(n) = sum_{k=0}^{n/2} binom{n}{n-2k} cdot binom{2k}{k}$ The first term is the number of ways to arrange the zeroes, and then the second term arranges the parities. Now, we can simplify further:
$s(n) = sum_{k=0}^{n/2} frac{2k!}{2k!} cdot frac{n!}{(n-2k)!(k!)(k!)} = sum_{k=0}^{n/2} frac{n!}{(n-2k)!(k!)(k!)}$
Edit: put a few values into the OIES and came across trinomial coeffecients. In particular, s(n) is the n-th central trinomial coefficient, which has several closed forms, which you can find in the second link.
answered 3 hours ago
Zachary Hunter
595
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$.
– timtfj
3 hours ago
Whoops yeah I forgot a term
– Zachary Hunter
3 hours ago
Yes, I got the same formula. Do you think It can be simplified into a closed formula?
– Lucio Tanzini
2 hours ago
@LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it.
– Zachary Hunter
2 hours ago
Update: found closed form.
– Zachary Hunter
1 hour ago
add a comment |
$s(n) = sum_{k=0}^{n/2} binom{n}{n-2k} cdot binom{2k}{k}$ The first term is the number of ways to arrange the zeroes, and then the second term arranges the parities. Now, we can simplify further:
$s(n) = sum_{k=0}^{n/2} frac{2k!}{2k!} cdot frac{n!}{(n-2k)!(k!)(k!)} = sum_{k=0}^{n/2} frac{n!}{(n-2k)!(k!)(k!)}$
Edit: put a few values into the OIES and came across trinomial coeffecients. In particular, s(n) is the n-th central trinomial coefficient, which has several closed forms, which you can find in the second link.
answered 3 hours ago
Zachary Hunter
595
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$s(n) = sum_{k=0}^{n/2} binom{n}{n-2k} cdot binom{2k}{k}$ The first term is the number of ways to arrange the zeroes, and then the second term arranges the parities. Now, we can simplify further:
$s(n) = sum_{k=0}^{n/2} frac{2k!}{2k!} cdot frac{n!}{(n-2k)!(k!)(k!)} = sum_{k=0}^{n/2} frac{n!}{(n-2k)!(k!)(k!)}$
Edit: put a few values into the OIES and came across trinomial coeffecients. In particular, s(n) is the n-th central trinomial coefficient, which has several closed forms, which you can find in the second link.
answered 3 hours ago
Zachary Hunter
595
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 27 mins ago
answered 3 hours ago
Zachary Hunter
595
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 3 hours ago
Zachary Hunter
595
answered 3 hours ago
Zachary Hunter
595
595
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Zachary Hunter is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$.
– timtfj
3 hours ago
Whoops yeah I forgot a term
– Zachary Hunter
3 hours ago
Yes, I got the same formula. Do you think It can be simplified into a closed formula?
– Lucio Tanzini
2 hours ago
@LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it.
– Zachary Hunter
2 hours ago
Update: found closed form.
– Zachary Hunter
1 hour ago
add a comment |
This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$.
– timtfj
3 hours ago
Whoops yeah I forgot a term
– Zachary Hunter
3 hours ago
Yes, I got the same formula. Do you think It can be simplified into a closed formula?
– Lucio Tanzini
2 hours ago
@LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it.
– Zachary Hunter
2 hours ago
Update: found closed form.
– Zachary Hunter
1 hour ago
This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$.
– timtfj
3 hours ago
This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$.
– timtfj
3 hours ago
Whoops yeah I forgot a term
– Zachary Hunter
3 hours ago
Whoops yeah I forgot a term
– Zachary Hunter
3 hours ago
Yes, I got the same formula. Do you think It can be simplified into a closed formula?
– Lucio Tanzini
2 hours ago
Yes, I got the same formula. Do you think It can be simplified into a closed formula?
– Lucio Tanzini
2 hours ago
@LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it.
– Zachary Hunter
2 hours ago
@LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it.
– Zachary Hunter
2 hours ago
Update: found closed form.
– Zachary Hunter
1 hour ago
Update: found closed form.
– Zachary Hunter
1 hour ago
add a comment |
The number of $0s, 1s$ and $-1s$ possible for a particular $n$ can be seen by the number of solutions to:
$$2p+q=n| p,q in Bbb Z^+$$
This can be done in $frac{n+1}{2}$ ways for odd $n$ and $frac{n+2}{2}$ ways for even $n$
You'll just need to account for positioning after this.
answered 5 hours ago
Rhys Hughes
4,7961327
Yes, but I'm afraid positioning is the main problem Indeed
– Lucio Tanzini
4 hours ago
add a comment |
The number of $0s, 1s$ and $-1s$ possible for a particular $n$ can be seen by the number of solutions to:
$$2p+q=n| p,q in Bbb Z^+$$
This can be done in $frac{n+1}{2}$ ways for odd $n$ and $frac{n+2}{2}$ ways for even $n$
You'll just need to account for positioning after this.
answered 5 hours ago
Rhys Hughes
4,7961327
Yes, but I'm afraid positioning is the main problem Indeed
– Lucio Tanzini
4 hours ago
add a comment |
The number of $0s, 1s$ and $-1s$ possible for a particular $n$ can be seen by the number of solutions to:
$$2p+q=n| p,q in Bbb Z^+$$
This can be done in $frac{n+1}{2}$ ways for odd $n$ and $frac{n+2}{2}$ ways for even $n$
You'll just need to account for positioning after this.
answered 5 hours ago
Rhys Hughes
4,7961327
The number of $0s, 1s$ and $-1s$ possible for a particular $n$ can be seen by the number of solutions to:
$$2p+q=n| p,q in Bbb Z^+$$
This can be done in $frac{n+1}{2}$ ways for odd $n$ and $frac{n+2}{2}$ ways for even $n$
You'll just need to account for positioning after this.
answered 5 hours ago
Rhys Hughes
4,7961327
edited 4 hours ago
answered 5 hours ago
Rhys Hughes
4,7961327
answered 5 hours ago
Rhys Hughes
4,7961327
answered 5 hours ago
Rhys Hughes
4,7961327
4,7961327
Yes, but I'm afraid positioning is the main problem Indeed
– Lucio Tanzini
4 hours ago
add a comment |
Yes, but I'm afraid positioning is the main problem Indeed
– Lucio Tanzini
4 hours ago
Yes, but I'm afraid positioning is the main problem Indeed
– Lucio Tanzini
4 hours ago
Yes, but I'm afraid positioning is the main problem Indeed
– Lucio Tanzini
4 hours ago
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3056013%2fin-how-many-ways-can-i-write-0-as-a-sum-of-n-0s-1s-textand-1s%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
1
Set up a recurrence perhaps.
– paw88789
5 hours ago
do you mean n each or a total of n?
– player100
5 hours ago
Sorry I meant that in total, the number of 0's, 1's and -1's is n
– Lucio Tanzini
5 hours ago
@MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer!
– timtfj
5 hours ago
I'd start here: for each $n$, we can choose how many times $0$ occurs ,and how many times $1$ occurs. $-1$ then has to match $1$. So if $0$ is used $r$ times and $1$ is used $s$ times, $r=n-2s$.Then for each choice of $r$ and $s$ you've got a defined permutation problem, with $r, s$ and $s$ items..
– timtfj
4 hours ago