This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

14
votes
6answers
3k views

What is the probability of this exact same Champions League draw?

As you can see here, there has been a strange coincidence with the UEFA Champions League draw. The real draw which took place today, ended up being exactly the same as the rehearsal draw which took ...
14
votes
2answers
161 views

Simplifying $\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$

How do I simplify: $$\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$$ Should I use modulos or should I factor them? Or any I suppose to use combinatorics? Any one have a ...
14
votes
3answers
459 views

Are the logarithms in number theory natural?

I find the frequent emergence of logarithms and even nested logarithms in number theory, especially the prime number counting business, somewhat unsettling. What is the reason for them? Has it maybe ...
14
votes
2answers
272 views

A question on partitions of n

Let $P$ be the set of partitions of n. Let $\lambda$ denote the shape of a particular partition. Let $f_\lambda(i)$ be the frequency of $i$ in $\lambda$ and let $a_\lambda(i) := \# \lbrace j : ...
14
votes
3answers
985 views

Cutting a unit square into smaller squares

My algebra professor gave me this puzzle a while back. I'm pretty sure I've found the right solution; nonetheless, I wanted to share it and see if you come up with anything really nice or unexpected. ...
14
votes
3answers
339 views

Why there are $11$ non-isomorphic graphs of order $4$?

I'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why. I know that ...
14
votes
2answers
366 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
14
votes
3answers
2k views

Gay Speed Dating Problem

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 ...
14
votes
3answers
2k views

How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, ...
14
votes
1answer
1k views

Combinatorial proof of a Fibonacci identity: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

Does anyone know a combinatorial proof of the following identity, where $F_n$ is the $n$th Fibonacci number? $$n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3$$ It's not in the place I thought it ...
14
votes
2answers
657 views

Shortest sequence containing all permutations

Given an integer $n$, define $s(n)$ to be the length of the shortest sequence $S = (a_1, \cdots a_{s(n)})$ such that every permutation of $\{1,\cdots,n\}$ is a subsequence of $S$. If $n=1$, then $S = ...
14
votes
3answers
1k views

Minimum number of integer-sided squares needed to tile an $m$ by $n$ rectangle.

Let $T(m,n)$ for integers $m,n$ be the least number of integer-sided squares needed to tile an $m\times n$ rectangle. Clearly $T(kx,ky)\leq T(x,y)$. Are there integers $x,y,k\gt 1$, such that ...
14
votes
1answer
4k views

Odd and even numbers in Pascal's triangle-Sierpinski's triangle

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. I recently learned that when the Pascal's triangle is reduced ...
14
votes
1answer
307 views

How many strategies are there for this puzzle where one of n logicians must call his own hat's color among n?

$n$ logicians are wearing hats which can be of $n$ different colors. Each logician can see the colors of all hats except his own. The logicians must simultaneously call out a color; they win if at ...
14
votes
2answers
525 views

What is the probability that every pair of students studies together at some point?

A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 ...
14
votes
4answers
390 views

Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)

I found the following formula in a book without any proof: $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$ I don't know how to prove this at all. Could you show me how ...
14
votes
3answers
301 views

On a Putnam's 2009 problem [duplicate]

Find all even natural numbers $n$ such that the following is true: There is a non-constant function $f : \Bbb{R}^2 \longrightarrow \Bbb{Z}_2$ such that for any regular $n$-gon $A_1...A_n$, $f(A_1) + ...
14
votes
1answer
358 views

Show that $ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $

Show that $$ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $$ I don't know whether such identity already exists, or has been posted here before. I discovered this identity while ...
14
votes
2answers
689 views

Combinatorial proof of arithmetic geometric mean inequality

