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)

15
votes
1answer
556 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
206 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
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
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
3answers
2k 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 ...
15
votes
2answers
684 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
1answer
408 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
383 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
397 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
3answers
627 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
531 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
1answer
294 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
714 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
238 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 ...
15
votes
1answer
312 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
15
votes
2answers
1k views

any pattern here ? (revised 2)

for any positive number $k$, I have a $(k+1)*(k+1)$ matrix. I wonder if these matrices follow any "obvious" pattern. My goal is to guess the elements for matrix with $k=5$ and above (most probably in ...
14
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$ ...
14
votes
5answers
571 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 ...
14
votes
7answers
5k views

What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
14
votes
5answers
943 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 ...
14
votes
3answers
320 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 ...
14
votes
7answers
6k views

Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
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
162 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
473 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
274 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
1k 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
2answers
384 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
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 ...
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
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
2answers
9k 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 ...
14
votes
1answer
345 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
1answer
731 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 ...
14
votes
2answers
302 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 ...
14
votes
1answer
777 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 ...
14
votes
3answers
304 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
372 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
633 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
486 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
452 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
538 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 ...
14
votes
1answer
59 views

random walk on finite cyclic group

Suppose that I have a random walk on the finite cyclic group of order $d > 2$, where the initial probability distribution $Q$ assigns the values $p, q, r$ to $-1, 0, 1$, respectively, where $p + q ...
14
votes
0answers
529 views

$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$ Where: n,k are natural numbers and $k\le n$. t is taken over all ...
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
445 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
9answers
2k views

How many ways can seven people sit around a circular table?

How many ways seven people can sit around a circular table? For first, I thought it was $7!$ (the number of ways of sitting in seven chairs), but the answer is $(7-1)!$. I don't understand how ...
13
votes
6answers
576 views

Combinatorial identity with sum of binomial coefficients

How to attack this kinds of problem? I am hoping that there will some kind of shortcuts to calculate this. $$\sum_{k=0}^{38\,204\,629\,939\,869} ...
13
votes
7answers
3k views

Why is it important to study combinatorics?

I was having a discussion with my friend Sayan Mukherjee about why we need to study combinatorics which admittedly, is not our favourite subject because we see very less motivation for it(I am not ...