Mixing
Let X=set of all pairs (i,j) with $i neq j$. Counting subsets L of X that have equal number of pairs starting with k as pairs ending with k
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Let $X=(i,j); i,j=1, dots, n, i neq j$ be the set of pairs. How do you count the subsets $L$ of $X$ that satisfy this property: for every $k=1,dots, n$ there are as many elements of $L$ with first coordinate $k$ as with second coordinate equal to $k$?
Here's an example. For n=3, the subset (1,2),(2,3),(3,1) satisfies this property. Same as with (1,3),(3,1), and so on. I think there are 9 such L, including the empty set for this case.
combinatorics combinations
asked Jul 14 at 22:42
Camilo
745
add a comment |Â
up vote
3
down vote
favorite
Let $X=(i,j); i,j=1, dots, n, i neq j$ be the set of pairs. How do you count the subsets $L$ of $X$ that satisfy this property: for every $k=1,dots, n$ there are as many elements of $L$ with first coordinate $k$ as with second coordinate equal to $k$?
Here's an example. For n=3, the subset (1,2),(2,3),(3,1) satisfies this property. Same as with (1,3),(3,1), and so on. I think there are 9 such L, including the empty set for this case.
combinatorics combinations
asked Jul 14 at 22:42
Camilo
745
i can't offer much help, but one approach might be to label n nodes and represent the coordinates as vectors on a directed graph
– Barycentric_Bash
Jul 14 at 23:42
I count $10$ for $n=3$: $2^3=8$ possibilities with each of the three two-cycles either there or not, and two different orientations for a three-cycle.
– joriki
Jul 15 at 7:44
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Let $X=(i,j); i,j=1, dots, n, i neq j$ be the set of pairs. How do you count the subsets $L$ of $X$ that satisfy this property: for every $k=1,dots, n$ there are as many elements of $L$ with first coordinate $k$ as with second coordinate equal to $k$?
Here's an example. For n=3, the subset (1,2),(2,3),(3,1) satisfies this property. Same as with (1,3),(3,1), and so on. I think there are 9 such L, including the empty set for this case.
combinatorics combinations
asked Jul 14 at 22:42
Camilo
745
Let $X=(i,j); i,j=1, dots, n, i neq j$ be the set of pairs. How do you count the subsets $L$ of $X$ that satisfy this property: for every $k=1,dots, n$ there are as many elements of $L$ with first coordinate $k$ as with second coordinate equal to $k$?
Here's an example. For n=3, the subset (1,2),(2,3),(3,1) satisfies this property. Same as with (1,3),(3,1), and so on. I think there are 9 such L, including the empty set for this case.
combinatorics combinations
asked Jul 14 at 22:42
Camilo
745
asked Jul 14 at 22:42
Camilo
745
asked Jul 14 at 22:42
Camilo
745
asked Jul 14 at 22:42
Camilo
745
745
i can't offer much help, but one approach might be to label n nodes and represent the coordinates as vectors on a directed graph
– Barycentric_Bash
Jul 14 at 23:42
I count $10$ for $n=3$: $2^3=8$ possibilities with each of the three two-cycles either there or not, and two different orientations for a three-cycle.
– joriki
Jul 15 at 7:44
add a comment |Â
i can't offer much help, but one approach might be to label n nodes and represent the coordinates as vectors on a directed graph
– Barycentric_Bash
Jul 14 at 23:42
I count $10$ for $n=3$: $2^3=8$ possibilities with each of the three two-cycles either there or not, and two different orientations for a three-cycle.
– joriki
Jul 15 at 7:44
i can't offer much help, but one approach might be to label n nodes and represent the coordinates as vectors on a directed graph
– Barycentric_Bash
Jul 14 at 23:42
i can't offer much help, but one approach might be to label n nodes and represent the coordinates as vectors on a directed graph
– Barycentric_Bash
Jul 14 at 23:42
I count $10$ for $n=3$: $2^3=8$ possibilities with each of the three two-cycles either there or not, and two different orientations for a three-cycle.
– joriki
Jul 15 at 7:44
I count $10$ for $n=3$: $2^3=8$ possibilities with each of the three two-cycles either there or not, and two different orientations for a three-cycle.
– joriki
Jul 15 at 7:44
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
This is OEIS sequence A007080. If you take $1,ldots,n$ as the set of vertices of a directed graph, and the pairs as directed edges, the subsets you want correspond to directed graphs in which indegree and outdegree coincide for every vertex. Alternatively, you could describe this as the flows without sinks or sources on a complete digraph with $n$ vertices that use each edge at most once.
There are apparently two different definitions of a “Eulerian digraphâ€. One definition requires a path to exist that visits all edges exactly once. This is equivalent to the indegrees and outdegrees being equal and the edges being connected. There is also another definition, used e.g. in this article, that doesn't require connectedness and defines Eulerian digraphs directly via the equality of indegrees and outdegrees. It appears that this is the definition implied in the OEIS entry, as the count there coincides up to $n=4$ with my count by hand, and for $n=4$ there are $3$ disconnected graphs that would change the result if the other definition were being used.
The OEIS entry contains an asymptotic formula,
$$
a_nsimmathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1
;,
$$
and some links, but not much else. Generally OEIS tends to be good at collecting knowledge about such sequences, so it's likely that not much more is known and it will not be easy to find out much more.
This paper improves on the asymptotic result:
$$
a_n=mathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1left(1+frac316n+Oleft(frac1n^2right)right)
;.
$$
It also describes a method for obtaining higher-order corrections.
answered Jul 15 at 8:06
joriki
165k10180328
P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does).
– joriki
Jul 15 at 8:38
1
Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :).
– Camilo
Jul 16 at 7:10
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
This is OEIS sequence A007080. If you take $1,ldots,n$ as the set of vertices of a directed graph, and the pairs as directed edges, the subsets you want correspond to directed graphs in which indegree and outdegree coincide for every vertex. Alternatively, you could describe this as the flows without sinks or sources on a complete digraph with $n$ vertices that use each edge at most once.
There are apparently two different definitions of a “Eulerian digraphâ€. One definition requires a path to exist that visits all edges exactly once. This is equivalent to the indegrees and outdegrees being equal and the edges being connected. There is also another definition, used e.g. in this article, that doesn't require connectedness and defines Eulerian digraphs directly via the equality of indegrees and outdegrees. It appears that this is the definition implied in the OEIS entry, as the count there coincides up to $n=4$ with my count by hand, and for $n=4$ there are $3$ disconnected graphs that would change the result if the other definition were being used.
The OEIS entry contains an asymptotic formula,
$$
a_nsimmathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1
;,
$$
and some links, but not much else. Generally OEIS tends to be good at collecting knowledge about such sequences, so it's likely that not much more is known and it will not be easy to find out much more.
This paper improves on the asymptotic result:
$$
a_n=mathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1left(1+frac316n+Oleft(frac1n^2right)right)
;.
$$
It also describes a method for obtaining higher-order corrections.
answered Jul 15 at 8:06
joriki
165k10180328
P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does).
– joriki
Jul 15 at 8:38
1
Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :).
– Camilo
Jul 16 at 7:10
add a comment |Â
up vote
1
down vote
accepted
This is OEIS sequence A007080. If you take $1,ldots,n$ as the set of vertices of a directed graph, and the pairs as directed edges, the subsets you want correspond to directed graphs in which indegree and outdegree coincide for every vertex. Alternatively, you could describe this as the flows without sinks or sources on a complete digraph with $n$ vertices that use each edge at most once.
There are apparently two different definitions of a “Eulerian digraphâ€. One definition requires a path to exist that visits all edges exactly once. This is equivalent to the indegrees and outdegrees being equal and the edges being connected. There is also another definition, used e.g. in this article, that doesn't require connectedness and defines Eulerian digraphs directly via the equality of indegrees and outdegrees. It appears that this is the definition implied in the OEIS entry, as the count there coincides up to $n=4$ with my count by hand, and for $n=4$ there are $3$ disconnected graphs that would change the result if the other definition were being used.
The OEIS entry contains an asymptotic formula,
$$
a_nsimmathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1
;,
$$
and some links, but not much else. Generally OEIS tends to be good at collecting knowledge about such sequences, so it's likely that not much more is known and it will not be easy to find out much more.
This paper improves on the asymptotic result:
$$
a_n=mathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1left(1+frac316n+Oleft(frac1n^2right)right)
;.
$$
It also describes a method for obtaining higher-order corrections.
answered Jul 15 at 8:06
joriki
165k10180328
P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does).
– joriki
Jul 15 at 8:38
1
Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :).
– Camilo
Jul 16 at 7:10
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
This is OEIS sequence A007080. If you take $1,ldots,n$ as the set of vertices of a directed graph, and the pairs as directed edges, the subsets you want correspond to directed graphs in which indegree and outdegree coincide for every vertex. Alternatively, you could describe this as the flows without sinks or sources on a complete digraph with $n$ vertices that use each edge at most once.
There are apparently two different definitions of a “Eulerian digraphâ€. One definition requires a path to exist that visits all edges exactly once. This is equivalent to the indegrees and outdegrees being equal and the edges being connected. There is also another definition, used e.g. in this article, that doesn't require connectedness and defines Eulerian digraphs directly via the equality of indegrees and outdegrees. It appears that this is the definition implied in the OEIS entry, as the count there coincides up to $n=4$ with my count by hand, and for $n=4$ there are $3$ disconnected graphs that would change the result if the other definition were being used.
The OEIS entry contains an asymptotic formula,
$$
a_nsimmathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1
;,
$$
and some links, but not much else. Generally OEIS tends to be good at collecting knowledge about such sequences, so it's likely that not much more is known and it will not be easy to find out much more.
This paper improves on the asymptotic result:
$$
a_n=mathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1left(1+frac316n+Oleft(frac1n^2right)right)
;.
$$
It also describes a method for obtaining higher-order corrections.
answered Jul 15 at 8:06
joriki
165k10180328
This is OEIS sequence A007080. If you take $1,ldots,n$ as the set of vertices of a directed graph, and the pairs as directed edges, the subsets you want correspond to directed graphs in which indegree and outdegree coincide for every vertex. Alternatively, you could describe this as the flows without sinks or sources on a complete digraph with $n$ vertices that use each edge at most once.
There are apparently two different definitions of a “Eulerian digraphâ€. One definition requires a path to exist that visits all edges exactly once. This is equivalent to the indegrees and outdegrees being equal and the edges being connected. There is also another definition, used e.g. in this article, that doesn't require connectedness and defines Eulerian digraphs directly via the equality of indegrees and outdegrees. It appears that this is the definition implied in the OEIS entry, as the count there coincides up to $n=4$ with my count by hand, and for $n=4$ there are $3$ disconnected graphs that would change the result if the other definition were being used.
The OEIS entry contains an asymptotic formula,
$$
a_nsimmathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1
;,
$$
and some links, but not much else. Generally OEIS tends to be good at collecting knowledge about such sequences, so it's likely that not much more is known and it will not be easy to find out much more.
This paper improves on the asymptotic result:
$$
a_n=mathrm e^-frac14sqrt nleft(frac2^nsqrtpi nright)^n-1left(1+frac316n+Oleft(frac1n^2right)right)
;.
$$
It also describes a method for obtaining higher-order corrections.
answered Jul 15 at 8:06
joriki
165k10180328
edited Jul 15 at 8:15
answered Jul 15 at 8:06
joriki
165k10180328
answered Jul 15 at 8:06
joriki
165k10180328
answered Jul 15 at 8:06
joriki
165k10180328
165k10180328
P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does).
– joriki
Jul 15 at 8:38
1
Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :).
– Camilo
Jul 16 at 7:10
add a comment |Â
P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does).
– joriki
Jul 15 at 8:38
1
Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :).
– Camilo
Jul 16 at 7:10
P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does).
– joriki
Jul 15 at 8:38
P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does).
– joriki
Jul 15 at 8:38
1
1
Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :).
– Camilo
Jul 16 at 7:10
Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :).
– Camilo
Jul 16 at 7:10
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852019%2flet-x-set-of-all-pairs-i-j-with-i-neq-j-counting-subsets-l-of-x-that-hav%23new-answer', 'question_page');
);
Post as a guest
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
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
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
i can't offer much help, but one approach might be to label n nodes and represent the coordinates as vectors on a directed graph
– Barycentric_Bash
Jul 14 at 23:42
I count $10$ for $n=3$: $2^3=8$ possibilities with each of the three two-cycles either there or not, and two different orientations for a three-cycle.
– joriki
Jul 15 at 7:44