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)

17
votes
1answer
229 views

How many planar arrangements of $n$ circles?

Is there a known formula or recursion for the number of distinct arrangements of $n$ distinct circles in a plane, where two arrangements are regarded as distinct unless one can be obtained from the ...
17
votes
0answers
245 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 ...
16
votes
3answers
1k views

Why do graph degree sequences always have at least one number repeated? [duplicate]

Why do graph degree sequences always have at least one number repeated? $(1, 2, 2, 3)$ = Valid, as you can see, because the $2$ is repeated. $(1, 2, 3)$ = Not possible to construct a graph with ...
16
votes
4answers
5k views

Generating functions for combinatorics

I have no formal education in generating functions, but, based on another question, I have seen that they can be powerful for combinatorics. Are there a few general principles for using generating ...
16
votes
3answers
1k views

Alternating sum of squares of binomial coefficients

I know that the sum of squares of binomial coefficients is just ${2n}\choose{n}$ but what is the closed expression for the sum ${n}\choose{0}$$^2$ - ${n}\choose{1}$$^2$ + ${n}\choose{2}$$^2$ + ... + ...
16
votes
4answers
628 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
435 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
392 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
2answers
423 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 ...
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
642 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
863 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
722 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
774 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
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
1answer
467 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 ...
16
votes
1answer
325 views

On the inequality $\frac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$

For all positive integers $n$, $p(n)$ is the number of partitions of $n$ as the sum of positive integers (the partition numbers); e.g. $p(4)=5$ since $4=1+1+1+1=1+1+2=1+3=2+2=4.$ Prove ...
16
votes
3answers
507 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
703 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
500 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
266 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
256 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
239 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
636 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
720 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
911 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
3answers
663 views

Reference for combinatorial game theory.

What is a good reference material for elementary combinatorial game theory? By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more ...
15
votes
1answer
571 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
393 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
4answers
863 views

Where do summation formulas come from?

It's a classic problem in an introductory proof course to prove that $\sum_{ i \mathop =1}^ni = \frac{n(n+1)}{2}$ by induction. The problem with induction is that you can't prove what the sum is ...
15
votes
3answers
410 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
3answers
3k 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
752 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
224 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
2answers
418 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
541 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 ...