For 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)

16
votes
4answers
625 views

How to solve $\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2$?

I have tried something to solve the series $$\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2.$$ My approach is : $$(1+x)^n=\binom{n}{0} + \binom{n}{1}x + ...
16
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
16
votes
4answers
430 views

Prove that $n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $

Basically I had some fun doing this: 0 1 1 6 7 6 8 12 19 6 27 18 37 6 64 24 61 125 etc. starting with ...
16
votes
3answers
1k 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 ...
16
votes
7answers
2k views

Probability that the sum of three integer numbers (from 1 to 100) is more than 100

I have an urn with $100$ balls. Each ball has a number in it, from $1$ to $100$. I take three balls from the urn without putting the balls again in the urn. I sum the three numbers obtained. What's ...
16
votes
6answers
387 views

Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$

Prove that $$ \frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}. $$ I tried already by induction over $k$ but i ...
16
votes
3answers
2k views

Consecutive birthdays probability

Let $n$ be a number of people. At least two of them may be born on the same day of the year with probability: $$1-\prod_{i=0}^{n-1} \frac{365-i}{365}$$ But what is the probability that at least two ...
16
votes
4answers
638 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
16
votes
2answers
851 views

What's the General Expression For Probability of a Failed Gift Exchange Draw

My family does a gift exchange every year at Christmas. There are five couples and we draw names from a hat. If a person draws their own name, or the name of their spouse, all the names go back in a ...
16
votes
4answers
715 views

Determinant of a generalized Pascal matrix

Let $M$ denote the infinite matrix defined recursively by $$ M_{ij} = \begin{cases} 1, & \text{if } i=1 \text{ and } j=1; \\ aM_{i-1,j}+bM_{i,j-1}+cM_{i-1,j-1}, & ...
16
votes
3answers
7k views

Expanding and understanding the poison pills riddle

You might have heard of the riddle that asks you to identify one fake pill (poisoned) among 12 pills of identical appearance, with the fake pill being either lighter or heavier than the others. You ...
16
votes
4answers
530 views

Limit of $\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1}\right)$

I'm trying to calculate the limit for the sum of binomial coefficients: $$S_{n}=\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1} \right).$$
16
votes
1answer
757 views

How many different shapes can I make with this toy?

I have the following toy, perhaps some of you have seen it before. It consists of a bunch of cubes with an elastic string in the middle. You can bend it into different shapes like this: Or this: ...
16
votes
1answer
792 views

Why should a combinatorialist know category theory?

