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)

19
votes
2answers
999 views

Not lifting your pen on the $n\times n$ grid

Does there exist $n$, and $r<2n-2$, such that the $n\times n$ square grid can be connected with an unbroken path of $r$ straight lines? Note: This has essentially already been asked - see this ...
19
votes
4answers
239 views

How to Prove : $\frac{2}{(n+2)!}\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^{n+2}=\frac{n(3n+1)}{12}$

While I calculate an integral $$ \int\limits_{[0,1]^n}\cdots\int(x_1+\cdots+x_n)^2\mathrm dx_1\cdots\mathrm dx_n $$ I used two different methods and got two answers. I am sure it's equivalent, but ...
19
votes
1answer
770 views

What function satisfies $F'(x) = F(2x)$?

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed ...
19
votes
1answer
2k 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 ...
19
votes
7answers
835 views

Number of ways to connect sets of $k$ dots in a perfect $n$-gon

Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices in a given perfect $n$-gon such that no two lines intersect at the interior of the $n$-gon and no vertex remains ...
19
votes
6answers
687 views

How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?

How do I prove the following identity directly? $$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$ I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized ...
19
votes
2answers
1k 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 ...
19
votes
1answer
968 views

Why is a general formula for Kostka numbers “unlikely” to exist?

In reference to Stanley's Enumerative Combinatorics Vol. 2: right after he has defined Kostka numbers (section 7.10), he mentions that it is unlikely that a general formula for $K_{\lambda\mu}$ exists,...
19
votes
3answers
630 views

Counting binary sequences with no more than $2$ equal consecutive numbers

I invented the following problem, but I can't solve it. There are $n$ $1$'s and $n$ $0$'s and my question is what is the number of ways to arrange them avoiding $3$ equal consecutive numbers. So for ...
19
votes
1answer
586 views

Probability that two randomly chosen permutations will generate $S_n$.

Every undergraduate learns a fact about the symmetric group that $(1\,2)$ and $(1\,2\,\cdots\,n)$ generate $S_n$. Also, it is interesting to know that for a prime $p$, any 2-cycle and any $p$-cycle ...
19
votes
2answers
2k 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 ...
18
votes
2answers
2k views

4 cards are drawn from a pack without replacement. What is the probability of getting all 4 from different suits?

4 cards are drawn from a pack without replacement. What is the probability of getting all 4 from different suits? Here's how I tried to solve: For the first draw, we have 52 cards, and we have to ...
18
votes
7answers
3k views

What is combinatorics?

I've tried to search the web and in books, but I haven't found a good definition or definitive explanation of what combinatorics is. Could anyone give me a definition/explanation of combinatorics, ...
18
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 considering a ...
18
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$ + ... + $(...
18
votes
4answers
6k 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 ...
18
votes
3answers
587 views

An Inequality Involving Bell Numbers: $B_n^2 \leq B_{n-1}B_{n+1}$

The following inequality came up while trying to resolve a conjecture about a certain class of partitions (the context is not particularly enlightening): $$ B_n^2 \leq B_{n-1}B_{n+1} $$ for $n \geq ...
18
votes
1answer
2k 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 ...
18
votes
4answers
841 views

Is there a way to prove $\int {x^n e^x dx} = e^x \sum_{k = 0}^n {( - 1)^k \frac{{n!}}{{(n-k)!}}x^{n-k} } + C$ combinatorially?

In How to integrate $\int x^n e^x dx$?, it is shown that $$\int {x^n e^x dx} = e^x \sum_{k = 0}^n ( - 1)^k \frac{n!}{(n-k)!}x^{n-k} + C.$$ Since $\frac{n!}{(n-k)!}$ is $P(n,k)$, the number of $k$-...
18
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 ...
18
votes
2answers
246 views

How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?

As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
18
votes
3answers
606 views

A sum of fractional parts.

I am looking to evaluate the sum $$\sum_{1\leq k\leq mn}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\} .$$ Using matlab, and experimenting around, it seems to be $\frac{(m-1)(n-1)}{4}$ when $...
18
votes
1answer
427 views

Special about 2015 with conjecture?

