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)

13
votes
4answers
623 views

How this operation is called?

This operation is similar to discrete convolution and cross-correlation, but has binomial coefficients: $$f(n)\star g(n)=\sum_{k=0}^n \binom{n}{k}f(n-k)g(k) $$ Particularly, $$a^n\star ...
13
votes
3answers
679 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 ...
13
votes
4answers
480 views

Intriguing polynomials coming from a combinatorial physics problem

For real $0<q<1$, integer $n >0 $ and integer $k\ge 0$, define $$[k, n]_q \equiv -\sum_{m=1}^{n} q^{m(k+1)} (q^{-n}; q)_m = -\sum_{m=1}^{n} q^{m(k+1)} \prod_{l=0}^{m-1} (1-q^{l-n})$$ ...
13
votes
3answers
431 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 ...
13
votes
3answers
231 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 ...
13
votes
2answers
316 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 ...
13
votes
2answers
338 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 ...
13
votes
5answers
467 views

Number of ways to divide a stick of integer length $N$

Suppose we have a stick of integer length $N$. I'm looking for (preferably closed-form) formula that gives the numbers of ways in which we can divide the stick into 3 parts with distinct integral ...
13
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 ...
13
votes
2answers
1k 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, ...
13
votes
2answers
205 views

Evaluate the determinant $\det\left[ \binom{2n}{n+i-j} \right]_{i,j=0}^{n-1}$

I am trying to show that: \begin{equation} \det\left[ \binom{2n}{n+i-j} \right]_{i,j=0}^{n-1}=\prod_{i=0}^{n-1} \frac{\binom{2n+i}{n}}{\binom{n+i}{n}} \end{equation} I have tried playing with the ...
13
votes
2answers
264 views

Combinatorial interpretation of this identity of Gauss?

Gauss came up with some bizarre identities, namely $$ \sum_{n\in\mathbb{Z}}(-1)^nq^{n^2}=\prod_{k\geq 1}\frac{1-q^k}{1+q^k}. $$ How can this be interpreted combinatorially? It strikes me as being ...
13
votes
4answers
727 views

Coloring the faces of a hypercube

I will restate the 3-D version of the problem. In how many ways can you color a regular cube with 2 colors up to a rotational isometry. The answer is of course a special case of Burnsides Lemma which ...
13
votes
3answers
663 views

Exceptional books on real world applications of graph theory.

What are some exceptional graph theory books geared explicitly towards real-world applications? I would be interested in both general books on the subject (essentially surveys of applied graph ...
13
votes
1answer
631 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 ...
13
votes
3answers
3k views

How to rotate n individuals at a dinner party so that every guest meets every other guests

I'm throwing an event where every individual is suppose to meet every other individual so I'm trying figure out how to rotate them. My friends say its easy but they have yet to come up with an answer ...
13
votes
2answers
436 views

Signed Multinomial Expansion Coefficients?

I've been spending probably an undue amount of time trying to compute the coefficients of polynomials of the form $p_n(x_1, ..., x_n) = \displaystyle\prod_{\sigma \in \{ -1 , 1 \}^{n-1} } (x_1 + ...
13
votes
3answers
415 views

Probability of a winning consecutive $k$-subset out of $n$ coin flips

Assume we flip a coin $n$ times. A $k$-sequence is defined as any consecutive sequence of coin flips of length $k$. Call a $k$-sequence "winning" if there are strictly more heads than tails. What is ...
13
votes
1answer
303 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 ...
13
votes
1answer
304 views

Enumerative Combinatorics

Sam has $255$ cakes, each labeled with a unique non-empty subset of $\{1, 2, 3, 4, 5, 6, 7, 8\}$. Each day, he chooses one cake uniformly at random out of the cakes not yet eaten. Then, he eats that ...
13
votes
3answers
943 views

Proving $k \binom{n}{k} = n \binom{n-1}{k-1}$

Suppose we want to prove $$ k \binom{n}{k} = n \binom{n-1}{k-1}$$ In the LHS we are choosing a team of $k$ players from $n$ players. Then we are choosing a captain. In the RHS we are choosing a ...
13
votes
2answers
677 views

The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go . . . ] Here's my description of the game: There's a $4\times 4$ grid with some random, numbered cards on. The numbers are either one, two, or multiples of three. ...
12
votes
8answers
2k views

Calculating the number of possible paths through some squares

I'm prepping for the GRE. Would appreciate if someone could explain the right way to solve this problem. It seems simple to me but the site where I found this problem says I'm wrong but doesn't ...
12
votes
4answers
1k views

Simple combinatorics question - caught off guard!

Prove that ${{2n}\choose{n}}$ is even for $n \in \mathbb{N}$. This one caught me off-guard when answering (or attempting to answer!) this for a student today. I tried this approach: ...
12
votes
7answers
476 views

Prove that $2^n < \binom{2n}{n} < 2^{2n}$

Prove that $2^n < \binom{2n}{n} < 2^{2n}$. This is proven easily enough by splitting it up into two parts and then proving each part by induction. First part: $2^n < \binom{2n}{n}$. The ...
12
votes
4answers
421 views

Partitioning the naturals into an infinite number of large sets

Is it possible to partition the positive integers into an infinite number of disjoint large sets ?
12
votes
6answers
798 views

Proving a binomial sum identity

Mathematica tells me that $$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$ Although I have not been able to come up with a proof. Proofs, hints, or references are all ...
12
votes
4answers
9k views