I know almost nothing about category theory (I have just skimmed the first chapters of Aluffi's algebra book), reading this question got me thinking... why should someone mostly interested in ...
16
votes
3answers
364 views

Distribution of a maximum

Randomly select $n$ numbers from ${\{1,2,\dots,m\}}$ without replacement, and order the chosen elements increasingly: $X_1 < X_2 < \dots < X_n$ And we can view each $X_i$ as a random ...
16
votes
3answers
495 views

Counting the number of polygons in a figure

I often come across figures like this on the net, or as contest problems, asking to find the number of a specific type of polygon in the figure (triangles, in this case). But I've never really found ...
16
votes
1answer
1k views

Given a set of digits, what is the biggest number we can make using exponentiation - numberphile noodle quiz

The question is motivated by a question on a can of number noodles. Each item is a digit between $0$ and $9$. Clearly, if you form a string and consider it to represent a base $10$ integer, then ...
16
votes
3answers
696 views

What's next for me?

I'm in my last year of undergrad, and I would like to do original research for my senior thesis. I am already published in finite group theory and am looking for a new topic to study. I have taken ...
16
votes
2answers
485 views

The Weaver Android app $\rightarrow$ cute combinatorics problem

There's an Android puzzle app called "The Weaver". My question is why every level seems to be solvable in far fewer moves than one might naively think. Here's a link for people who want to play along ...
16
votes
1answer
261 views

Is there a combinatoric identity for the multiplicities of the following set?

Are you ready for some psychedelic pictures? Define the multiset$$S_n=\left\{\sum_{j=1}^n(-1)^{\left\lfloor(k-1)/2^{j-1}\right\rfloor}u_n^j\mbox{ for }1\leq k\leq2^n\right\}$$ where ...
16
votes
1answer
254 views

Combinatorics in finite vector space

Let $q$ be a prime power and $V$ a finite $\mathbb F_q$-vector space with two subspaces $I$ and $J$. Let $k$, $a$ and $b$ be non-negative integers. Determine the number of subspaces $K$ of $V$ ...
16
votes
1answer
237 views

Some four clubs have exactly $1$ student in common

There are $100$ students in a school, and they form $450$ clubs. Any two clubs have at least $3$ students in common, and any five clubs have no more than $1$ student in common. Must it be that some ...
15
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$ ...
15
votes
5answers
634 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 ...
15
votes
1answer
1k views

Hard combinatorics and probability question.

A large white cube is painted red, and then cut into $27$ identical smaller cubes. These smaller cubes are shuffled randomly. A blind man (who also cannot feel the paint) reassembles the small cubes ...
15
votes
1answer
710 views

Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s - total $kn$ cards.

Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s - total $kn$ cards - so that no same numbers appear consecutively. For $k=2$ we can compute it by using ...
15
votes
4answers
909 views

Finding an Explicit Formula from the Recurrence: $na_{n}= 2 ( a_{n-1}+a_{n-2})$

Here is the recurrence: $$na_{n}=2(a_{n-1}+a_{n-2}) \qquad\text{ where } a_{0}=1\text{ and }a_{1}=2$$ At first I thought that this could be easily solved by simply multiplying the Fibonacci ...
15
votes
1answer
570 views

The 'Unlock All Digits' Game

I challenged myself and thought of a new problem I tried to solve. Here are the rules : The goal is to 'unlock' all the numbers $0,1,2,3,4,5,6,7,8$ and $9$ When you start the game, the only number ...
15
votes
3answers
390 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 ...
15
votes
3answers
214 views

Proving that $\frac{(k!)!}{k!^{(k-1)!}}$ is an integer

I have to prove that: $$\frac{(k!)!}{k!^{(k-1)!}} \in \Bbb Z$$ for any $k \geq 1, k \in \Bbb N$ Tried doing $t = k!$ which would give $$\frac{t!}{t^{t/k}}$$ But I think I just made it harder, and ...
15
votes
3answers
401 views

Is it possible to uniquely number faces of a hexagonal grid with consecutive numbers?

You have a grid of regular hexagons. The aim of the game is to have each hex contain the numbers 1-6 on its edges. Each edge must also be connected to another edge that has a value one higher and ...
15
votes
2answers
418 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 ...
15
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 ...
15
votes
2answers
1k views

Combinatorial interpretation of Binomial Inversion

It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...
15
votes
2answers
743 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 = ...
15
votes
3answers
196 views

Prove a combinatorial identity

Prove the combinatorial identity $$ \sum_{n_1+\ldots+n_m=n} \;\; \prod_{i=1}^m \frac{1}{n_i}\binom{2n_i}{n_i-1}=\frac{m}{n}\binom{2n}{n-m}, \enspace n_i>0,i=1,\ldots,m $$ I "discovered" this ...
15
votes
1answer
411 views

How find the “how many good dyeing” method

$A_{1},A_{2},\cdots,A_{2013}$ are $2013$ different points placed on the circumference of a circle. Each point is dyed one of three colors: red, blue and green. We call a dyeing method good, if for any ...
15
votes
2answers
390 views

Why are braid numbers of the form $Q_h^2$ or $2 \times Q_h^2$?

Consider two piles of $h$ playing cards each, all distinct. Repeatedly take one of the cards on top of one of these two piles and move it on top of one of two new piles, until both of the new piles ...
15
votes
1answer
446 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 ...
15
votes
2answers
417 views

A “What's my vector?” game

Alice chooses a binary vector $V$ of length $n$ which is unknown to Bob. In each round Bob can choose any number of indices $i$ and then Alice tells Bob how many of the $V_i$ are set to $1$. The ...
15
votes
2answers
425 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 ...
15
votes
3answers
630 views

Finding when $(a-n)(b-n)|(ab-n)$

Given $n$ and $k$, find the number of pairs of integers $(a, b)$ which satisfy the conditions $n < a < k, n < b < k$ and $(ab-n)$ is divisible by $(a-n)(b-n)$. Given: $0 ≤ n ≤ 100000, \ n ...
15
votes
2answers
540 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 ...
15
votes
3answers
1k 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, ...
15
votes
1answer
308 views

Expected size of subset forming convex polygon.

If there are $4$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the interval $\left(0,1\right)$, what is the expected largest size (or ...
15
votes
2answers
770 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 ...
15
votes
1answer
333 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 ...
15
votes
0answers
195 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
14
votes
3answers
787 views

Are there complete Graeco-Latin squares?

Are there two orthogonal complete Latin squares of any order greater than 1? If so, what is the smallest order for which they exist? (A Latin square of order $n$ is an $n\times n$ array of symbols ...
14
votes
5answers
1k views

Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially

$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$ For the first one, I was able to express $k^2$ in terms of the binomial coefficients by ...