# Tagged Questions

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.

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
1k views

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$ ...
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 ...
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?...
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?
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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}.\...
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: ...
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 ...
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 ...
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: ...
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 ...
### 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 ...
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 ...