How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other?

I have a homework problem in my textbook that has stumped me so far. There is a similar one to it that has not been assigned and has an answer in the back of the textbook. It reads: How many ways ...
12
votes
2answers
441 views

If 1 boy knows r girls and 1 girl knows r boys ,then number of boys=girls

Yet another question from BdMO 2013 Nationals: In a class,every boy knows $r$ number of girls and every girl knows $r$ number of boys.Show that there are equal number of boys and girls[Assume that ...
12
votes
3answers
476 views

How to get ${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$

I found this in my test book, any hints? Given $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$$ Then find the value of x and y in n. According to the answer ...
12
votes
2answers
760 views

Color an $n\times n$ square with $n$ colors

How many ways is there to color an $n\times n$ square grid with $n$ colors such that each column and each row contains exactly one $1\times 1$ square of each color? And how many ways if the same is ...
12
votes
3answers
545 views

Best Strategy for a die game

You are allowed to roll a die up to six times. Anytime you stop, you get the dollar amount of the face value of your last roll. Question: What is the best strategy? According to my calculation, for ...
12
votes
1answer
348 views

Squarefree polynomials over finite fields

I'm trying to figure out how many squarefree polynomials there are of a fixed degree over $\mathbb{F}_2$ specifically (and in general, over any finite field). Looking at some low-degree examples seems ...
12
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 ...
12
votes
2answers
393 views

Expected value of maximum consecutive distance in a uniformly random permutation

How does one compute $\mathbb{E}[\max_{1\le i < n} |\sigma(i) - \sigma(i+1)|]$ where the expectation is taken over a uniformly random permutation $\sigma \in \mathbb{P}_n$, the set of all ...
12
votes
2answers
231 views

Distinctness is maintained after adding some element to all sets

Let $S=\{S_1,S_2,\ldots,S_n\}$ be a set of $n$ distinct subsets with $S_i \subseteq \{1,\ldots,n\}$ for $i=1,\ldots, n$ then $k \in \{1,\ldots,n\}$ exists with $S_i \cup \{k\}$ is distinct for ...
12
votes
4answers
419 views

Showing that $Q_n=D_n+D_{n-1}$

Let $T_n$ be the set of permutations of $\{1,\cdots,n\}$ which do not have i immediately followed by i+1 for $1\le i\le n-1$, so $T_n=\{\sigma \in S_n: \sigma(i)+1\ne\sigma(i+1)$ for $1\le i\le ...
12
votes
2answers
423 views

board game: 10 by 10 light bulbs, minimum switches to get all off?

Hy all! My problem is as follows: There's a board of 10 by 10 light bulbs. (So it's a square with 10 columns and 10 rows.) Every single bulb has got its own switch. However, something went wrong and ...
12
votes
3answers
272 views

Select a new value from last $N$ values; how long until the last $N$ are all the same?

Say first we have N distinct numbers in a line, like 1,2,3,...,N, in each round, we choose a ...
12
votes
4answers
360 views

Counting (Number theory / Factors)

I'm stuck with this counting problem: I have an expression: $T = (N!) \times (N!) / D$ where, $D \in [1 - N!]$, i.e. $D$ takes all values from $1$ to $N!$ and I'm to count the number of points where ...
12
votes
2answers
373 views

Proving the existence of a weakly increasing subsequence of length $n$

Let for all integers $i=1,2,\ldots,2^{n-1}$be given integers $f(i)$ such that $$1\le f(i)\le i.$$ Can one show that there exist $a_{1},a_{2},\ldots,a_{n}$ such ...
12
votes
2answers
223 views

Given $n$ points on the plane, find a circle which contains only three

Given $n$ points on $\mathbb{R}^{2}$, s.t no three are on the same straight line, and not all the points are on the same circle, prove that there exists a circle which contains only three of those ...
12
votes
2answers
327 views

Show $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ by block-walking interpretation of Pascal's triangle

A combinatorial proof for the identity $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$ is the following "committee" argument, which seems the most common. There are $\binom{n}{k}$ ...
12
votes
1answer
414 views

What does the minimal eigenvalue of a graph say about the graph's connectivity?

I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this ...
12
votes
2answers
307 views

A card game with no decisions

A friend showed me a mindless card game he plays, in which the initial state of the deck completely determines whether he wins or loses. The game is played as follows: Shuffle a standard $52$ card ...
12
votes
2answers
1k views

Minimum number of moves to reach a cell in a chessboard by a knight

Given an infinite chessboard represented as a 2D Cartesian plane. A knight is placed at the origin. What is the minimum number of moves it needs to reach a cell $(m,n)$? (Without loss of generality, ...
12
votes
1answer
249 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 ...
12
votes
1answer
318 views

Words that agree on the count of all subwords of length $\leq k$

I'm working with a two letter alphabet $\{0,1\}$, and I'm talking about generalized sub-word i.e. letters don't need to be adjacent, $|01010|_{00} = 3$ For example, the two words $u=1001$ and ...
12
votes
3answers
179 views

Prove $1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3}$

Prove that: $$ 1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3} $$ Now, if I simplify the right hand combinatorial expression, it reduces to $\frac{n(n+1)(2n+1)}{6}$ which is well known and can be ...
12
votes
1answer
654 views

Counting subsets with r mod 5 elements

Some time ago Qiaochu Yuan asked about counting subsets of a set whose number of elements is divisible by 3 (or 4). The story becomes even more interesting if one asks about number of subsets of ...