Consider a pool of $N$ candidates, where $N$ is an even number. Each day, you would like to pair all the candidates up in order for them to get to know each other. In other words, each candidate should spend a day with each of the $N-1$ other candidates by the end of the internship. What algorithm allows for generating a daily list of pairings such that no two candidates meet each other twice? Is this always possible?
37793
Given a list of people:  [   1,   2,   3,   4,   5,   6 ]   The goal is to generate some number of lists of pairs.  [   [     [1,2],     [3,4],     [5,6]   ],   [     [2,3],     [4,5],     [6,1]   ],   [     [3,1],     [5,2],     [4,6]   ],   [     [2,6],     [3,5],     [4,1]   ],   [     [4,2],     [5,1],     [3,6]   ] ]   Each list of pairs represents the schedule for that week. Each pair represents the people who should meet with that week.  In the example above, in the first week, persons 1 &amp; 2, 3 &amp; 4, 5 &amp; 6 will meet. In the second week, persons 2 &amp; 3, 4 &amp; 5, 6 &amp; 1 will meet and so on until everyone has meet with each other.  After some experimenting, it appears that for a list of n people, if n is even, there will be n - 1 lists of pairs. If n is odd, there will be n lists of pairs and one person will have a bye week where they don't meet with anyone.  Is there an algorithm to generate this list of pairs given a list of people?
89588
Question:  Consider a group of n people with the following properties:  • no person is friends with everyone, • any pair of strangers share exactly one friend in common,  • no three people are mutually friends. Show that everyone has the same number of friends.  I want to solve this using Ramsey's theorem but I'm struggling to formulate it in a way that would make it straightforward.. Any help would be greatly appreciated.
22855
"How large must a class be to make the probability of finding two people with the same birthday at least 50%?"  I have 360 friends on facebook, and, as expected, the distribution of their birthdays is not uniform at all.  I have one day with that has 9 friends with the same birthday. (9 months after big holidays and valentines day seem to be big ones, lol..)  So, given that some days are more likely for a birthday, I'm assuming the number of 23 is an upperbound.  Has there been a better estimate to this problem?
74356
This is a follow-up to a Stackoverflow .  There are established algorithms (such as the ) that one should use to shuffle an array, rather than relying on "naive" ad-hoc implementations.   I am now interested in proving (or disproving) that my naive algorithm is broken (as in: does not generate all possible permutations with equal probability).  Here is the algorithm:     Loop a couple of times (length of array should do), and in every iteration, get two random array indexes and swap the two elements there.   Obviously, this needs more random numbers than KFY (twice as much), but aside from that does it work properly? And what would be the appropriate number of iterations (is "length of array" enough)?
85581
Find the number of ways in distributing $8$ distinct balls into $6$ distinct boxes such that there is at least $1$ ball in each box.  We are well acquainted with the traditional Inclusion-Exclusion principle in solving this and it will come up as $191520$ ways.  I tried in this way:  When we distribute $8$ balls into $6$ boxes we have two possible cases  Case $1.$ There are exactly $2$ boxes with $2$ balls each  Case $2.$ There is exactly $1$ Box with $3$ balls in it.  For Case $1$, the distribution is done by choosing $2$ boxes from $6$ boxes and $2$ balls from $8$ balls and those two balls can be arranged in $2!$ ways. But I require another two balls from remaining $6$ balls to be placed in each of these two boxes which can be done in $\binom{6}{2} \times 2!$ ways. Finally remaining $4$ balls can be distributed in remaining $4$ boxes in $4!$ ways. So total number of ways for Case $1.$ is  $$\binom{6}{2} \times \binom{8}{2} \times 2! \times \binom{6}{2} \times 2! \times 4!=604800$$  For Case $2$, the number of ways is  $$\binom{6}{1} \times \binom{8}{3} \times 5!=40320$$  I am pretty sure the value obtained for Case $2.$ is correct. but I could not find where I went wrong in Case $1.$
33535
$n$ people attend the same meeting, what is the chance that two people share the same birthday? Given the first $b$ birthdays, the probability the next person doesn't share a birthday with any that went before is $(365-b)/365$. The probability that none share the same birthday is the following: $\Pi_{0}^{n-1}\frac{365-b}{365}$. How many people would have to attend a meeting so that there is at least a $50$% chance that two people share a birthday?   So I set $\Pi_{0}^{n-1}\frac{365-b}{365}=.5$ and from there I manipulated some algebra to get $\frac{364!}{(364-n)!365^{n}}=.5\iff (364-n)!365^{n}=364!/.5=.....$   There has to be an easier way of simplifying this.
39195
I need a pair of non-isomorphic graphs with the smallest n-vertex possibility and where degree sequences are the same. Is the minimum number 2, such as a multigraph with n=2? Please help with the reasoning on this question. Thank you!
51768
Here's an interesting problem that I came up with the other night.  With straight speed dating, (assuming the number of men and women are equal) the number of iterations that need to be made before every man has chatted with every woman is N/2, where N is the total number of people.  Gay speed dating is much more complex. The traditional model obviously won't work. Assuming in straight speed dating, the men stay at their tables, the "sitting" men in gay speed dating won't meet one another (nor will the "standing" men).  Counting combinations in gay speed dating manually, I see the following numbers:  f(2) = 1 f(3) = 3 f(4) = 3 f(5) = 5 f(6) = 5   These numbers suggest that gay speed dating can be done with N or N-1 iterations (albeit in a much more chaotic pattern).  Anyone have any ideas? Also, if it is N iterations, would there be a pattern that could be followed? I.e.: could the gentlemen circle a rectangular table in a clockwise fashion, then rearrange themselves and continue in another fashion such that given any number of men, every man would be paired with every other man in the smallest number of iterations and without pairing two men together twice.
53938
Find a recurrence relation for the number of $n$-digit binary sequences with no pair of consecutive $1$s.  I know my base case:$$a_1 = 2$$ for either $1$ or $0$. Normally to construct the recurrent relation I would say fill in $n-1$ spaces then add a $1$ or $0$, which is simply:$$a_n = 2\cdot a_{n-1}$$However, I don't believe this is right, because this doesn't take into account that there can't be any consecutive $1$s.  Even when I use the base case of $2$ digits:$$a_2 = 3$$for either $01$, $10$, or $00$, I still get the recurrence relation of:$$a_n = 3\cdot a_{n-2}$$which also does not account for $01$ and $10$ occurring consecutively.   So how would I express this?
75144
It is a trivial exercise in the pigeonhole principle to show that if an organization contains $m$ people and forms disjoint committees of $n$ members each, then at most $$\bigg \lfloor \frac{m}{n} \bigg\rfloor$$ committees can be formed.  However, I have recently attempted a seemingly simple variation on this problem: what if the committees need not be disjoint, but no two committees can share more than one member.  It seems like another easy exercise in the pigeonhole principle, but I have been unable to come up with a formula for the largest possible number of committees in terms of $m$ and $n$. Does anyone know of such a formula?
56753
Assume that there are $n$ people line up to get into $m$ different clubs. How many ways to do it if each people is different and order of people in the line matters.  Sol. Clearly, each people has $m$ different choices for clubs. So there are $m^n$ ways of choosing clubs. Now we count number of different lines. Let $x_i$ be the number of people lining to get to the club $i$, $1 \leq i \leq m$, $x_i \geq 0$.  Then $$x_1 + x_2 + ... + x_m = n$$ with $x_i$ non-negative integers. So there are ${m+n-1}\choose{n-1}$ ways, ignore order in each line. So there are ${m+n-1}\choose{n-1}$$ x_1!x_2!...x_n!$ possible lines.  The answer is weird since it is in $x_1, ...,x_n$ terms, and I think it is wrong. However, I am not sure how to fix it.  Any help please ?
96602
So the question has three parts and I'm stuck on the third, that's how it goes :  Claude wants to invite 5 friends to dinner in a pool of 11 friends.  a) How many ways can he do this?  My answer : $\binom{11}{5} = 462$  It's correct  b) 2 of these friends can't be separated from each other, how many ways?  My answer : $\binom{10}{4} = 210$  It's correct  c) 2 of them are mad at each other and can't be invited together, how many ways?  My answer : ''a) - b)'' = $\binom{11}{5} - \binom{10}{4} = 252$  It's false  The answer: 378    I can't seem to understand, plus there is no explanation in my textbook, it's straight the answer, so I'm completely lost. I've tried lots of different things but never got it right.   Thank you for helping me understand. Combinatorics are like hell to me.
117406
Suppose I have a set of $n$ boys and each subset of $1\leqslant k \leqslant n$ boys knows at least $k$ girls then this means that the set of boys $B$ satisfies the marriage condition.  I am doing an exercise from a Graph Theory book and it says we can show by induction on $n$ that the number of possible marriage arrangements is $\geqslant t!$ if every individual boy knows at least $t \leqslant n$ girls or there are $\geqslant t!/(t-n)!$ possible marriages if each individual boy knows at least $t&gt;n$ girls.   I am struggling to see how the induction hypothesis can be implemented to prove the $n+1$ case. When you swap from the $n$ to $n+1$ case the conditions change and I can't see the link between them.  Would anyone be able to point me in the right direction?
39087
I am struggling with this probability/combinatorics problem.  the problem states: "11 people are seated around a round table. At some point, everyone stands up and sits again at a randomly chosen seat. Show that the expected value of the number of pairs which swapped places (A sat at B's place and B sat at A's place) is 1/2."  I struggle with calculating the number of orderings in which pairs switch places. I know we have 10! possible permutations for 11 people sitting in a circle, and there are $11\choose2$ possible pairs that could switch places. But I'm not sure how to count for example the number of permutation in which only one couple switches places.
103156
I have no idea what the first problem on this list is asking? The others I can figure our, but does anyone know what the first one is actually asking? If so, how would you set it up?  Nate can only invite 8 people to his birthday, but has 13 friends he’d like to invite.  Eight of his friends are boys and five are girls.  Three of the girls are roommates and must stay together.  If Dante randomly selects 8 people, determine the probability for each scenario.   Dante’s random selection is a valid outcome Dante does not invite any girls Dante invites an equal number of boys and girls
43369
During a period of $n$ days, two persons drink beers, one each. There are $n$ different beers $B_1, B_2, B_3,\ldots, B_n$, where $n\geqslant 1$ is an integer. t Person1 drinks the beers in order, i.e., on the $i$-th day, she drinks beer $B_i$. Person2 takes a uniformly random permutation $a_1, a_2, \ldots, a_n$ of the set $\{1, 2,\ldots, n\}$ and drinks beer $B_{a_i}$ on the $i$-th day. Let $X$ be the random variable whose value is the number of days during which person 1 and person 2 drink the same beer. Determine the expected value $\mathbb E(X)$ of $X$.  I know that I should let $X$ be the number of days during which both persons drink the same beer. And  $$ X_i = \left\{\begin{array}{rc} 1,&amp;\text{if they drink the same beer on the }i\text{-th day} \\ 0,&amp;\text{if they drink different beers on the }i\text{-th day}\end{array}\right. $$  Then  $$\begin{align} \mathbb E[X_i] &amp;= 1\cdot P(X=1) = P(\text{Person 1 and Person 2 drink beer }i) \\&amp;= P(\text{Person1 drinks beer }i)P(\text{Person 2 drinks beer }i) \\ &amp;= 1\cdot P(\text{Person 2 drinks beer }i) = \frac{1}{(n-i)!} \end{align}$$   So, is my approach right? If it's will the next step be: $\mathbb E(X) = n\cdot\frac{1}{(n-i)!}$?
15756
Number of ways to select $K$ people from $N$ people (who are aligned in a line)  such that at least $r$ people are there in between them  Ex: I want to select 3 people from 10 people (who are aligned in a line) such that at least 2 people should be there between the selected people   May I know the resources for learning this type of problems , also what is the solution if people are arranged in circular manner