Mixing
Number of Symmetric Chains of Length $n +1 - 2i$ in $mathcal P(1,2, dots , n)$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am having trouble understanding the function to count the number of symmetric chains in $mathcal P(1,2, dots, n)$ that I have in my notes.
In my notes, we have defined a symmetric chain ( in $mathcal P(1,2, dots, n)$
) to be a chain of sets $mathcal C = C_i, C_i+1, dots, C_n-i$ such that $|C_j| = j$.
Given this, my notes go on to say that for $0 leq i leq fracn2$, the number of symmetric chains with $n + 1 - 2i $ sets is $l(n,i) = binom ni - binomni-1$.
However, I am having a lot of trouble understanding why this is true, and in particular what these binomial coefficients are representing. Further, I suspect that this might be wrong as I have tested some small cases, and assuming that I'm understanding what it means for a chain to be a symmetric chain, then it doesn't seem to work in the cases $n=4, ; i = 1,2$.
Any clarification or correction with regards to this formula would be very much appreciated, thank you!
combinatorics
asked Jul 30 at 13:39
user366818
704310
 |Â
show 3 more comments
up vote
1
down vote
favorite
I am having trouble understanding the function to count the number of symmetric chains in $mathcal P(1,2, dots, n)$ that I have in my notes.
In my notes, we have defined a symmetric chain ( in $mathcal P(1,2, dots, n)$
) to be a chain of sets $mathcal C = C_i, C_i+1, dots, C_n-i$ such that $|C_j| = j$.
Given this, my notes go on to say that for $0 leq i leq fracn2$, the number of symmetric chains with $n + 1 - 2i $ sets is $l(n,i) = binom ni - binomni-1$.
However, I am having a lot of trouble understanding why this is true, and in particular what these binomial coefficients are representing. Further, I suspect that this might be wrong as I have tested some small cases, and assuming that I'm understanding what it means for a chain to be a symmetric chain, then it doesn't seem to work in the cases $n=4, ; i = 1,2$.
Any clarification or correction with regards to this formula would be very much appreciated, thank you!
combinatorics
asked Jul 30 at 13:39
user366818
704310
1
I think that your notes are saying that in a symmetric chain decomposition of $mathcalP(n)$ there are $l(n,i)$ chains of this size.
– Jamie Radcliffe
Jul 30 at 13:41
You probably also need $C_j subset C_j+1$. Otherwise the choices of the subsets is independent and you just multiply the number of subsets of each size in your chain.
– Ross Millikan
Jul 30 at 14:05
If $n=3$ and $i=1$, we should get the number of symmetric chains of length $3+1-2=2$ to be $l(3,1)=binom31-binom30=2$, right? I found the following chains: $big1,1,2big$, $big1,1,3big$, $big2,2,3big$. Did I misunderstand something?
– Batominovski
Jul 30 at 14:08
@Batominovski But what about $2,12$?
– user366818
Jul 30 at 14:09
The point is I have found more than $2$ symmetric chains, when you say that there should be $2$.
– Batominovski
Jul 30 at 14:10
 |Â
