Mixing
${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$
up vote
2
down vote
favorite
In a proof, the author states that it is clear that:
Given $xgeq 1$ and $ n-x geq 1$ and finally also $ngeq 2$
$${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$$
This is not immediately clear to me. Of course, If I have $n$ objects and I split them up in $x$ and $n-x$ objects and then I choose to form pairs, amongst these
two subsets, I end up with fewer pairs than if I would consider the bigger set, so it is certainly smaller than $ n choose 2$.
I just don't see how it is smaller than $ {n-1choose 2}$.
combinatorics inequality binomial-coefficients
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
add a comment |
up vote
2
down vote
favorite
In a proof, the author states that it is clear that:
Given $xgeq 1$ and $ n-x geq 1$ and finally also $ngeq 2$
$${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$$
This is not immediately clear to me. Of course, If I have $n$ objects and I split them up in $x$ and $n-x$ objects and then I choose to form pairs, amongst these
two subsets, I end up with fewer pairs than if I would consider the bigger set, so it is certainly smaller than $ n choose 2$.
I just don't see how it is smaller than $ {n-1choose 2}$.
combinatorics inequality binomial-coefficients
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
Are there perhaps some restrictions on $x$? The inequality is certainly false when $x=0$ or $x=n$ (and $nge 2$).
– Mike Earnest
2 days ago
Yes $x geq 1$ and $n-x geq 1$ also $ngeq 2$, specifically we look at two disconnected graphs and all possible edges we can form. Then $n$ is the total amount of vertices and $x$ and $n-x$ are the vertices in both disconnected subgraphs.
– WesleyGroupshaveFeelingsToo
2 days ago
You can compute the difference, it factors to a simple expression.
– Martin R
2 days ago
1
Sorry you didn't ask there, I would explain it.
– greedoid
2 days ago
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
In a proof, the author states that it is clear that:
Given $xgeq 1$ and $ n-x geq 1$ and finally also $ngeq 2$
$${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$$
This is not immediately clear to me. Of course, If I have $n$ objects and I split them up in $x$ and $n-x$ objects and then I choose to form pairs, amongst these
two subsets, I end up with fewer pairs than if I would consider the bigger set, so it is certainly smaller than $ n choose 2$.
I just don't see how it is smaller than $ {n-1choose 2}$.
combinatorics inequality binomial-coefficients
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
In a proof, the author states that it is clear that:
Given $xgeq 1$ and $ n-x geq 1$ and finally also $ngeq 2$
$${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$$
This is not immediately clear to me. Of course, If I have $n$ objects and I split them up in $x$ and $n-x$ objects and then I choose to form pairs, amongst these
two subsets, I end up with fewer pairs than if I would consider the bigger set, so it is certainly smaller than $ n choose 2$.
I just don't see how it is smaller than $ {n-1choose 2}$.
combinatorics inequality binomial-coefficients
combinatorics inequality binomial-coefficients
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
edited 2 days ago
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
821218
Are there perhaps some restrictions on $x$? The inequality is certainly false when $x=0$ or $x=n$ (and $nge 2$).
– Mike Earnest
2 days ago
Yes $x geq 1$ and $n-x geq 1$ also $ngeq 2$, specifically we look at two disconnected graphs and all possible edges we can form. Then $n$ is the total amount of vertices and $x$ and $n-x$ are the vertices in both disconnected subgraphs.
– WesleyGroupshaveFeelingsToo
2 days ago
You can compute the difference, it factors to a simple expression.
– Martin R
2 days ago
1
Sorry you didn't ask there, I would explain it.
– greedoid
2 days ago
add a comment |
Are there perhaps some restrictions on $x$? The inequality is certainly false when $x=0$ or $x=n$ (and $nge 2$).
– Mike Earnest
2 days ago
Yes $x geq 1$ and $n-x geq 1$ also $ngeq 2$, specifically we look at two disconnected graphs and all possible edges we can form. Then $n$ is the total amount of vertices and $x$ and $n-x$ are the vertices in both disconnected subgraphs.
– WesleyGroupshaveFeelingsToo
2 days ago
You can compute the difference, it factors to a simple expression.
– Martin R
2 days ago
1
Sorry you didn't ask there, I would explain it.
– greedoid
2 days ago
Are there perhaps some restrictions on $x$? The inequality is certainly false when $x=0$ or $x=n$ (and $nge 2$).
– Mike Earnest
2 days ago
Are there perhaps some restrictions on $x$? The inequality is certainly false when $x=0$ or $x=n$ (and $nge 2$).
– Mike Earnest
2 days ago
Yes $x geq 1$ and $n-x geq 1$ also $ngeq 2$, specifically we look at two disconnected graphs and all possible edges we can form. Then $n$ is the total amount of vertices and $x$ and $n-x$ are the vertices in both disconnected subgraphs.
– WesleyGroupshaveFeelingsToo
2 days ago
Yes $x geq 1$ and $n-x geq 1$ also $ngeq 2$, specifically we look at two disconnected graphs and all possible edges we can form. Then $n$ is the total amount of vertices and $x$ and $n-x$ are the vertices in both disconnected subgraphs.
– WesleyGroupshaveFeelingsToo
2 days ago
You can compute the difference, it factors to a simple expression.
– Martin R
2 days ago
You can compute the difference, it factors to a simple expression.
– Martin R
2 days ago
1
1
Sorry you didn't ask there, I would explain it.
– greedoid
2 days ago
Sorry you didn't ask there, I would explain it.
– greedoid
2 days ago
add a comment |
6 Answers
6
active
oldest
votes
up vote
3
down vote
accepted
We need to prove that
$$frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}leqfrac{(n-1)(n-2)}{2}$$ or
$$x^2-x+n^2-(2x+1)n+x^2+xleq n^2-3n+2$$ or
$$x^2-nx+n-1leq0$$ or
$$(x-1)(x+1-n)leq0,$$
which is true for $1leq xleq n-1.$
answered 2 days ago
Michael Rozenberg
94.2k1588183
add a comment |
up vote
3
down vote
$$
f(x)=binom{x}{2}+binom{n-x}{2}=frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}=frac{x(x-1)+(n-x)(n-x-1)}{2}=ax^2+bx+c
$$
for some $a, b, cinmathbb R$ with $a>0$. Because $a>0$ (a convex parabola) its maximum must lie on the boundary of the set ${x:xgeq 1$ or $n-xgeq 1}$, that is $x=1$ or $n-x=1Leftrightarrow x=n-1$.
Finally we have
$$
f(x)leq f(1)=f(n-1)=binom{n-1}{2}
$$
answered 2 days ago
P De Donato
1686
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
3
down vote
Consider two complete graphs $K_x$ and $K_{n-x}$ and without loss of generality assume $x le n-x$.
Now suppose we merge the vertices into a larger complete graph $K_{n-1}$, adding all remaining edges between the two previously disjoint graphs, but removing one of the vertices as a "tax". The question amounts to showing that the resulting graph has at least as many edges as the two smaller graphs together.
Removing a vertex from $K_x$ destroys $x-1$ edges. On the other hand, each of the remaining $x-1$ vertices can be matched with a vertex in $K_{n-x}$ since $x-1 < n-x$, so when the two graphs are merged, the number of edges created is at least the number destroyed, with equality when $x=1$.
answered 2 days ago
Théophile
19.2k12946
add a comment |
up vote
2
down vote
Your method of splitting items in two groups actually gives an equality:
$$
binom{n}{2}=binom{x}{2}+binom{n-x}{2}+x(n-x)
$$
(we can either choose both items from the first group, or both from the second, or one from each).
Now,
begin{align}
binom{n-1}{2}&=binom{n}{2}-(n-1)\
&=binom{x}{2}+binom{n-x}{2}+x(n-x)-(n-1)
end{align}
and so your problem reduces to showing that $f(x)=x(n-x)-n+1$ is nonnegative for $1 leq x leq n-1$. For a fixed $n$, $f$ is quadratic in $x$ with roots $1$ and $n-1$; since the leading coefficient is negative, $f$ must be positive between the roots.
answered 2 days ago
Micah
29.4k1363104
add a comment |
up vote
1
down vote
begin{align}
{xchoose2} +{n-xchoose2}
&=frac{(x-1)x}2 +frac{(n-x)(n-x-1)}2 \
&=tfrac12 (x^2-x +n^2-nx-n -nx+x^2+x) \
&=tfrac12 (2x^2 -2nx+n^2-n) \
&=tfrac12 (2x(x-n) +n(n-1))
end{align}
Given $1 leq x leq n-1$ (and $x-n leq -1$), then
begin{align}
&leq tfrac12 (2(n-1)(-1) +n(n-1)) \
&=frac{(n-1)(n-2)}2 color{blue}{cdot frac{(n-3)!}{(n-3)!}} \
&=frac{(n-1)!}{2!(n-3)!} \
&={n-1choose2}.
end{align}
answered 2 days ago
Rócherz
2,5112620
add a comment |
up vote
0
down vote
Writing them out,
${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$
becomes
$x(x-1)+(n-x)(n-x-1) le (n-1)(n-2)
$
or
$x^2-x+n^2-n(x+x+1)+x^2-x
le n^2-3n+2
$
or
$2x^2-2x
le n(2x+1-3)+2
$
or
$2x^2-2x
le n(2x-2)+2
$
or
$x^2-x
le n(x-1)+1
$
or
$x(x-1)
le n(x-1)+1
$
or
$(x-n)(x-1)
le 1
$
which is true for
$x ge 1$
and
$x le n-1$.
This is false for $x=0$
or
$x=n$
where this algebra does not work.
answered 2 days ago
marty cohen
71.3k546123
add a comment |
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
We need to prove that
$$frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}leqfrac{(n-1)(n-2)}{2}$$ or
$$x^2-x+n^2-(2x+1)n+x^2+xleq n^2-3n+2$$ or
$$x^2-nx+n-1leq0$$ or
$$(x-1)(x+1-n)leq0,$$
which is true for $1leq xleq n-1.$
answered 2 days ago
Michael Rozenberg
94.2k1588183
add a comment |
up vote
3
down vote
accepted
We need to prove that
$$frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}leqfrac{(n-1)(n-2)}{2}$$ or
$$x^2-x+n^2-(2x+1)n+x^2+xleq n^2-3n+2$$ or
$$x^2-nx+n-1leq0$$ or
$$(x-1)(x+1-n)leq0,$$
which is true for $1leq xleq n-1.$
answered 2 days ago
Michael Rozenberg
94.2k1588183
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
We need to prove that
$$frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}leqfrac{(n-1)(n-2)}{2}$$ or
$$x^2-x+n^2-(2x+1)n+x^2+xleq n^2-3n+2$$ or
$$x^2-nx+n-1leq0$$ or
$$(x-1)(x+1-n)leq0,$$
which is true for $1leq xleq n-1.$
answered 2 days ago
Michael Rozenberg
94.2k1588183
We need to prove that
$$frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}leqfrac{(n-1)(n-2)}{2}$$ or
$$x^2-x+n^2-(2x+1)n+x^2+xleq n^2-3n+2$$ or
$$x^2-nx+n-1leq0$$ or
$$(x-1)(x+1-n)leq0,$$
which is true for $1leq xleq n-1.$
answered 2 days ago
Michael Rozenberg
94.2k1588183
answered 2 days ago
Michael Rozenberg
94.2k1588183
answered 2 days ago
Michael Rozenberg
94.2k1588183
answered 2 days ago
Michael Rozenberg
94.2k1588183
94.2k1588183
add a comment |
add a comment |
up vote
3
down vote
$$
f(x)=binom{x}{2}+binom{n-x}{2}=frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}=frac{x(x-1)+(n-x)(n-x-1)}{2}=ax^2+bx+c
$$
for some $a, b, cinmathbb R$ with $a>0$. Because $a>0$ (a convex parabola) its maximum must lie on the boundary of the set ${x:xgeq 1$ or $n-xgeq 1}$, that is $x=1$ or $n-x=1Leftrightarrow x=n-1$.
Finally we have
$$
f(x)leq f(1)=f(n-1)=binom{n-1}{2}
$$
answered 2 days ago
P De Donato
1686
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
3
down vote
$$
f(x)=binom{x}{2}+binom{n-x}{2}=frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}=frac{x(x-1)+(n-x)(n-x-1)}{2}=ax^2+bx+c
$$
for some $a, b, cinmathbb R$ with $a>0$. Because $a>0$ (a convex parabola) its maximum must lie on the boundary of the set ${x:xgeq 1$ or $n-xgeq 1}$, that is $x=1$ or $n-x=1Leftrightarrow x=n-1$.
Finally we have
$$
f(x)leq f(1)=f(n-1)=binom{n-1}{2}
$$
answered 2 days ago
P De Donato
1686
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
3
down vote
up vote
3
down vote
$$
f(x)=binom{x}{2}+binom{n-x}{2}=frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}=frac{x(x-1)+(n-x)(n-x-1)}{2}=ax^2+bx+c
$$
for some $a, b, cinmathbb R$ with $a>0$. Because $a>0$ (a convex parabola) its maximum must lie on the boundary of the set ${x:xgeq 1$ or $n-xgeq 1}$, that is $x=1$ or $n-x=1Leftrightarrow x=n-1$.
Finally we have
$$
f(x)leq f(1)=f(n-1)=binom{n-1}{2}
$$
answered 2 days ago
P De Donato
1686
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$$
f(x)=binom{x}{2}+binom{n-x}{2}=frac{x(x-1)}{2}+frac{(n-x)(n-x-1)}{2}=frac{x(x-1)+(n-x)(n-x-1)}{2}=ax^2+bx+c
$$
for some $a, b, cinmathbb R$ with $a>0$. Because $a>0$ (a convex parabola) its maximum must lie on the boundary of the set ${x:xgeq 1$ or $n-xgeq 1}$, that is $x=1$ or $n-x=1Leftrightarrow x=n-1$.
Finally we have
$$
f(x)leq f(1)=f(n-1)=binom{n-1}{2}
$$
answered 2 days ago
P De Donato
1686
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 days ago
P De Donato
1686
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 days ago
P De Donato
1686
answered 2 days ago
P De Donato
1686
1686
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
P De Donato is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
up vote
3
down vote
Consider two complete graphs $K_x$ and $K_{n-x}$ and without loss of generality assume $x le n-x$.
Now suppose we merge the vertices into a larger complete graph $K_{n-1}$, adding all remaining edges between the two previously disjoint graphs, but removing one of the vertices as a "tax". The question amounts to showing that the resulting graph has at least as many edges as the two smaller graphs together.
Removing a vertex from $K_x$ destroys $x-1$ edges. On the other hand, each of the remaining $x-1$ vertices can be matched with a vertex in $K_{n-x}$ since $x-1 < n-x$, so when the two graphs are merged, the number of edges created is at least the number destroyed, with equality when $x=1$.
answered 2 days ago
Théophile
19.2k12946
add a comment |
up vote
3
down vote
Consider two complete graphs $K_x$ and $K_{n-x}$ and without loss of generality assume $x le n-x$.
Now suppose we merge the vertices into a larger complete graph $K_{n-1}$, adding all remaining edges between the two previously disjoint graphs, but removing one of the vertices as a "tax". The question amounts to showing that the resulting graph has at least as many edges as the two smaller graphs together.
Removing a vertex from $K_x$ destroys $x-1$ edges. On the other hand, each of the remaining $x-1$ vertices can be matched with a vertex in $K_{n-x}$ since $x-1 < n-x$, so when the two graphs are merged, the number of edges created is at least the number destroyed, with equality when $x=1$.
answered 2 days ago
Théophile
19.2k12946
add a comment |
up vote
3
down vote
up vote
3
down vote
Consider two complete graphs $K_x$ and $K_{n-x}$ and without loss of generality assume $x le n-x$.
Now suppose we merge the vertices into a larger complete graph $K_{n-1}$, adding all remaining edges between the two previously disjoint graphs, but removing one of the vertices as a "tax". The question amounts to showing that the resulting graph has at least as many edges as the two smaller graphs together.
Removing a vertex from $K_x$ destroys $x-1$ edges. On the other hand, each of the remaining $x-1$ vertices can be matched with a vertex in $K_{n-x}$ since $x-1 < n-x$, so when the two graphs are merged, the number of edges created is at least the number destroyed, with equality when $x=1$.
answered 2 days ago
Théophile
19.2k12946
Consider two complete graphs $K_x$ and $K_{n-x}$ and without loss of generality assume $x le n-x$.
Now suppose we merge the vertices into a larger complete graph $K_{n-1}$, adding all remaining edges between the two previously disjoint graphs, but removing one of the vertices as a "tax". The question amounts to showing that the resulting graph has at least as many edges as the two smaller graphs together.
Removing a vertex from $K_x$ destroys $x-1$ edges. On the other hand, each of the remaining $x-1$ vertices can be matched with a vertex in $K_{n-x}$ since $x-1 < n-x$, so when the two graphs are merged, the number of edges created is at least the number destroyed, with equality when $x=1$.
answered 2 days ago
Théophile
19.2k12946
answered 2 days ago
Théophile
19.2k12946
answered 2 days ago
Théophile
19.2k12946
answered 2 days ago
Théophile
19.2k12946
19.2k12946
add a comment |
add a comment |
up vote
2
down vote
Your method of splitting items in two groups actually gives an equality:
$$
binom{n}{2}=binom{x}{2}+binom{n-x}{2}+x(n-x)
$$
(we can either choose both items from the first group, or both from the second, or one from each).
Now,
begin{align}
binom{n-1}{2}&=binom{n}{2}-(n-1)\
&=binom{x}{2}+binom{n-x}{2}+x(n-x)-(n-1)
end{align}
and so your problem reduces to showing that $f(x)=x(n-x)-n+1$ is nonnegative for $1 leq x leq n-1$. For a fixed $n$, $f$ is quadratic in $x$ with roots $1$ and $n-1$; since the leading coefficient is negative, $f$ must be positive between the roots.
answered 2 days ago
Micah
29.4k1363104
add a comment |
up vote
2
down vote
Your method of splitting items in two groups actually gives an equality:
$$
binom{n}{2}=binom{x}{2}+binom{n-x}{2}+x(n-x)
$$
(we can either choose both items from the first group, or both from the second, or one from each).
Now,
begin{align}
binom{n-1}{2}&=binom{n}{2}-(n-1)\
&=binom{x}{2}+binom{n-x}{2}+x(n-x)-(n-1)
end{align}
and so your problem reduces to showing that $f(x)=x(n-x)-n+1$ is nonnegative for $1 leq x leq n-1$. For a fixed $n$, $f$ is quadratic in $x$ with roots $1$ and $n-1$; since the leading coefficient is negative, $f$ must be positive between the roots.
answered 2 days ago
Micah
29.4k1363104
add a comment |
up vote
2
down vote
up vote
2
down vote
Your method of splitting items in two groups actually gives an equality:
$$
binom{n}{2}=binom{x}{2}+binom{n-x}{2}+x(n-x)
$$
(we can either choose both items from the first group, or both from the second, or one from each).
Now,
begin{align}
binom{n-1}{2}&=binom{n}{2}-(n-1)\
&=binom{x}{2}+binom{n-x}{2}+x(n-x)-(n-1)
end{align}
and so your problem reduces to showing that $f(x)=x(n-x)-n+1$ is nonnegative for $1 leq x leq n-1$. For a fixed $n$, $f$ is quadratic in $x$ with roots $1$ and $n-1$; since the leading coefficient is negative, $f$ must be positive between the roots.
answered 2 days ago
Micah
29.4k1363104
Your method of splitting items in two groups actually gives an equality:
$$
binom{n}{2}=binom{x}{2}+binom{n-x}{2}+x(n-x)
$$
(we can either choose both items from the first group, or both from the second, or one from each).
Now,
begin{align}
binom{n-1}{2}&=binom{n}{2}-(n-1)\
&=binom{x}{2}+binom{n-x}{2}+x(n-x)-(n-1)
end{align}
and so your problem reduces to showing that $f(x)=x(n-x)-n+1$ is nonnegative for $1 leq x leq n-1$. For a fixed $n$, $f$ is quadratic in $x$ with roots $1$ and $n-1$; since the leading coefficient is negative, $f$ must be positive between the roots.
answered 2 days ago
Micah
29.4k1363104
answered 2 days ago
Micah
29.4k1363104
answered 2 days ago
Micah
29.4k1363104
answered 2 days ago
Micah
29.4k1363104
29.4k1363104
add a comment |
add a comment |
up vote
1
down vote
begin{align}
{xchoose2} +{n-xchoose2}
&=frac{(x-1)x}2 +frac{(n-x)(n-x-1)}2 \
&=tfrac12 (x^2-x +n^2-nx-n -nx+x^2+x) \
&=tfrac12 (2x^2 -2nx+n^2-n) \
&=tfrac12 (2x(x-n) +n(n-1))
end{align}
Given $1 leq x leq n-1$ (and $x-n leq -1$), then
begin{align}
&leq tfrac12 (2(n-1)(-1) +n(n-1)) \
&=frac{(n-1)(n-2)}2 color{blue}{cdot frac{(n-3)!}{(n-3)!}} \
&=frac{(n-1)!}{2!(n-3)!} \
&={n-1choose2}.
end{align}
answered 2 days ago
Rócherz
2,5112620
add a comment |
up vote
1
down vote
begin{align}
{xchoose2} +{n-xchoose2}
&=frac{(x-1)x}2 +frac{(n-x)(n-x-1)}2 \
&=tfrac12 (x^2-x +n^2-nx-n -nx+x^2+x) \
&=tfrac12 (2x^2 -2nx+n^2-n) \
&=tfrac12 (2x(x-n) +n(n-1))
end{align}
Given $1 leq x leq n-1$ (and $x-n leq -1$), then
begin{align}
&leq tfrac12 (2(n-1)(-1) +n(n-1)) \
&=frac{(n-1)(n-2)}2 color{blue}{cdot frac{(n-3)!}{(n-3)!}} \
&=frac{(n-1)!}{2!(n-3)!} \
&={n-1choose2}.
end{align}
answered 2 days ago
Rócherz
2,5112620
add a comment |
up vote
1
down vote
up vote
1
down vote
begin{align}
{xchoose2} +{n-xchoose2}
&=frac{(x-1)x}2 +frac{(n-x)(n-x-1)}2 \
&=tfrac12 (x^2-x +n^2-nx-n -nx+x^2+x) \
&=tfrac12 (2x^2 -2nx+n^2-n) \
&=tfrac12 (2x(x-n) +n(n-1))
end{align}
Given $1 leq x leq n-1$ (and $x-n leq -1$), then
begin{align}
&leq tfrac12 (2(n-1)(-1) +n(n-1)) \
&=frac{(n-1)(n-2)}2 color{blue}{cdot frac{(n-3)!}{(n-3)!}} \
&=frac{(n-1)!}{2!(n-3)!} \
&={n-1choose2}.
end{align}
answered 2 days ago
Rócherz
2,5112620
begin{align}
{xchoose2} +{n-xchoose2}
&=frac{(x-1)x}2 +frac{(n-x)(n-x-1)}2 \
&=tfrac12 (x^2-x +n^2-nx-n -nx+x^2+x) \
&=tfrac12 (2x^2 -2nx+n^2-n) \
&=tfrac12 (2x(x-n) +n(n-1))
end{align}
Given $1 leq x leq n-1$ (and $x-n leq -1$), then
begin{align}
&leq tfrac12 (2(n-1)(-1) +n(n-1)) \
&=frac{(n-1)(n-2)}2 color{blue}{cdot frac{(n-3)!}{(n-3)!}} \
&=frac{(n-1)!}{2!(n-3)!} \
&={n-1choose2}.
end{align}
answered 2 days ago
Rócherz
2,5112620
edited 2 days ago
answered 2 days ago
Rócherz
2,5112620
answered 2 days ago
Rócherz
2,5112620
answered 2 days ago
Rócherz
2,5112620
2,5112620
add a comment |
add a comment |
up vote
0
down vote
Writing them out,
${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$
becomes
$x(x-1)+(n-x)(n-x-1) le (n-1)(n-2)
$
or
$x^2-x+n^2-n(x+x+1)+x^2-x
le n^2-3n+2
$
or
$2x^2-2x
le n(2x+1-3)+2
$
or
$2x^2-2x
le n(2x-2)+2
$
or
$x^2-x
le n(x-1)+1
$
or
$x(x-1)
le n(x-1)+1
$
or
$(x-n)(x-1)
le 1
$
which is true for
$x ge 1$
and
$x le n-1$.
This is false for $x=0$
or
$x=n$
where this algebra does not work.
answered 2 days ago
marty cohen
71.3k546123
add a comment |
up vote
0
down vote
Writing them out,
${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$
becomes
$x(x-1)+(n-x)(n-x-1) le (n-1)(n-2)
$
or
$x^2-x+n^2-n(x+x+1)+x^2-x
le n^2-3n+2
$
or
$2x^2-2x
le n(2x+1-3)+2
$
or
$2x^2-2x
le n(2x-2)+2
$
or
$x^2-x
le n(x-1)+1
$
or
$x(x-1)
le n(x-1)+1
$
or
$(x-n)(x-1)
le 1
$
which is true for
$x ge 1$
and
$x le n-1$.
This is false for $x=0$
or
$x=n$
where this algebra does not work.
answered 2 days ago
marty cohen
71.3k546123
add a comment |
up vote
0
down vote
up vote
0
down vote
Writing them out,
${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$
becomes
$x(x-1)+(n-x)(n-x-1) le (n-1)(n-2)
$
or
$x^2-x+n^2-n(x+x+1)+x^2-x
le n^2-3n+2
$
or
$2x^2-2x
le n(2x+1-3)+2
$
or
$2x^2-2x
le n(2x-2)+2
$
or
$x^2-x
le n(x-1)+1
$
or
$x(x-1)
le n(x-1)+1
$
or
$(x-n)(x-1)
le 1
$
which is true for
$x ge 1$
and
$x le n-1$.
This is false for $x=0$
or
$x=n$
where this algebra does not work.
answered 2 days ago
marty cohen
71.3k546123
Writing them out,
${xchoose 2}+{n-xchoose 2} leq {n-1choose 2}$
becomes
$x(x-1)+(n-x)(n-x-1) le (n-1)(n-2)
$
or
$x^2-x+n^2-n(x+x+1)+x^2-x
le n^2-3n+2
$
or
$2x^2-2x
le n(2x+1-3)+2
$
or
$2x^2-2x
le n(2x-2)+2
$
or
$x^2-x
le n(x-1)+1
$
or
$x(x-1)
le n(x-1)+1
$
or
$(x-n)(x-1)
le 1
$
which is true for
$x ge 1$
and
$x le n-1$.
This is false for $x=0$
or
$x=n$
where this algebra does not work.
answered 2 days ago
marty cohen
71.3k546123
answered 2 days ago
marty cohen
71.3k546123
answered 2 days ago
marty cohen
71.3k546123
answered 2 days ago
marty cohen
71.3k546123
71.3k546123
add a comment |
add a comment |
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%2f3005453%2fx-choose-2n-x-choose-2-leq-n-1-choose-2%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
Are there perhaps some restrictions on $x$? The inequality is certainly false when $x=0$ or $x=n$ (and $nge 2$).
– Mike Earnest
2 days ago
Yes $x geq 1$ and $n-x geq 1$ also $ngeq 2$, specifically we look at two disconnected graphs and all possible edges we can form. Then $n$ is the total amount of vertices and $x$ and $n-x$ are the vertices in both disconnected subgraphs.
– WesleyGroupshaveFeelingsToo
2 days ago
You can compute the difference, it factors to a simple expression.
– Martin R
2 days ago
1
Sorry you didn't ask there, I would explain it.
– greedoid
2 days ago