Reputation
509
Top tag
Next privilege 1,000 Rep.
Create new tags
Badges
2 14
Impact
~6k people reached

2d
comment Counting number of finite sequences with certain properties
please define 'longest common subsequence'. An example to clarify will make it handy.
2d
revised Average length of a cycle in a n-permutation
removed clarification after the question was reopened
2d
comment Average length of a cycle in a n-permutation
Proof of the fact: The expected number of k-cycles in a random permutation of $[n]$ is $\frac{1}{k}$**. Let $x_i=1$ if $i$ is a part of a k-cycle, else 0. $\frac{\sum_{i=1}^{n}x_i}{k}$ counts the number of k-cycles of $[n]$. We have $E \left( \frac{\sum_{i=1}^{n}x_i}{k} \right)=\frac{1}{k} \sum_{i=1}^{n}E(x_i)=\frac{1}{k} \sum_{i=1}^{n}\frac{1}{n}=\frac{1}{k}$ Proof of the fact: **Probability that 1 belongs to a k-cycle is 1/n (independent of k). Apart from one, a k-cycle can be constructed in $\binom{n-1}{k-1}(k-1)!(n-k)!$ . Dividing by $n!$ gives $\frac{1}{n}$
2d
revised Average length of a cycle in a n-permutation
clarification about why this question is not a duplicate
2d
revised Average length of a cycle in a n-permutation
clarification about why this question is not a duplicate
2d
comment Average length of a cycle in a n-permutation
@brian-m-scott : It would be great to hear about the approach you had on mind.
2d
accepted Average length of a cycle in a n-permutation
2d
comment Average length of a cycle in a n-permutation
Thanks Brian! Please let me know if my further analysis is incorrect. Total number of k-cycles (in all permutations) is $n!/k$ and total number of cycles (in all permutations) is $n! \cdot H_n$. Hence, $p(length=k \mid cycle)$ (probability that a random cycle has length k) is $\frac{n!/k}{n! \cdot H_n}=\frac{1}{k \cdot H_n}$. From here, avg cycle length=$\sum_{k=1}^{n}k\cdot p(length=k | cycle)=\sum_{k=1}^{n}k\cdot \frac{1}{k\cdot H_n}=\frac{n}{H_n}$
Aug
26
comment Average length of a cycle in a n-permutation
@martycohen No, its not a duplicate. As brian-m-scott suggests, the above question may be a pointer. We are looking for the 'average length' of a cycle, not 'average number' of cycles.
Aug
26
asked Average length of a cycle in a n-permutation
Jan
13
answered Number of upward closed subsets
Oct
3
comment Distribute n balls across m bags when bags are not empty to get the same sizes
Finally, each box contains either $\lfloor \frac{N}{m} \rfloor$ or $\lfloor \frac{N}{m} \rfloor +1$ balls. As the first step, we fill $i$ th box with $\lfloor \frac{N}{m} \rfloor -n_i$ balls for all $i$, so that each box contains $\lfloor \frac{N}{m} \rfloor$ balls. We are left with $r:=N-\lfloor \frac{N}{m} \rfloor$ balls, that can be distributed in $\binom{m}{r}$ ways. I hope this clarifies.
Sep
30
answered Distribute n balls across m bags when bags are not empty to get the same sizes
Sep
24
awarded  Autobiographer
Aug
22
comment Sperner family intersection with chains.
A better question to ask here would be: Can we classify the maximal antichains such that they intersect with every maximal chain? I expect the answer to be: An antichain intersects with every maximal chain only if it contains all subsets of a particular size.
Aug
22
comment Sperner family intersection with chains.
All subsets of same size form a maximal antichain. This has exactly one element common with any maximal chain.
Aug
22
comment Sperner family intersection with chains.
I reckon that the fact is incorrect: Consider the poset of subsets of $\{1,2,3,4\}$. The maximal antichain $\{\{1\},\{2,3,4\}\}$ has no element common with the maximal chain $\{2\} \subset \{2,3\} \subset \{2,3,1\} \subset \{2,3,1,4\}$
Jul
26
comment minimum number of unit distances required for a unit equilateral triangle
If $n$ points are placed on the $x$-axis at integer points, there will be $n-1$ unit distances and we do not have an equilateral triangle. But, we do not have "all" unit distances. (By the time I typed this comment, I could no longer see vadim's comment to which I intended to reply.)
Jul
26
asked minimum number of unit distances required for a unit equilateral triangle
Jul
25
comment How to calculate the number of integer solution of a linear equation with constraints?
See lemma 2 here