show 3 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am having trouble understanding the function to count the number of symmetric chains in $mathcal P(1,2, dots, n)$ that I have in my notes.
In my notes, we have defined a symmetric chain ( in $mathcal P(1,2, dots, n)$
) to be a chain of sets $mathcal C = C_i, C_i+1, dots, C_n-i$ such that $|C_j| = j$.
Given this, my notes go on to say that for $0 leq i leq fracn2$, the number of symmetric chains with $n + 1 - 2i $ sets is $l(n,i) = binom ni - binomni-1$.
However, I am having a lot of trouble understanding why this is true, and in particular what these binomial coefficients are representing. Further, I suspect that this might be wrong as I have tested some small cases, and assuming that I'm understanding what it means for a chain to be a symmetric chain, then it doesn't seem to work in the cases $n=4, ; i = 1,2$.
Any clarification or correction with regards to this formula would be very much appreciated, thank you!
combinatorics
asked Jul 30 at 13:39
user366818
704310
I am having trouble understanding the function to count the number of symmetric chains in $mathcal P(1,2, dots, n)$ that I have in my notes.
In my notes, we have defined a symmetric chain ( in $mathcal P(1,2, dots, n)$
) to be a chain of sets $mathcal C = C_i, C_i+1, dots, C_n-i$ such that $|C_j| = j$.
Given this, my notes go on to say that for $0 leq i leq fracn2$, the number of symmetric chains with $n + 1 - 2i $ sets is $l(n,i) = binom ni - binomni-1$.
However, I am having a lot of trouble understanding why this is true, and in particular what these binomial coefficients are representing. Further, I suspect that this might be wrong as I have tested some small cases, and assuming that I'm understanding what it means for a chain to be a symmetric chain, then it doesn't seem to work in the cases $n=4, ; i = 1,2$.
Any clarification or correction with regards to this formula would be very much appreciated, thank you!
combinatorics
asked Jul 30 at 13:39
user366818
704310
asked Jul 30 at 13:39
user366818
704310
asked Jul 30 at 13:39
user366818
704310
asked Jul 30 at 13:39
user366818
704310
704310
1
I think that your notes are saying that in a symmetric chain decomposition of $mathcalP(n)$ there are $l(n,i)$ chains of this size.
– Jamie Radcliffe
Jul 30 at 13:41
You probably also need $C_j subset C_j+1$. Otherwise the choices of the subsets is independent and you just multiply the number of subsets of each size in your chain.
– Ross Millikan
Jul 30 at 14:05
If $n=3$ and $i=1$, we should get the number of symmetric chains of length $3+1-2=2$ to be $l(3,1)=binom31-binom30=2$, right? I found the following chains: $big1,1,2big$, $big1,1,3big$, $big2,2,3big$. Did I misunderstand something?
– Batominovski
Jul 30 at 14:08
@Batominovski But what about $2,12$?
– user366818
Jul 30 at 14:09
The point is I have found more than $2$ symmetric chains, when you say that there should be $2$.
– Batominovski
Jul 30 at 14:10
 |Â
show 3 more comments
1
I think that your notes are saying that in a symmetric chain decomposition of $mathcalP(n)$ there are $l(n,i)$ chains of this size.
– Jamie Radcliffe
Jul 30 at 13:41
You probably also need $C_j subset C_j+1$. Otherwise the choices of the subsets is independent and you just multiply the number of subsets of each size in your chain.
– Ross Millikan
Jul 30 at 14:05
If $n=3$ and $i=1$, we should get the number of symmetric chains of length $3+1-2=2$ to be $l(3,1)=binom31-binom30=2$, right? I found the following chains: $big1,1,2big$, $big1,1,3big$, $big2,2,3big$. Did I misunderstand something?
– Batominovski
Jul 30 at 14:08
@Batominovski But what about $2,12$?
– user366818
Jul 30 at 14:09
The point is I have found more than $2$ symmetric chains, when you say that there should be $2$.
– Batominovski
Jul 30 at 14:10
1
1
I think that your notes are saying that in a symmetric chain decomposition of $mathcalP(n)$ there are $l(n,i)$ chains of this size.
– Jamie Radcliffe
Jul 30 at 13:41
I think that your notes are saying that in a symmetric chain decomposition of $mathcalP(n)$ there are $l(n,i)$ chains of this size.
– Jamie Radcliffe
Jul 30 at 13:41
You probably also need $C_j subset C_j+1$. Otherwise the choices of the subsets is independent and you just multiply the number of subsets of each size in your chain.
– Ross Millikan
Jul 30 at 14:05
You probably also need $C_j subset C_j+1$. Otherwise the choices of the subsets is independent and you just multiply the number of subsets of each size in your chain.
– Ross Millikan
Jul 30 at 14:05
If $n=3$ and $i=1$, we should get the number of symmetric chains of length $3+1-2=2$ to be $l(3,1)=binom31-binom30=2$, right? I found the following chains: $big1,1,2big$, $big1,1,3big$, $big2,2,3big$. Did I misunderstand something?
– Batominovski
Jul 30 at 14:08
If $n=3$ and $i=1$, we should get the number of symmetric chains of length $3+1-2=2$ to be $l(3,1)=binom31-binom30=2$, right? I found the following chains: $big1,1,2big$, $big1,1,3big$, $big2,2,3big$. Did I misunderstand something?
– Batominovski
Jul 30 at 14:08
@Batominovski But what about $2,12$?
– user366818
Jul 30 at 14:09
@Batominovski But what about $2,12$?
– user366818
Jul 30 at 14:09
The point is I have found more than $2$ symmetric chains, when you say that there should be $2$.
– Batominovski
Jul 30 at 14:10
The point is I have found more than $2$ symmetric chains, when you say that there should be $2$.
– Batominovski
Jul 30 at 14:10
 |Â