It is a well known fact that for positive reals $x_1, x_2, \dots, x_n$, their arithmetic mean is no less than their geometric mean: $$ \frac{x_1 + x_2 + \dots + x_n}{n} \ge \sqrt[n]{x_1 x_2 \dots ...
14
votes
2answers
568 views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
14
votes
1answer
460 views

How many possible board states in 2048?

I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" ...
14
votes
4answers
434 views

Gambling puzzle

A math friend of mine showed me this strange gambling puzzle. There is a button in a casino and every time you press it you can win either $1$ or $0$ dollars. The probability of winning $1$ dollar ...
14
votes
1answer
530 views

What is the combinatoric significance of an integral related to the exponential generating function?

Suppose that you have an exponential generating function.: $E(z)=\sum_{n=0}^{\infty} \frac{a_{n}z^{n}}{n!}$, and that the definition of $a_{n}$ can be reasonably extended to noninteger arguments. (the ...
13
votes
6answers
1k views

Why $0!$ is equal to $1$? [duplicate]

Many counting formulas involving factorials can make sense for the case $n= 0$ if we define $0!=1 $; e.g., Catalan number and the number of trees with a given number of vetrices. Now here is my ...
13
votes
5answers
436 views

How do we show the equality of these two summations?

How do you show the following? $$\sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1 = \sum \limits_{j=1}^{n}\ \sum \limits_{k=1}^{j}\ \sum \limits_{i=1}^{k}\ 1 $$ It's not ...
13
votes
3answers
1k views

The $5n+1$ Problem

The Collatz Conjecture is a famous conjecture in mathematics that has lasted for over 70 years. It goes as follows: Define $f(n)$ to be as a function on the natural numbers by: $f(n) = n/2$ if $n$ ...
13
votes
5answers
535 views

Combinatorially showing $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$

I am trying to show that $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$. I found that using stirling's approximation, I can get: $$ \lim_{n\to \infty}{\frac{2n\choose n}{4^n}}= \lim_{n\to ...
13
votes
3answers
307 views

Integer sequences which quickly become unimaginably large, then shrink down to “normal” size again?

There are a number of integer sequences which are known to have a few "ordinary" size values, and then to suddenly grow at unbelievably fast rates. The TREE sequence is one of these sequences, which ...
13
votes
4answers
698 views

How this operation is called?

This operation is similar to discrete convolution and cross-correlation, but has binomial coefficients: $$f(n)\star g(n)=\sum_{k=0}^n \binom{n}{k}f(n-k)g(k) $$ Particularly, $$a^n\star ...
13
votes
4answers
499 views

Intriguing polynomials coming from a combinatorial physics problem

For real $0<q<1$, integer $n >0 $ and integer $k\ge 0$, define $$[k, n]_q \equiv -\sum_{m=1}^{n} q^{m(k+1)} (q^{-n}; q)_m = -\sum_{m=1}^{n} q^{m(k+1)} \prod_{l=0}^{m-1} (1-q^{l-n})$$ ...
13
votes
2answers
813 views

Color an $n\times n$ square with $n$ colors

How many ways is there to color an $n\times n$ square grid with $n$ colors such that each column and each row contains exactly one $1\times 1$ square of each color? And how many ways if the same is ...
13
votes
3answers
340 views

Show that $\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
13
votes
2answers
338 views

How much would it cost to try every possible burger combination?

I was at a restaurant that allows you to build your own custom burger. I got bored and started to work out how many possible combinations of burger there could be. After figuring that out and sharing ...
13
votes
5answers
515 views

Number of ways to divide a stick of integer length $N$

Suppose we have a stick of integer length $N$. I'm looking for (preferably closed-form) formula that gives the numbers of ways in which we can divide the stick into 3 parts with distinct integral ...
13
votes
2answers
1k views

Automorphisms of the Petersen graph

I am trying to find out the automorphism group of the Petersen graph. My book carries the hint: "Show that the $\tbinom{5}{2}$ pairs from {1, . . . , 5} can be used to label the vertices in such a way ...
13
votes
3answers
391 views

Find the number of pairs $(m, n)$ of positive integers such that $\frac{ m}{n+1} < \sqrt{2} < \frac{m+1}{n}$

Find the number of pairs $(m, n)$ of positive integers such that $\frac{ m}{n+1} < \sqrt{2} < \frac{m+1}{n}$ Constraint: $m$ and $n$ are both less than or equal to 1000 I toiled over this ...
13
votes
2answers
211 views

Evaluate the determinant $\det\left[ \binom{2n}{n+i-j} \right]_{i,j=0}^{n-1}$

I am trying to show that: \begin{equation} \det\left[ \binom{2n}{n+i-j} \right]_{i,j=0}^{n-1}=\prod_{i=0}^{n-1} \frac{\binom{2n+i}{n}}{\binom{n+i}{n}} \end{equation} I have tried playing with the ...
13
votes
2answers
8k views

Combinatorial proof of summation of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Can you guys help me prove this? There is a way of proving this logically but I was hoping to find a more "mathematical" proof, if possible. $$\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n ...
13
votes
2answers
298 views

Combinatorial interpretation of this identity of Gauss?

Gauss came up with some bizarre identities, namely $$ \sum_{n\in\mathbb{Z}}(-1)^nq^{n^2}=\prod_{k\geq 1}\frac{1-q^k}{1+q^k}. $$ How can this be interpreted combinatorially? It strikes me as being ...
13
votes
4answers
762 views

Coloring the faces of a hypercube

I will restate the 3-D version of the problem. In how many ways can you color a regular cube with 2 colors up to a rotational isometry. The answer is of course a special case of Burnsides Lemma which ...
13
votes
1answer
168 views

Filling an $n\times n$ board

This problem has been bothering me for quite a while now. Consider an $n\times n$ chessboard, with $n$ being an odd positive integer. In the middle square of the board, a $0$ is placed. Starting with ...
13
votes
1answer
669 views

Is it true that a connected graph has a spanning tree, if the graph has uncountably many vertices?

I found a proof that every connected graph (possibly infinite) has a spanning tree in Diestel's Graph Theory (Fourth Edition), Ch. 8 that uses Zorn's Lemma, but at a crucial step it seems to be ...
13
votes
3answers
4k views

How to rotate n individuals at a dinner party so that every guest meets every other guests

I'm throwing an event where every individual is suppose to meet every other individual so I'm trying figure out how to rotate them. My friends say its easy but they have yet to come up with an answer ...
13
votes
2answers
349 views

A card game with no decisions

A friend showed me a mindless card game he plays, in which the initial state of the deck completely determines whether he wins or loses. The game is played as follows: Shuffle a standard $52$ card ...
13
votes
2answers
446 views

Signed Multinomial Expansion Coefficients?

I've been spending probably an undue amount of time trying to compute the coefficients of polynomials of the form $p_n(x_1, ..., x_n) = \displaystyle\prod_{\sigma \in \{ -1 , 1 \}^{n-1} } (x_1 + ...
13
votes
2answers
290 views

A question about the minesweeper game

This is just out of curiosity. Suppose the game has $m \times n$ boxes for positive integers $m$ and $n$. How can we make the sum of the numbers on a finished game the most? There are two extreme ...
13
votes
3answers
456 views

Probability of a winning consecutive $k$-subset out of $n$ coin flips

Assume we flip a coin $n$ times. A $k$-sequence is defined as any consecutive sequence of coin flips of length $k$. Call a $k$-sequence "winning" if there are strictly more heads than tails. What is ...
13
votes
1answer
310 views

How many $N$ of the form $2^n$ are there such that no digit is a power of $2$?

How many $N$ of the form $2^n,\text{ with } n \in \mathbb{N}$ are there such that no digit is a power of $2$? For this one the answer given is the $2^{16}$, but how could we prove that that this ...
13
votes
1answer
307 views

Enumerative Combinatorics

Sam has $255$ cakes, each labeled with a unique non-empty subset of $\{1, 2, 3, 4, 5, 6, 7, 8\}$. Each day, he chooses one cake uniformly at random out of the cakes not yet eaten. Then, he eats that ...
13
votes
1answer
624 views

Rubik's cube interesting questions?

The upper bound for the number of moves required to solve a regular Rubik's cube has been shown to be 20. Two questions come to mind: Does this result have more general significance? What are the ...