What is the maximum amount of checkers you can place on an $m \times n$ checkerboard such that no four checkers make a rectangle parallel to the rows and columns? Does there exist a closed form for the relationship between the number of checkers and the size of the checkerboard?  There are really too many cases and one specific solution for 4 checkers is below. The number of possible rectangles is given by the number of ways to choose two columns times the number of ways to choose two rows. i.e.: $$\frac{nm(n-1)(m-1)}{4}$$ The number of ways to put $4$ checkers on the board is: $${nm}\choose{4}$$ Thus, the number of ways to put $4$ checkers on a board without rectangles is just: $${{nm}\choose{4}} - \frac{nm(n-1)(m-1)}{4}$$ This does not answer your question regarding $k$ checkers on the board  So, what is the generalization of this question? And does there exist a closed form? And how to apply some counting skills in this problem and maybe apply some knowledge in the combinatorics design like my duplicated questions?
120606
What is the maximum amount of checkers you can place on an $m \times n$ checkerboard such that no four checkers make a rectangle parallel to the rows and columns?   The square colors don't matter; it is essentially a grid. Also the checkers are all indistinguishable.  I tried looking at the problem row by row, but this devolved into too many cases. I've also looked at small values of $m$, but couldn't get anywhere.  It seems that if there are a lot of rows, the optimal way is to place 2 checkers for the first $\binom{n}{2}$ rows, and then place 1 continuing down the rest. However, when there are relatively few rows, there seems to be a lot of cases regarding how many checkers to place for each row.
69954
In how many ways can $9$ black and $9$ white rooks be placed on a $6 × 6$ chess board, so that no white rook can capture a black one? A rook can capture another piece if it is in the same rank (row) or the same file (column) as the other piece, with no other pieces between the two?  I was thinking of a $6×6$ matrix, but that option doesn't seem to help?
52652
I don’t know how to handle this 3 players case, may anyone give a hand? Thanks!     When playing card game, there are 3 players playing 32 cards, each   receive 10 cards, 2 remind on the table. Overall are 4 aces and 4   kings in the game. How likely is P (E | D)? D = "The table remains 2   aces" E = "I (at least) get one king".   I guess I should have steps as follows.   P(E) = P(1King)+P(2K)+P(3K)+P(4K) P(D) = (4/32) * (4/32) = 1/256 P (E | D) = P(E) + P(D)   Equations may be used:  Counting combinations      The number of combinations of n objects taken r at a time is     nCr = n(n - 1)(n - 2) . . . (n - r + 1)/r! = n! / r!(n - r)!                 Number of favorable outcomes P(I) =     Total number of possible outcome
48908
Consider the squares of an $8 \times 8$ chessboard filled with the numbers $1,2,3,4 \ldots ,64$ in sequential order.   If we choose $8$ squares with the property that there is exactly $1$ from each row and exactly $1$ from each column, and add up the numbers in the chosen squares, show that the sum obtained is always $260$.  Please provide full solution and explanation.
66140
I am looking for an algorithm that can return the number of size of n squares that fit into a a rectangle of a given width and height, maximizing the use of space (thus, leaving the least amount of leftover space for squares that do not fit). Neither the rectangle nor the squares can be rotated.  For example, let's say I have a rectangle that is 5 inches by 7 inches, and I need it to fit 35 squares. The algorithm needs to tell me that the 35 squares fit if they are 1 inch wide/tall (as they could be laid out inside the rectangle in a 5 x 7 grid). Another example is if I need to divide a rectangle 35 inches by 1 inch into 35 squares. It should still tell me that the squares will fit if they are 1-inch wide/tall (as they could be laid out in the rectangle in a 35 x 1 grid).  The tricky part is that sometimes there may be leftover space, as the squares cannot be divided into partial squares. Let's say for either of the two examples above I need to lay out 34 squares and not 35 (in which case the answers would still be 1 inch), or maybe 33, or 7 squares. Or, perhaps the rectangle width and height aren't whole numbers. With the number of squares being a variable I need an algorithm that can tell me the size of the squares for a given rectangle width and height.  Thanks for your help!
37533
I know the formula for putting $n$ identical balls in $r$ different boxes such that each box has at least 1 ball, but what is the formula for putting $n$ different balls in $r$ different boxes, no box being empty?  Thanks!
3804
I am looking to calculate the number of $m\times n$ matrices which have no empty rows or columns (at least one $1$ in each row and column).  I have looked at the answers to a few similar questions such as  and  but I am struggling to make these approaches work in this case.
113586
The answer is 2454, apparently. I am getting 1446, however. Can anyone point out my error ?  We need to partition the solution into the mutually exclusive cases of choices of 4 letters where we have no repetitions (e.g. MATH), where we have one repetition (e,g, MATT) and where we have two repetitions (e.g. MMTT). Then we compute the corresponding number of perms of each case, and add, thus:  We have 8 unique letters, so we can make 8C4 selections with no repetitions.  We have 3 pairs of repetitions {MM, AA, TT} which gives us 3 * 7C2 choices with one repetition, since having chosen, say, MM, we need to select 2 more letters from the remaining 7 unique letters.  We have 3C2 choices with 2 repetitions taken from the set {MM, AA, TT}  So our total number of perms is:  (#choices of 4, no reps * 4!) + (#choices of 4, 1 rep * 4!/2!) + (#choices of 4, 2 reps * 4!/(2!2!) ) = (8C4 * 24) + (3 * 7C2 * 12) + (3C2 * 6) = 672 + 756 + 18 = 1446  Where did I go wrong ?
21054
I'm having trouble fully understanding this introductory combinatorics problem; this is all that's provided, so it's most likely me not fully comprehending the question.  Any help is appreciated.  The problem is this:     Each square of a 1998 by 2002 chess board contains either 0 or 1 such that the total number of squares containing 1 is odd in each row and each column. Prove that the number of white unit squares containing 1 is even.   I have discovered that this is a legitimate question and has been copied out of a book entitled 102 Combinatorial Problems where the problem and solution are clearly stated . Thank you and apologies for the ambiguity.
4247
We have a $100\times100$ board divided into $10^4$ unit squares. These squares are coloured with four colours so that every row and every column has $25$ squares   of each colour. Prove that there are $2$ rows and $2$ columns such that their $4$ intersections are painted with different colors.   My attempt:  I first counted number of pairs $\mathcal P$ $(r_1,r_2)$ such that $r_1,r_2$ belongs to same row, but different in colour. This can be done in $$\binom 42\times25\times 25$$ ways. So, in $100$ rows, this number is $$100\times\binom 42\times25\times 25$$ Now, we can find a pair of columns in $$\binom{100}2$$ ways.  So, by Pigeonhole Principle, we can find at least a pair of columns containing $$\left\lceil\frac{100\times\binom 42\times25\times 25}{\binom{100}2}\right\rceil\\=\left\lceil\frac{100\times75\times 50}{50\times99}\right\rceil\\=76$$ of those pairs $\mathcal P$.    But unable to proceed anymore. And this approach too seems misleading, because in every pair of columns, we can always find $\binom42\times25\times25$ pairs from $\mathcal P$. So, this approach makes no sense, I think.  What should be correct approach? And also, "if we pour $nk+1$ objects into $n$ urns, then there is an urn with $k+1$ objects", can this concept be plugged in this question?
1408
I have  and I have to fill 16 little squares with a diagonal  Rules   You cannot place more than 1 diagonal in each square The diagonals cannot touch each other (example bellow)       But what I seek here is a mathematical solution for this puzzle, I don't even know where to start looking for information.  Can someone explain how do I solve this puzzle using equations?
25547
Problem (1.8): There are ten girls and four boys in Mr. Fat's combinatorics class. In how many ways can these students sit around a circular table such that no boys are next to each other.   My Attempt: Total number of ways in which both boys are girls can be arranged on a circular table is $13!$ and the number of ways in which any two boys can be together is $2!*12!$. Therefore the answer is $13!-2*12!=11*12!$. Is this answer correct? I am asking this because I am confused about the exact meaning of the line "no boys are together." Does this mean that no two/three/four boys are together?   Note: Meanwhile I have made another attempt on the problem. We can place the $10$ girls on the circular table in $9!$ ways. Then we are left with $10$ spots which need to be filled with $4$ boys. This can be done in $P^{10}_4$ ways. Thus, the number of ways is $9!P^{10}_4$.
78459
So the question is how many ways are there to put N unlabelled balls in M labeled buckets.  One way (I think) I figured it out is $M^N$ ways to put each ball, divided by $N!$ permutations of ball ordering we don't care about:  $$M^N \over N!$$  First, is this correct?  Second, is there another way to approach it without using division?  I need to calculate it in a non-prime modulo space so division isn't available.  I really need a recurrence.
5024
Problem: Find the number of twelve-card hands containing four cards in each of three suits.   My solution:   pick a suit : 4 ways. choose 4 cards from the 13 in that suit: ${^{13}}{C}_{4}$ ways. pick another suit: 3 ways. choose 4 cards from the 13 in the new suit: ${^{13}}{C}_{4}$ ways. pick the final suit: 2 ways. choose 4 cards from the 13 in the final suit: ${^{13}}{C}_{4}$ ways.   Hence, total number of ways is $4\cdot{^{13}}{C}_{4}\cdot3\cdot{^{13}}{C}_{4}\cdot2\cdot{^{13}}{C}_{4} = {^{4}}{P}_{3}\cdot\left({^{13}}{C}_{4}\right)^3 $ total hands.   This is the incorrect answer. Why?
104965
A box contains $n$ identical balls numbered $1$ through $n$. Suppose $k$ balls are drawn in  succession.   (a) What is the probability that m is the largest number drawn?   (b) What is the probability that the largest number drawn is less than or equal to $m$?  I don't know how to solve this problem? Could you help me? For (a), I only know that the denominator will be $\binom{n}{k}$. How to find the numerator for both cases?
115265
Problem:    How many triangles do $m$ lines form if   a) Every two lines intersect and no three lines intersect at one point.  b) There are $n$ lines among $m$ lines that are parallel to each other. No other line is parallel to these $n$ lines, and no other two lines are parallel to each other. Again no three lines intersect at one point.  Thank you.
80113
If we remove the square in the upper right corner of a $8\times 8$ chessboard.  The question is: Is it possible to cover the entire remaining area, with $1\times 3$ chocolate bars? (they can be laid on the chessboard vertically and horizontally aswell)  For the answer: We know that there will be $63$ squares left on the chessboard, of which $32$ are white and $31$ are black, since the one in the upper right corner was black. $63$ is divisible by $3$, so it could be possible to cover the area, but that doesn't prove that an arrangement exists to do it. I'm not sure how to continue and am seeking help. Thanks.