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)

14
votes
3answers
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 ...
1
vote
2answers
40 views

What is the probability of sinking ships in a simplified game of battleship?

Consider a a simplified game of battleship. We are given a 4x4 board on which we can place 2 pieces. One destroyer which is a 1 × 2 squares and a submarine that is 1 × 3 squares . The pieces are ...
2
votes
1answer
41 views

Powers of adjacency matrix doesn't seem to correspond to observed number of paths on graph

I would really appreciate some help on this! $A^n$ represents $n^{th}$ power of the adjacency matrix of a graph. I keep reading that the $A^n_{ij}$ entry equals "the number of paths of length n ...
3
votes
3answers
122 views

Examples of combinatorial/probabilistic proofs of theorems in linear algebra

Are there any examples of combinatorial/probabilistic proofs of theorems in linear algebra? Motivation: I see here, the inverse is true.
0
votes
1answer
33 views

Combinatorial techniques, methods, and ideas in (“undergraduate”) real analysis

This question is dual to Probabilistic techniques, methods, and ideas in ("undergraduate") real analysis: I would like to collect some examples of combinatorial arguments to undergraduate ...
3
votes
0answers
56 views

Probability of Posting a Quad and Trip on 4chan

Important Pre-Requisite Knowledge On the image board 4chan, every time you post your post gets a 9 digit post ID. An example of this post ID would be $586794945$. A Quad is a post ID which ends with ...
10
votes
0answers
177 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
1
vote
2answers
44 views

Binomial-coefficients if, k, m, n natural numbers and k \leq n the result of

If $k, m, n$, are natural numbers and $k \leq n$ What is: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
0
votes
1answer
40 views

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this :

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
7
votes
2answers
135 views

Solving a circular permutation problem with recursion

N people are invited to a dinner party, and they are sitting at a round table. Each person is sitting on a chair; there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
2
votes
1answer
29 views

What is a simple proof that something is np complete that does not use np completeness of something else?

What is a simple proof that something is NP complete that does not use NP completeness of something else? Every proof seems to reduce to something else being NP complete.
0
votes
2answers
38 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
12
votes
1answer
698 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 ...
3
votes
1answer
57 views

A combinatorial proof of Wilson's Theorem

I am looking for a combinatorial proof of Wilson's Theorem. Something along the lines of this kind of proof. $\textbf{Combinatorial proof of Fermat's Little Theorem}$ First consider a $p$ -tuple and ...
2
votes
3answers
1k views

Probability of having exactly 1 pair from drawing 5 cards

I have an exercise as follows: There is a collection of cards consisting of 52 cards (13 types and 4 colours each type). We draw 5 cards from the collection. Then what is the probability of having ...
11
votes
3answers
183 views

Prove the identity $ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$

$$ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$$ Class themes are: Generating functions and formal power series.
2
votes
1answer
41 views

Counting in other bases [duplicate]

While this could be considered opinionated to a certain degree, by setting the requirement as ease of use, is there a base that is better for performing simple math functions (+-×÷) than base ten. I ...
1
vote
0answers
52 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
0
votes
1answer
79 views

Prove if n<m there is at least one [(n/m)]?

Suppose there are n programmers in m cubicles. Prove that there must be at least one cubicle containing at least $\lceil \frac{n}{m} \rceil$ programmers. Note: I was not able to find the right sign [ ...
0
votes
3answers
51 views

Combinatorics Question (discrete math) [on hold]

In how many ways can one mark 6 blocks on a grid of 5 columns and 3 rows such that in every row at least one block will be marked? An explanation will be appreciated! Thanks a lot
1
vote
1answer
40 views

Proof regarding notations

I tried to solve the following question: Let $f,g$ be non-negative functions such that $f(n)=g(n)\left[1+o(1)\right]$. Prove that $f(n)=\Theta(g(n))$. I looked on two cases: ...
1
vote
2answers
28 views

Deciding $\displaystyle o,\omega,\Theta$ notations

I have a question which I couldn't solve for about two hours. It goes like this: Let $\displaystyle f(n)=\left(\frac{n+3\ln(n)}{n}\right)^n \ ; \ g(n)=27^{\ln(n)}$. Fill the blank box with ...
1
vote
1answer
23 views

Generalized Dyck words with alphabet of size $k$

It is known (e.g., here) that the Catalan number $C_n$ is the number of Dyck words of length $2n$, where a Dyck word is a string consisting of $n$ $X$'s and $n$ $Y$'s such that no initial segment of ...
2
votes
1answer
54 views

Maximization problem related to set of common representatives

We are given set $\{1, \dots n\}$ and requested to construct $A = \{A_1 \dots A_s\}$, where $|A_i|=k$, $|A| = s$, $A_i \subset \{1, \dots n\}$. We say that $S$ is a minimal set of common ...
6
votes
5answers
147 views

Calculate the binomial sum $ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i} $