show 3 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
I agree with Jamie Radcliffe. Let $[n]:=1,2,ldots,n$ and $mathcalP_n$ denote the power set $mathcalPbig([n]big)$. Suppose that $mathcalP_n$ has a decomposition into pairwise disjoint symmetric chains
$$mathcalP_n=bigcup_k=0^leftlfloor fracn2rightrfloor,bigcup_r=1^t_k,mathcalC_k^r,,$$
where $mathcalC_k^1,mathcalC_k^2,ldots,mathcalC_k^t_k$ are symmetric chains of length $n+1-2k$ for each $k=0,1,2,ldots,leftlfloorfracn2rightrfloor$. For example, when $n=4$, we have
$$beginalignmathcalP_4&=bigemptyset,1,1,2,1,2,3,1,2,3,4big
\
&phantomaaaaacupbig2,2,3,2,3,4bigcupbig3,3,4,3,4,1bigcupbig4,4,1,4,1,2big
\
&phantomaaaaacupbig1,3bigcupbig2,4big,.endalign$$
We shall prove that
$$t_k=l(n,k)=binomnk-binomnk-1text for every k=0,1,2,ldots,leftlfloorfracn2rightrfloor$$
by induction on $k$. We start with $t_0=1=l(n,0)$. This is trivial because $emptysetinmathcalP_n$ has to be in exactly one symmetric chain.
Now, suppose that $kinBiggl1,2,ldots,leftlfloorfracn2rightrfloorBiggr$ and that $t_j=l(n,j)$ for all $j=0,1,2,ldots,k-1$. The number of $k$-subsets of $[n]$ that already lie in some $mathcalC_j^s$ with $j<k$ is
$$sum_j=0^k-1,t_j=sum_j=0^k-1,l(n,j)=sum_j=0^k-1,Biggl(binomnj-binomnj-1Biggr)=binomnk-1,.$$
Hence, there are exactly $displaystylebinomnk-binomnk-1=l(n,k)$ subsets of $[n]$ of size $k$ left. Each of these subsets must belong in exactly one symmetric chain of length $n+1-2k$. Therefore,
$$t_k=l(n,k),,$$
as desired.
answered Jul 30 at 14:27
Batominovski
22.8k22777
OP asked about the number of symmetric chains, not about decompositions of the power set into disjoint symmetric chains.
– Ross Millikan
Jul 30 at 14:46
@RossMillikan I know that. Read the comments under the question. We believe that the OP misunderstood something.
– Batominovski
Jul 30 at 14:47
add a comment |Â
up vote
2
down vote
The number of symmetric chains is much higher. You have $n choose i$ ways to choose $C_i$. Then you choose the $n-2i$ elements that will get added, but you choose them in order, so the total number of chains is $$n choose in-i choose n-2i(n-2i)!$$
For example, if $n=6, i=2$ we have $6 choose 2=15$ ways to choose $C_2$, then $4$ ways to choose the element to add to make $C_3$, and $3$ ways to choose the element to add to make $C_4$, for a total of $15 cdot 4 cdot 3=180$. The above formula gives $15 cdot 6 cdot 2=180$
answered Jul 30 at 14:42
Ross Millikan
275k21184351
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
I agree with Jamie Radcliffe. Let $[n]:=1,2,ldots,n$ and $mathcalP_n$ denote the power set $mathcalPbig([n]big)$. Suppose that $mathcalP_n$ has a decomposition into pairwise disjoint symmetric chains
$$mathcalP_n=bigcup_k=0^leftlfloor fracn2rightrfloor,bigcup_r=1^t_k,mathcalC_k^r,,$$
where $mathcalC_k^1,mathcalC_k^2,ldots,mathcalC_k^t_k$ are symmetric chains of length $n+1-2k$ for each $k=0,1,2,ldots,leftlfloorfracn2rightrfloor$. For example, when $n=4$, we have
$$beginalignmathcalP_4&=bigemptyset,1,1,2,1,2,3,1,2,3,4big
\
&phantomaaaaacupbig2,2,3,2,3,4bigcupbig3,3,4,3,4,1bigcupbig4,4,1,4,1,2big
\
&phantomaaaaacupbig1,3bigcupbig2,4big,.endalign$$
We shall prove that
$$t_k=l(n,k)=binomnk-binomnk-1text for every k=0,1,2,ldots,leftlfloorfracn2rightrfloor$$
by induction on $k$. We start with $t_0=1=l(n,0)$. This is trivial because $emptysetinmathcalP_n$ has to be in exactly one symmetric chain.
Now, suppose that $kinBiggl1,2,ldots,leftlfloorfracn2rightrfloorBiggr$ and that $t_j=l(n,j)$ for all $j=0,1,2,ldots,k-1$. The number of $k$-subsets of $[n]$ that already lie in some $mathcalC_j^s$ with $j<k$ is
$$sum_j=0^k-1,t_j=sum_j=0^k-1,l(n,j)=sum_j=0^k-1,Biggl(binomnj-binomnj-1Biggr)=binomnk-1,.$$
Hence, there are exactly $displaystylebinomnk-binomnk-1=l(n,k)$ subsets of $[n]$ of size $k$ left. Each of these subsets must belong in exactly one symmetric chain of length $n+1-2k$. Therefore,
$$t_k=l(n,k),,$$
as desired.
answered Jul 30 at 14:27
Batominovski
22.8k22777
OP asked about the number of symmetric chains, not about decompositions of the power set into disjoint symmetric chains.
– Ross Millikan
Jul 30 at 14:46
@RossMillikan I know that. Read the comments under the question. We believe that the OP misunderstood something.
– Batominovski
Jul 30 at 14:47
add a comment |Â
up vote
1
down vote
accepted
I agree with Jamie Radcliffe. Let $[n]:=1,2,ldots,n$ and $mathcalP_n$ denote the power set $mathcalPbig([n]big)$. Suppose that $mathcalP_n$ has a decomposition into pairwise disjoint symmetric chains
$$mathcalP_n=bigcup_k=0^leftlfloor fracn2rightrfloor,bigcup_r=1^t_k,mathcalC_k^r,,$$
where $mathcalC_k^1,mathcalC_k^2,ldots,mathcalC_k^t_k$ are symmetric chains of length $n+1-2k$ for each $k=0,1,2,ldots,leftlfloorfracn2rightrfloor$. For example, when $n=4$, we have
$$beginalignmathcalP_4&=bigemptyset,1,1,2,1,2,3,1,2,3,4big
\
&phantomaaaaacupbig2,2,3,2,3,4bigcupbig3,3,4,3,4,1bigcupbig4,4,1,4,1,2big
\
&phantomaaaaacupbig1,3bigcupbig2,4big,.endalign$$
We shall prove that
$$t_k=l(n,k)=binomnk-binomnk-1text for every k=0,1,2,ldots,leftlfloorfracn2rightrfloor$$
by induction on $k$. We start with $t_0=1=l(n,0)$. This is trivial because $emptysetinmathcalP_n$ has to be in exactly one symmetric chain.
Now, suppose that $kinBiggl1,2,ldots,leftlfloorfracn2rightrfloorBiggr$ and that $t_j=l(n,j)$ for all $j=0,1,2,ldots,k-1$. The number of $k$-subsets of $[n]$ that already lie in some $mathcalC_j^s$ with $j<k$ is
$$sum_j=0^k-1,t_j=sum_j=0^k-1,l(n,j)=sum_j=0^k-1,Biggl(binomnj-binomnj-1Biggr)=binomnk-1,.$$
Hence, there are exactly $displaystylebinomnk-binomnk-1=l(n,k)$ subsets of $[n]$ of size $k$ left. Each of these subsets must belong in exactly one symmetric chain of length $n+1-2k$. Therefore,
$$t_k=l(n,k),,$$
as desired.
answered Jul 30 at 14:27
Batominovski
22.8k22777
OP asked about the number of symmetric chains, not about decompositions of the power set into disjoint symmetric chains.
– Ross Millikan
Jul 30 at 14:46
@RossMillikan I know that. Read the comments under the question. We believe that the OP misunderstood something.
– Batominovski
Jul 30 at 14:47
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
I agree with Jamie Radcliffe. Let $[n]:=1,2,ldots,n$ and $mathcalP_n$ denote the power set $mathcalPbig([n]big)$. Suppose that $mathcalP_n$ has a decomposition into pairwise disjoint symmetric chains
$$mathcalP_n=bigcup_k=0^leftlfloor fracn2rightrfloor,bigcup_r=1^t_k,mathcalC_k^r,,$$
where $mathcalC_k^1,mathcalC_k^2,ldots,mathcalC_k^t_k$ are symmetric chains of length $n+1-2k$ for each $k=0,1,2,ldots,leftlfloorfracn2rightrfloor$. For example, when $n=4$, we have
$$beginalignmathcalP_4&=bigemptyset,1,1,2,1,2,3,1,2,3,4big
\
&phantomaaaaacupbig2,2,3,2,3,4bigcupbig3,3,4,3,4,1bigcupbig4,4,1,4,1,2big
\
&phantomaaaaacupbig1,3bigcupbig2,4big,.endalign$$
We shall prove that
$$t_k=l(n,k)=binomnk-binomnk-1text for every k=0,1,2,ldots,leftlfloorfracn2rightrfloor$$
by induction on $k$. We start with $t_0=1=l(n,0)$. This is trivial because $emptysetinmathcalP_n$ has to be in exactly one symmetric chain.
Now, suppose that $kinBiggl1,2,ldots,leftlfloorfracn2rightrfloorBiggr$ and that $t_j=l(n,j)$ for all $j=0,1,2,ldots,k-1$. The number of $k$-subsets of $[n]$ that already lie in some $mathcalC_j^s$ with $j<k$ is
$$sum_j=0^k-1,t_j=sum_j=0^k-1,l(n,j)=sum_j=0^k-1,Biggl(binomnj-binomnj-1Biggr)=binomnk-1,.$$
Hence, there are exactly $displaystylebinomnk-binomnk-1=l(n,k)$ subsets of $[n]$ of size $k$ left. Each of these subsets must belong in exactly one symmetric chain of length $n+1-2k$. Therefore,
$$t_k=l(n,k),,$$
as desired.
answered Jul 30 at 14:27
Batominovski
22.8k22777
I agree with Jamie Radcliffe. Let $[n]:=1,2,ldots,n$ and $mathcalP_n$ denote the power set $mathcalPbig([n]big)$. Suppose that $mathcalP_n$ has a decomposition into pairwise disjoint symmetric chains
$$mathcalP_n=bigcup_k=0^leftlfloor fracn2rightrfloor,bigcup_r=1^t_k,mathcalC_k^r,,$$
where $mathcalC_k^1,mathcalC_k^2,ldots,mathcalC_k^t_k$ are symmetric chains of length $n+1-2k$ for each $k=0,1,2,ldots,leftlfloorfracn2rightrfloor$. For example, when $n=4$, we have
$$beginalignmathcalP_4&=bigemptyset,1,1,2,1,2,3,1,2,3,4big
\
&phantomaaaaacupbig2,2,3,2,3,4bigcupbig3,3,4,3,4,1bigcupbig4,4,1,4,1,2big
\
&phantomaaaaacupbig1,3bigcupbig2,4big,.endalign$$
We shall prove that
$$t_k=l(n,k)=binomnk-binomnk-1text for every k=0,1,2,ldots,leftlfloorfracn2rightrfloor$$
by induction on $k$. We start with $t_0=1=l(n,0)$. This is trivial because $emptysetinmathcalP_n$ has to be in exactly one symmetric chain.
Now, suppose that $kinBiggl1,2,ldots,leftlfloorfracn2rightrfloorBiggr$ and that $t_j=l(n,j)$ for all $j=0,1,2,ldots,k-1$. The number of $k$-subsets of $[n]$ that already lie in some $mathcalC_j^s$ with $j<k$ is
$$sum_j=0^k-1,t_j=sum_j=0^k-1,l(n,j)=sum_j=0^k-1,Biggl(binomnj-binomnj-1Biggr)=binomnk-1,.$$
Hence, there are exactly $displaystylebinomnk-binomnk-1=l(n,k)$ subsets of $[n]$ of size $k$ left. Each of these subsets must belong in exactly one symmetric chain of length $n+1-2k$. Therefore,
$$t_k=l(n,k),,$$
as desired.
answered Jul 30 at 14:27
Batominovski
22.8k22777
edited Jul 30 at 14:44
answered Jul 30 at 14:27
Batominovski
22.8k22777
answered Jul 30 at 14:27
Batominovski
22.8k22777
answered Jul 30 at 14:27
Batominovski
22.8k22777
22.8k22777
OP asked about the number of symmetric chains, not about decompositions of the power set into disjoint symmetric chains.
– Ross Millikan
Jul 30 at 14:46
@RossMillikan I know that. Read the comments under the question. We believe that the OP misunderstood something.
– Batominovski
Jul 30 at 14:47
add a comment |Â
OP asked about the number of symmetric chains, not about decompositions of the power set into disjoint symmetric chains.
– Ross Millikan
Jul 30 at 14:46
@RossMillikan I know that. Read the comments under the question. We believe that the OP misunderstood something.
– Batominovski
Jul 30 at 14:47
OP asked about the number of symmetric chains, not about decompositions of the power set into disjoint symmetric chains.
– Ross Millikan
Jul 30 at 14:46
OP asked about the number of symmetric chains, not about decompositions of the power set into disjoint symmetric chains.
– Ross Millikan
Jul 30 at 14:46
@RossMillikan I know that. Read the comments under the question. We believe that the OP misunderstood something.
– Batominovski
Jul 30 at 14:47
@RossMillikan I know that. Read the comments under the question. We believe that the OP misunderstood something.
– Batominovski
Jul 30 at 14:47
add a comment |Â
up vote
2
down vote
The number of symmetric chains is much higher. You have $n choose i$ ways to choose $C_i$. Then you choose the $n-2i$ elements that will get added, but you choose them in order, so the total number of chains is $$n choose in-i choose n-2i(n-2i)!$$
For example, if $n=6, i=2$ we have $6 choose 2=15$ ways to choose $C_2$, then $4$ ways to choose the element to add to make $C_3$, and $3$ ways to choose the element to add to make $C_4$, for a total of $15 cdot 4 cdot 3=180$. The above formula gives $15 cdot 6 cdot 2=180$
answered Jul 30 at 14:42
Ross Millikan
275k21184351
add a comment |Â
up vote
2
down vote
The number of symmetric chains is much higher. You have $n choose i$ ways to choose $C_i$. Then you choose the $n-2i$ elements that will get added, but you choose them in order, so the total number of chains is $$n choose in-i choose n-2i(n-2i)!$$
For example, if $n=6, i=2$ we have $6 choose 2=15$ ways to choose $C_2$, then $4$ ways to choose the element to add to make $C_3$, and $3$ ways to choose the element to add to make $C_4$, for a total of $15 cdot 4 cdot 3=180$. The above formula gives $15 cdot 6 cdot 2=180$
answered Jul 30 at 14:42
Ross Millikan
275k21184351
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The number of symmetric chains is much higher. You have $n choose i$ ways to choose $C_i$. Then you choose the $n-2i$ elements that will get added, but you choose them in order, so the total number of chains is $$n choose in-i choose n-2i(n-2i)!$$
For example, if $n=6, i=2$ we have $6 choose 2=15$ ways to choose $C_2$, then $4$ ways to choose the element to add to make $C_3$, and $3$ ways to choose the element to add to make $C_4$, for a total of $15 cdot 4 cdot 3=180$. The above formula gives $15 cdot 6 cdot 2=180$
answered Jul 30 at 14:42
Ross Millikan
275k21184351
The number of symmetric chains is much higher. You have $n choose i$ ways to choose $C_i$. Then you choose the $n-2i$ elements that will get added, but you choose them in order, so the total number of chains is $$n choose in-i choose n-2i(n-2i)!$$
For example, if $n=6, i=2$ we have $6 choose 2=15$ ways to choose $C_2$, then $4$ ways to choose the element to add to make $C_3$, and $3$ ways to choose the element to add to make $C_4$, for a total of $15 cdot 4 cdot 3=180$. The above formula gives $15 cdot 6 cdot 2=180$
answered Jul 30 at 14:42
Ross Millikan
275k21184351
answered Jul 30 at 14:42
Ross Millikan
275k21184351
answered Jul 30 at 14:42
Ross Millikan
275k21184351
answered Jul 30 at 14:42
Ross Millikan
275k21184351
275k21184351
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867026%2fnumber-of-symmetric-chains-of-length-n-1-2i-in-mathcal-p-1-2-dots-n%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
1
I think that your notes are saying that in a symmetric chain decomposition of $mathcalP(n)$ there are $l(n,i)$ chains of this size.
– Jamie Radcliffe
Jul 30 at 13:41
You probably also need $C_j subset C_j+1$. Otherwise the choices of the subsets is independent and you just multiply the number of subsets of each size in your chain.
– Ross Millikan
Jul 30 at 14:05
If $n=3$ and $i=1$, we should get the number of symmetric chains of length $3+1-2=2$ to be $l(3,1)=binom31-binom30=2$, right? I found the following chains: $big1,1,2big$, $big1,1,3big$, $big2,2,3big$. Did I misunderstand something?
– Batominovski
Jul 30 at 14:08
@Batominovski But what about $2,12$?
– user366818
Jul 30 at 14:09
The point is I have found more than $2$ symmetric chains, when you say that there should be $2$.
– Batominovski
Jul 30 at 14:10