In the question Is there something special about 2015? Jack D'Aurizio found a nice result: $$\dfrac{1^2+2^2+\cdots +77^2}{77}=2015.$$ Then I was wondering: Is there a rectangular table $(7\times ...
18
votes
1answer
764 views

How to prove a double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! $$\sum_{m=s}^{2s}\sum_{k=0}^{...
18
votes
2answers
535 views

Maximizing curious symmetric function from simple combinatorics

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture). (This question has been posted at ...
18
votes
1answer
331 views

Count the number of bases in a subset

Consider $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the subset $\mathrm{S}^n = \{(x_1,\ldots,x_n) \in \mathbb{R}^n | x_i = 0 \; \mathrm{or} \; 1\;\forall i = 1,\ldots,n\}$. How many ...
18
votes
5answers
670 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 ...
18
votes
1answer
264 views

Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$

Consider the following iterative process. We start with a 2-element set $S_0=\{0,1\}$. At $n^{\text{th}}$ step $(n\ge1)$ we take all non-empty subsets of $S_{n-1}$, then for each subset compute the ...
18
votes
2answers
346 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
18
votes
1answer
2k views

Number of moves to solve a flood-it/sock-dye game

[ Question based on the sock dye game ] [ Update: It appears that this game is better known as "Flood it" and is NP-hard. Also, "the number of moves required to flood the whole board is $\Omega(n)$ ...
18
votes
1answer
446 views

Involutions, RSK and Young Tableaux

Let $S_n$ be the symmetric group on $n$ elements. The Robinson-Schensted-Knuth (RSK) correspondence sends a permutation $\pi\in S_n$ to a pair of Standard Young Tableaux $(P,Q)$ with equal shapes $\...
18
votes
1answer
307 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$ ...
17
votes
4answers
2k views

Have I found all the numbers less than 50,000 with exactly 11 divisors?

The math problem I am trying to solve is to find all positive integers that meet these two conditions: have exactly 11 divisors are less than 50,000 My starting point is a number with exactly 11 ...
17
votes
5answers
2k views

Probability of random integer's digits summing to 12

What is the probability that a random integer between 1 and 9999 will have digits that sum to 12? As a user suggested, I could make a spreadsheet and count them, but is there a quicker way to do this?...
17
votes
4answers
7k views

Why a complete graph has $\frac{n(n-1)}{2}$ edges?

I'm studying graphs in algorithm and complexity, (but I'm not very good at math) as in title: Why a complete graph has $\frac{n(n-1)}{2}$ edges? And how this is related with combinatorics?
17
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? ...
17
votes
1answer
950 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 ...
17
votes
4answers
406 views

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...
17
votes
5answers
2k views

Incredible Blackjack Hand

Last Saturday night I played at Bally's in Atlantic City and got a hand I could not believe. Dealer had 9 and I was dealt 2 8s. I split the 8s and was given a third card. It was an 8 so I split them ...
17
votes
3answers
473 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 ...
17
votes
2answers
2k 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 ...
17
votes
2answers
2k 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 ...
17
votes
4answers
830 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}, & \mbox{otherwise}.\...
17
votes
4answers
472 views

How many different numbers can be written if each used digit symbol is used at least 2 times?

How many different numbers can be written if each used digit symbol is used at least 2 times ? I would like to find the function $P(n,d)$: $P(n,d)$ where $n$ is base, $d$ is digit; Some examples: ...
17
votes
5answers
1k views

Lower bound in algorithmic puzzle

Puzzle: there are $n$ computers most of which are good; the others may be bad ("most" in the strict sense: there are strictly more good computers than bad ones). You may ask any computer $A$ about the ...
17
votes
3answers
8k 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 ...
17
votes
1answer
1k 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: ...
17
votes
4answers
587 views

$N$ perfect logicians wearing hats

I once came across the following riddle: (assume $N$ to be extremely large) There are $N$ perfect logicians arranged in a vertical row. They are allowed to strategize before the game, during the ...
17
votes
3answers
484 views

Prove an inequality on $l^2$ sequences over $F_2$

Denote $F_2$ the free non-abelian group on two letters $a, b$. Note that any element in $F_2$ is just a word formed by letters from the set $\{a,b,a^{-1},b^{-1}\}$, and the group structure is given ...
17
votes
1answer
2k 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 ...