I need any hint with calculating of the sum $$ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}. $$ Maple give the strange unsimplified result $$ I_n={\frac {1/12\,i\sqrt {3} \left( - \left( \left( ...
2
votes
2answers
40 views

If given $\sum_{r=1}^{m-1}\binom r3$, how does the summation evaluate when $n<r$ in $\binom nr$?

Correct me if I'm running the summation correctly - $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\sum_{r=2}^{m-1}\binom r3$$ $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\binom 23+\sum_{r=3}^{m-1}\binom r3$$ ...
0
votes
2answers
16 views

combinations which way way is correct?

The problem How many ways are there to select 5 persons: 2 men and 2 women from a group of 20 people: 12 men and 8 women. So far I've found 2 solutions: We select 3 men and 2 women or 2 men ...
0
votes
1answer
32 views

Miklos Schweitzer 2014 - sum of reciprocal of lengths of intervals

We let there be $k$ intervals within $[0,1]$. Prove that the sum of the reciprocals of the lengths of the intervals plus twice the sum of the reciprocals of the lengths of the nonempty intersection of ...
-2
votes
0answers
24 views

circles and points on a grid [on hold]

An infinite number of points are marked on the coordinate grid such that there is no circle that passes by 1000 of them. Is there necessarily a circle of radius 20 that does not contain any of those ...
1
vote
1answer
28 views

Find a probability of $n$ event happening from $m$ types

The question is: to find a sum $$ S=\sum\limits_{n_1+n_2+\ldots+n_m = n,\ n_i=0,1,\ldots,n} p_1^{n_1}p_2^{n_2}\cdots p_m^{n_m}, $$ where $p_i\in[0,1]$. UPDATE. This issue has no probabalistic ...
17
votes
1answer
190 views
+50

An example where $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is the number of ways of counting something?

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. There is a answer given here to this question here. I've seen how it can be proven using recurrence ...
1
vote
1answer
41 views

Expected number of matching “cards”. Why is $\sum_{m=0}^n D_{n,m} = \sum_{m=0}^n m \cdot D_{n,m}$?

Each of n ≥ 2 people puts his or her name on a slip of paper (no two have the same name). The slips of paper are shuffled in a hat, and then each person draws one (uni- formly at random at each ...
4
votes
2answers
29 views

Number of teams and matches

This question has two parts. Given n players, how many different teams can be created with at least one and at most n-1 players? For example, given the four players A, B, C, and D, the following ...
2
votes
1answer
47 views

Calculating sum of all permutations

Given a number n. If we generate all the permutation from 1 to n, for a permutation $P_i, F(P_i)$ is defined as $\sum(|P_i - i|)$ for i = 1 to n. So if n = 3, for the permutation 1 3 2 F = |1-1| + ...
2
votes
1answer
30 views

Combinatorics calc

I'm trying to make an application that's based on bets system. Until now i was able to calc the number of combination of the inserted events, in particular, i've used this formula: ...
0
votes
1answer
44 views

Prove that a preorder is not anti symmetric

Let $\prec$ be a relation on the set $ A = Z \times (N \setminus \{0\}) $ in this way: A. $<a,b> \prec <c,d> $ if $ ad \le bc$ Prove that $\prec$ is a Preorder and show it's not ...
0
votes
1answer
37 views

What happens from $\displaystyle (1+(x+x^2))^n$ to $\displaystyle \sum_k {n \choose k} (x+x^2)^n$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. I don't understand what happens from $\displaystyle \bbox[1px,border:1px solid black]{(1+(x+x^2))^n} $ to $\displaystyle ...
1
vote
1answer
29 views

Count and description of vertices of certain faces of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$

For $k \ge 1$, $d \ge 2$ and $k \le d - 1$, let ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ be the intersection of $k - 1$ facets of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$ with equations: ...
6
votes
0answers
57 views

Game to maintain distinct number of balls in glasses

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some ...
3
votes
1answer
47 views

Minimum number of bags to buy to allocate equally

It is from a programming contest but I feel it pertains more to the mathematics realm ( I once asked it in stackoverflow but they closed the problem saying I should go here ) The problem goes like ...
2
votes
1answer
34 views

Adjacent dominos in a train

Definition of a domino -- a domino contains two squares separated by a line. In both of the squares, there are some numbers of dots (can be 0). Definition of "double-n" domino set: It contains one of ...
1
vote
1answer
65 views

Proof of the fact that the set of (p,q) shuffles is a cross section of the subgroup $S_p\times S_q$

Definition Let $G$ be a group and $H$ its subgroup. We name a subset $K$ of $G$ a cross section if it has exactly one element from each left coset of $G/H$. Definition Let $n=p+q$ for some ...
8
votes
2answers
261 views

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? ...
17
votes
1answer
216 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 ...
1
vote
2answers
26 views

Permutation/Combination question on dice

Question: Three dice (six faces: each face -> number 1 to 6) are rolled. What is the number of possible outcomes such that at least one die shows number 2? My attempt: One die has to show two. ...
2
votes
2answers
33 views

Number of Terms in a Polynomial (4th Degree)

Find the number of terms of $(x^3+5x^2-x+2)^4$, when like terms are added. My approach to this uses stars and bars to get $****|||$, since there are $4$ groups. $\binom{7}{3} = ...
5
votes
2answers
43 views

Distributing candies

Suppose ther are B boys and G girls in a classroom.Teacher wants to distribute candies among B boys and G girls such that: 1.Each student gets atleast one candy and atmost N candies. 2.sum of ...
2
votes
1answer
36 views

Set of common representatives and pigeonhole principle in one problem

We are given set $\{1, \dots n\}$ and $A = \{A_1 \dots A_s\}$ such as $|A_i|=k$, $|A| = s = \binom n k$, namely $A$ contists of all possible subsets of size $k$. We say that $S$ is a set of common ...
0
votes
2answers
29 views

Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain at most one element from each $S_i$ is $(a_1 + 1)(a_2 + 1) \dots (a_t + 1)$.

I found this problems on Aigner's: A course in enumeration: 1.1 We are given $t$ disjoint sets $S_i$ with $|Si| = a_i$. Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain ...
2
votes
2answers
34 views

Probability in dice, Feller exercise

I am stuck with exercise 2 of Chapter 4 Feller vol 1 "an introduction to probability theory and its application". Here I report the exercise text: Five dice are thrown. Find the probability that at ...