Conversation started Jun 12, 2020 at 7:49.
Jun 12, 2020 07:49
I understand that number of ways of choosing some x (x>n) from n items is zero. But isn't this case automatically eliminated as we already fix the domain of r to be within 0 and n? So is this meant for non-integral values of r?
> Number of circular permutations of n things when p are alike and the rest are different, taken all at a time, distinguishing clockwise and anticlockwise arrangement is (n-1)!/p!
This formula looks similar to the linear permutation. However, is this really applicable for the circular permutation case? Further, is it possible to expand this simple formula to circular permutations where there exists more than one kind of repetitions (like 3 red balls and 4 blue balls)?
For the second question, from this answer on the main site, I came to know that one must 'master' the use of Burnside's lemma. Is there any alternate route for circular permutations with more than one kind of repetitions?
5 hours later…
Jun 12, 2020 13:03
@GuruVishnu Your question is a very good one, and actually I do not agree with your book's definition.
But first, let me clear up a misconception on your part. Whenever we define a function f, we have to specify its domain and a rule that fixes what is the output of f on each input from the domain. If you define a function C to have domain { (n,r) : n∈N ∧ r∈{0..n} }, then you cannot even talk about C(n,r) if r∉{0..n}; it is simply meaningless or forbidden.
So clearly your book wants to allow the domain of C to include pairs (n,r) such that r∉{0..n}. There is nothing wrong with choosing to do that.
This generalizes Pascal's triangle and the combinatorial definition in your book. It would be good for you to actually construct the table of values to see how it reproduces Pascal's triangle. You can check yours against mine:
··· 1 1 1 1 1 1 1 1 ··· ··· −3 −2 −1 0 1 2 3 4 ··· ··· 6 3 1 0 0 1 3 6 ··· ··· −10 −4 −1 0 0 0 1 4 ··· ··· 15 5 1 0 0 0 0 1 ···
It is unclear whether your book says anything about C(n,k) for n < 0, but since you didn't mention it I assume it doesn't. It would be bad to define it to be zero. Numerous theorems that involve binomial coefficients work only if it is compatible with my definition above, which means it must be nonzero for n < 0.
What you have discovered/invented is known as the forward difference operator $D$ defined as:
$
\def\nn{\mathbb{N}}
\def\zz{\mathbb{Z}}
\def\lfrac#1#2{{\large\frac{#1}{#2}}}
\def\lbinom#1#2{{\large\binom{#1}{#2}}}
$
$D = ( \text{function $f$ on $\zz$} \mapsto ( \text{int $n$} \mapsto f(n+1) -...Jun 12, 2020 13:42
So from now on I'll use the definition of C that I gave. You can prove by induction that C(n,k) = 1/k! · Product { n−i : k∈{0..k−1} }. This should immediately suggest extending C(n,k) further to be defined for any real n (but still k∈N) as a polynomial function with degree k. In fact, that is a very fruitful idea. The binomial theorem (1+x)^r where r is real (not just integer) requires this extension!
@GuruVishnu To correctly reason about combinatorics questions, you must fully understand their rigorous formulation. To prove that there are as many objects in a set S as in a set T, we must prove that there exists a bijection from S to T. If you cannot do this, then it means (unfortunately) that you do not (yet) understand why S and T have the same size.
For the example of circular permutations, don't even go to your question yet. First make sure you can show that there are (n−1)! ways to arrange n distinct beads on a circle (equally spaced), where we consider two ways the same iff one can be obtained from the other by rotating it around the circle.
16 hours later…
Jun 13, 2020 06:19
17 hours ago, by user21820
This generalizes Pascal's triangle and the combinatorial definition in your book. It would be good for you to actually construct the table of values to see how it reproduces Pascal's triangle. You can check yours against mine:
I understand that the different numbers in the Pascal's triangle show the values of C(n,r) where n and r depend upon the row and distance from the leftmost side of the triangle.
Is the Pascal's triangle's base on the right? I think that is the case as it follows the general trend: The number in the next row is the sum of numbers in the current row. I think, here, the trend is switched to columns. Or are we supposed to follow this format as opposed to the usual triangle?
"It is unclear whether your book says anything about C(n,k) for n < 0, but since you didn't mention it I assume it doesn't." - Even I'm not sure about the intention of the authors. It plainly gave this without any explanation: C(n,r)=0 if r ∉ {0,1,2,3,...,n}
I've learnt all the three parts of your definition earlier, but I never knew that we can use any integral value for n and r in C(n,r).
17 hours ago, by user21820
@GuruVishnu To correctly reason about combinatorics questions, you must fully understand their rigorous formulation. To prove that there are as many objects in a set S as in a set T, we must prove that there exists a bijection from S to T. If you cannot do this, then it means (unfortunately) that you do not (yet) understand why S and T have the same size.
I understand why a bijection (one-one and onto) between two sets implies the two sets have the same number of elements. However, I haven't encountered cases in combinatorics questions where I need to prove a bijection exists from one set to the other. Or in other words, I'm unable to see how it's related to this question. If possible, could you give an explanation or suggest a resource where I could learn about this?
17 hours ago, by user21820
For the example of circular permutations, don't even go to your question yet. First make sure you can show that there are (n−1)! ways to arrange n distinct beads on a circle (equally spaced), where we consider two ways the same iff one can be obtained from the other by rotating it around the circle.
As my book just gave the formulas (n-1)! and (n-1)!/2 for the circular permutation without any explanation, I learnt about it from this answer on the main site.
That was how I understood why it's (n-1)! permutations when clockwise and anticlockwise arrangements are counted separately and (n-1)!/2 when both directions are considered as the same thing. I didn't know to prove that before reading that answer as I didn't even fully understand what circular permutations were.
But now, the way I'd arrive at (n-1)! and (n-1)!/2 is similar to the method described in that answer. That method was satisfying for me and so I proceeded. But I don't know whether it's rigorous enough.
I can see that you've given me some hints to arrive at the formula rigorously in this message, but I'd like to try it after clearing the doubts I mentioned in this message.
Jun 13, 2020 07:41
@GuruVishnu It's quite common for high-school level textbooks to be unclear about what they mean. But I personally think it is far better to be precise. Regarding Pascal's triangle, it doesn't matter whether you think of it upright (the usual) or sideways (in the way I presented it). What is important is simply that you realize the best way to extend it to negative n.
@GuruVishnu Sadly, that's the problem with high-school level textbooks. I haven't seen any deal properly with combinatorics. Let me explain the circular permutation one and you will know what I mean.
Let W be the set of ways of arranging n distinct beads on a circle (equally spaced), where we consider two ways the same iff one can be obtained from the other by rotating it around the circle.
Let P be the set of permutations of {1..n−1}, meaning the set of lists that each has each k∈{1..n−1} in exactly one position.
First number the n beads 1 to n. For each arrangement A, define f(A) to be the list obtained by reading clockwise from just after bead n until just before bead n. Then f(A) is a permutation of {1..n}. (Note that this f is well-defined because we consider arrangements to be the same under rotation.)
Now we need to prove that f is injective and surjects onto P. For any arrangements A,B such that f(A) = f(B), reading the beads clockwise from just after bead n gives the same for both A and B, so clearly A and B are the same (up to rotation). Thus f is injective. I'll let you check for yourself that f surjects onto P, since it is trivial.
Jun 13, 2020 08:07
To make it a bit simpler, we can use {0..n−1} instead of {1..n}. Each permutation of {0..n−1} can be defined as a bijection from {0..n−1} to itself. Circular permutations can be defined as equivalence classes of permutations of {0..n−1} modulo the following equivalence relation: Given permutations A,B of {0..n−1}, define A ~ B iff ∃c∈Z ∀k∈{0..n−1} ( A(k) = B((k+c)%n) ). Here x%n is defined as the unique r∈{0..n−1} such that n | x−r. Now check that ~ is an equivalence relation.
Jun 13, 2020 08:26
You can define the bijection equally precisely using the equivalence relation. For each X∈P(n)/~, define f(X)∈X such that f(X)(n−1) = n−1, which exists because X = { A : A~B } for some B∈P(n), and B(c) = n−1 for some c∈{0..n−1}, so we can define f(X) to be ( {0..n−1} k ↦ B((k+c−n+1)%n) ), so that f(X)~B and f(X)(n−1) = B(c), giving f(X)∈X and f(X)(n−1) = n−1 as desired. Finally, define g(X) to be f(X) restricted to {0..n−2}.
If you are a mathematics major, it would be instructive to prove as an exercise that this f bijects from P(n)/~ to P(n−1), to fully formalize the intuitive reasoning. I don't mean to say that you must do this for each combinatorics question, but you must learn how to do it if you wish to truly grasp the underlying mathematics.
Jun 13, 2020 10:31
@Doubtnut If you hover your mouse over a message, a right-arrow button appears. That is the reply button. Click on it then type your message, and it will automatically make a ping (with an orange box) plus a link to the replied message. When you ping me, I also see an orange box, but if you don't click the reply button then it will not link to the earlier message.
I thought negative values of n had no meaning. At least you tried it before someone asked you to do so :-)
Thank you for your explanation of circular permutations. I think I've to read it some more times to understand it completely. By the way, I've learnt some basics about equivalence classes in the chapter relations. I just know a relation is an equivalence class if it's transitive, reflexive and symmetric and nothing more than that. This seems to be a bit different for me.
But I suspect your book did not even bother to teach equivalence classes. The definition of equivalence classes is exactly the one I used:
> Given any set S and equivalence relation ~ on S, the set of equivalence classes is S/~ := { { A : A~B } : B∈S }.
If A~B, then { X : X~A } = { X : X~B }, which intuitively means that A and B have (i.e. are in) the same equivalence class.
If ¬A~B, then not only { X : X~A } ≠ { X : X~B }, but in fact { X : X~A } ⋂ { X : X~B } = ∅, which intuitively means that the equivalence classes for A and B are disjoint.
You can try proving these basic results to get a feel for the foundational structure of equivalence classes.
Conversation ended Jun 13, 2020 at 12:07.
BM0001 : Extending Pascal's triangle and circular permutations
Jun '2012
Jun '2013
♦ 
Basic Mathematics
This room is meant for all basic mathematical discussion, incl...
Participants
- user21820 56%
- Guru Vishnu 37%
- Doubtnut 6%
all times are UTC
