Questions tagged [combinatorial-proofs]

Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc. They avoid complicated algebraic manipulations.

Filter by
Sorted by
Tagged with
2 votes
2 answers
55 views

Correctness of Solution for Forming a Committee with More Democrats than Republicans

I recently encountered a problem and derived a solution, but I am uncertain about its correctness. Here's the problem: At a congressional hearing, there are 2n members present. Exactly n of them are ...
AzharKhan's user avatar
0 votes
0 answers
12 views

proofs of combinatoric summation series [duplicate]

I need to verify some results from Wolfram Alpha, either by citing references where these results are stated, or via proof. I found a reference for one that I need in Boros & Moll 2004: $\sum_{d=0}...
Saf_AU's user avatar
  • 1
2 votes
0 answers
41 views

Number of all possible arrangements such that no two objects of same kind are together

There are $k_1+k_2+k_3+...+k_n$ objects of which $k_1$ are of first kind, $k_2$ are of second kind, $k_3$ are of third kind, ..., $k_n$ are of $n^{th}$ kind. Calculate the number of all possible ...
Sparsh Gupta's user avatar
0 votes
2 answers
145 views

Emma plays a game with rocks

Emma is playing a game. She has to place rocks on a $3\times3$ square board such that rocks are placed on non-adjacent squares (squares that are not directly above, below, left, or right of another ...
math.enthusiast9's user avatar
0 votes
0 answers
14 views

Combinatorial proof of $\sum_{k=1}^n k \binom{n}{k}=n 2^{n-1}$ [duplicate]

I am trying to find a combinatorial proof of the following identity $\sum_{k=1}^n k \binom{n}{k}=n 2^{n-1}$. Let $S$ be a set with $n$ elements. The idea would be to find two different ways to count ...
NTc5's user avatar
  • 35
2 votes
0 answers
48 views

Application of the Principle of Inclusion/Exclusion and the Binomial Theorem in Combinatorial Proofs [closed]

Consider a set $Z=X \cup Y$, where $X=\left\{x_1, \ldots, x_n\right\}$ is a set of blue elements and $Y=$ $\left\{y_1, \ldots, y_m\right\}$ is a set of red elements. (a) How many subsets of $Z$ ...
Allison's user avatar
  • 185
-4 votes
1 answer
106 views

Problem with kids playing a game on a grid with lattice points [closed]

A group of 252 kids play a game. They draw a grid on the ground consisting of lattice points and have to get from point $(0,0)$ to $(5,5)$ (the kids can only take unit length steps up or to the right)....
math.enthusiast9's user avatar
2 votes
0 answers
27 views

a grid problem in which it is necessary to show that there are some columns that satisfy the requirement

Let n > 3 be a positive integer and a 50 × n grid (50 rows and n columns). People fill in the numbers 1 and −1 unit squares of the table (each cell contains exactly 1 number) so that the sum of the ...
bestty's user avatar
  • 107
1 vote
2 answers
71 views

Nested sum of product of binomial numbers

I am currently working on an automata theory concerning a special case of nondeterministic automata. I am studying the state complexity of converting this automaton to a classical deterministic one (...
simon huraj's user avatar
-1 votes
0 answers
10 views

To find the conditions under which a word X can be constructed such that XX has a connection without intersecting lines. X, 1 to n random repeat twice

Given the numbers from 1 to n, we want to construct a word $X$. In this word, each number will randomly repeat twice. Now, we need to repeat this word once to form our final word $XX$. We can arrange ...
邓青英's user avatar
1 vote
1 answer
57 views

Existence of Identically-2-colored Equidistant Points on the Integers

I was wondering if every 2-coloring of the integer set would result in some number of equidistant (equally-spaced) points. I proved that there will always be 3 equally-spaced points of the same color, ...
mathy_mathema's user avatar
3 votes
0 answers
377 views

Determine the general term of the sequence $(a_n)_{n\ge1}$, strictly decreasing

Determine the general term of the sequence $(a_n)_{n\ge1}$, strictly decreasing, of strictly positive numbers, which satisfies the properties: a) $na_n \in \mathbb{N} \setminus \{0\}$ for every $n \in ...
math.enthusiast9's user avatar
15 votes
1 answer
305 views

Combinatorial proof, without axiom of choice, that for any set $A$, there is no surjection from $A^2$ to $3^A$

The well known proof of Cantor's theorem (stating that $A<2^A$ for any set $A$) does not make any use of the axiom of choice. I have now spent some time wondering if the analogous result $A^2<3^...
Tim Seifert's user avatar
  • 1,459
2 votes
2 answers
86 views

Find the number of functions $f : \{ 1,2,...,n \} \rightarrow \{p_1,p_2,p_3 \} $ for which the number $f(1)f(2)...f(n)$ is a perfect square.

Let $p_1,p_2,p_3$ be distinct prime numbers and consider $n \in \mathbb N$ . Find the number of functions $f : \{ 1,2,...,n \} \rightarrow \{p_1,p_2,p_3 \} $ for which the number $f(1)f(2)...f(n)$ is ...
Unknowduck's user avatar
0 votes
0 answers
37 views

Counting Subsets: Variable Sizes with Inclusion Constraint [duplicate]

If sets $A$ and $B$ are subsets of the set $\{1, 2, \ldots, n\}$, with $|A| = k$ and $|B| = m$, where $k \leq m$, the task is to determine the total number of pairs $(A, B)$ where $A \subseteq B \...
math.enthusiast9's user avatar
1 vote
2 answers
50 views

Bijection between permutations of even length cycles and pairs of factors

I was trying to solve Exercise 3.13.15 in Cameron's Combinatorics: Topics, Techniques, Algorithms. It goes like this: (a) Let $n = 2k$ be even, and $X$ a set of $n$ elements. Define a factor to be a ...
user246336's user avatar
  • 3,579
1 vote
1 answer
99 views

Combinatoric identity

I'm trying to get a combinatorial proof of the following identity by making up some story. $$\sum_{k=1}^n {k \choose j}k = {n+1 \choose j+1}n - {n+1 \choose j+2}$$ I can do it, by simplifying the ...
Barabara's user avatar
  • 682
0 votes
0 answers
20 views

Computing maximum of a ratio defined on the grid graph

Consider an $n \times n$ grid graph $G$. Define the following quantity \begin{equation} m(G) = \text{max}\bigg\{\frac{|E|_{H'}}{|V|_{H'}},~ H' \subseteq G, ~~|V|_{H'} > 0 \bigg\}, \end{equation} ...
RandomMatrices's user avatar
0 votes
0 answers
54 views

Is my logic correct? A bit string of n with more 0s than 1s

I am learning about combinatorial and bit strings. I decided to use combinatorial reasoning and wanted to see if my logic made sense. The question: How many bit strings of length n contain more 0’s ...
coolcat's user avatar
  • 51
0 votes
0 answers
22 views

How many bit strings of length n contain more 0’s than 1’s? [duplicate]

To solve this, I think we need to use combinatorial reasoning.= Consider a bit string of length ( n ). There are ( 2^n ) possible bit strings of this length because each bit can independently be ...
coolcat's user avatar
  • 51
3 votes
0 answers
58 views

Prove combinatoric equation: $\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$

Prove the equation: $$\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$$ My solution: We have $n+1$ players numbered from $1$ to $n+1$. We want to play a team game that ...
thefool's user avatar
  • 1,379
0 votes
0 answers
37 views

find number of disjoint subsets

For my discrete maths course i did the following exercise: Let M be a finite set with n elements, find $|\{(U,V)|U,V\subseteq M , U \not = V,U\cap V= \emptyset \}|$ I did it the following way: choose ...
macman's user avatar
  • 41
8 votes
1 answer
172 views

Simplifying a binomial sum for bridge deals with specific voids

While trying to get an expression for the number of deals from a generalised bridge deck with nobody being void in any suit I encountered the following subproblem. From a generalised bridge deck with $...
Parcly Taxel's user avatar
3 votes
2 answers
82 views

Combinatorial Proof of $p \mid {p \choose k}$

I found an 11 year old proof of the statement “if $p$ is prime and $ 0 < k < p$ then $p \mid {p \choose k}$” by Joriki here. It is as follows: If you count the number of k-element subsets of a ...
Robert Murray's user avatar
2 votes
1 answer
45 views

Equivalence of two ways to solve this combinatorics problem, and how to prove the resulting equality [duplicate]

This question arises from the following problem: We define the set $N=\{1,2,...,n\}$. How many different possibilities are there to form three sets $A$, $B$ and $C$ such that $A\subseteq B\subseteq C\...
Wild Feather's user avatar
0 votes
3 answers
86 views

Evaluate using combinatorial argument or otherwise :$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$

Evaluate using combinatorial argument or otherwise $$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$$ My Attempt By plugging in values of $i=0,1,2,3$ I could observe that ...
Maverick's user avatar
  • 9,220
2 votes
2 answers
71 views

The number of relations over a set

I need to calculate the number of relations over $A$, when the size of $A$ is $n$, and want to understand why my approach is not correct. I denoted $A_i$ as subset of $A$, and I said general relation ...
miiky123's user avatar
  • 217
0 votes
1 answer
51 views

On the probleme des menages solution on Titu Andreescu book

The probleme des menages consists of the following: How many ways can $n$ married couples si at a round table in such a way that there is one man between every two women and no man is seated next to ...
H4z3's user avatar
  • 603
0 votes
1 answer
102 views

Story proofs in Combinatorics/Probability [closed]

I have been recently been going through Blitzstein in an attempt to put my probability on a stronger foundation then it currently is. There is a large emphasis on the use of "story" proofs/...
Starlight's user avatar
  • 1,680
2 votes
1 answer
91 views

Prove that there are $n! - (n-1)(n-1)!$ ways to arrange $n$ objects in a circular arrangement.

Prove that there are $n! - (n-1)(n-1)!$ ways to arrange $n$ objects in a circular arrangement. I have tried algebraic proofs by equating it to $\frac{n!}{n}$ and to $(n-1)!$ but can't think of a way ...
dingus's user avatar
  • 49
0 votes
1 answer
49 views

Rewriting a sum over permutations

Suppose I have the set $I_{n} = \{1,...,n\}$ and $n$ formal objects $x_{1},...,x_{n}$ (you can think of these as elements of some algebra). Let me write: $$S(x_{1}\cdots x_{n}) = \frac{1}{n!}\sum_{\...
InMathweTrust's user avatar
0 votes
0 answers
85 views

Tic-tac-toe possible grids

Let's consider the tic-tac-toe game, with two players and a natural number n of rows and columns (X starts; the winning player is the first who fills up a row, a column, the diagonal or the ...
Amanda Wealth's user avatar
0 votes
0 answers
38 views

Seeking combinatorial proof for an Identity involving $2^{2n}$ and a sum of binomial coefficients [duplicate]

The following identity can be proved us generating functions and Newton's Binomial Theorem \begin{equation*} 2^{2n} = \sum_{k = 0}^{n} \binom{2k}{k} \binom{2n-2k}{n-k}, \qquad \...
NonalcoholicBeer's user avatar
2 votes
1 answer
140 views

Probability of ballot ending in a tie

I am fairly sure this is a studied problem, but I am no expert. We have a ballot with $k$ candidates and $n \geq k$ paritcipants, each participant voting once, each candidate having equal strength, so ...
Mr_3_7's user avatar
  • 321
1 vote
0 answers
56 views

Linear independence of binary vectors

I lately encountered the following problem, which I conjecture to be true, but have been unable to either give a proof or raise a counterexample. Let $A$ be a $m \times n$ binary matrix ($m \ge 2n, n \...
HenryYRZ's user avatar
3 votes
1 answer
257 views

Game of cards and divisors

Ana thinks about some different non-zero natural numbers, and for each of them, she writes on a card every positive divisor. Then, Ana hands all the cards to Maria, who groups them based on the number ...
math.enthusiast9's user avatar
4 votes
1 answer
59 views

Triangulation in Monsky's Theorem

In the proof of Monsky's Theorem, which states that it is not possible to dissect a square into an odd number of triangles of equal area, it is common to use a triangulation of a unit square. The ...
Cleto Pereira's user avatar
2 votes
4 answers
130 views

Is there a simpler proof for the following identity: $\sum_{n=0}^x \frac{(n+x)!}{n!2^n} = x!2^x$

The proof I have constructed for this first proves that $\sum_{n=0}^\infty \frac{(n+x)!}{n!2^n} = 2(x!2^x)$ using what I believe is combinatorial geometry, then proves that the identity above is half ...
LogicCube's user avatar
2 votes
3 answers
134 views

Combinatorial proof of $ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}. $ [duplicate]

I'm trying to understand the combinatorial identity $ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}. $ I have a good understanding of the algebraic manipulation involved, but I'm struggling with the ...
Alexis SM's user avatar
1 vote
0 answers
38 views

Connecting generating functions for binomial and negative binomial distributions

The generating function for the binomial distribution can be expressed as: $((1-p)+p)^r=\sum\limits_{k\ge 0} \binom{r}{k}(1-p)^k p^{r-k}$ $=\sum\limits_{k\ge 0} \text{ probability of $k$ failures when ...
Terence C's user avatar
  • 303
1 vote
2 answers
113 views

Number of permutations such that each number is either greater than all the numbers to its left or less than all the numbers to its right.

I've been stuck on the following problem which I've been trying to do recursively. Let n be a positive integer. Consider all permutations of $\{1, 2, \dots , n \}$. Let $A_n$ denote the set of those ...
H4z3's user avatar
  • 603
0 votes
1 answer
48 views

Find how many n-digit positive integers using the digits 1, 2, and 3, such that no two 1's are next to each other.

I found this problem in section $5$ of "A path to combinatorics for undergraduates" from Titu Andreescu, but I don't know what's wrong with my solution. First I defined $A_n$ to be the set ...
H4z3's user avatar
  • 603
1 vote
1 answer
76 views

How to prove that the following conclusion is true? [closed]

Consider a set $\mathcal{X}$ with $m$ numbers, and take out $a, b, c, d$ numbers respectively. The number of combinations of $a$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{a}$. The number ...
Kristy's user avatar
  • 21
1 vote
1 answer
129 views

Enumerating $m\times n$ binary matrices with constant column sum and at least one non-zero row entry

I have worked out the following, and would appreciate if anyone can verify or suggest improvements. If the columns should sum up to $k$, then there are $\binom{m}{k}^n$ $m\times n$-matrices with a ...
sehsan's user avatar
  • 11
2 votes
1 answer
64 views

Number of paths of length $k$ on Complete Graph with $\ell$ repeated edges

Consider $K_n$, which is the complete graph on $n$ vertices (every edge is present). I want to count the number of paths of length $k$ that start from vertex $1$ to vertex $2$, where repeated edges ...
Alan Chung's user avatar
  • 1,182
0 votes
2 answers
2k views

What is the total number of ways to distribute $20$ oranges to $3$ students such that each gets at least $1$ orange?

Here's the question: What is the total number of ways to distribute $20$ oranges to $3$ students such that each gets at least $1$ orange? (I come to fact that each orange is distinct or not at the ...
Maddy's user avatar
  • 43
2 votes
2 answers
68 views

Evaluate Sum of Products in The Form of $\sum_{\left\|\mathbf{x}\right\|=C}\prod_{i=0}^{n}\left(2+i\right)^{x_{i}}$

Background I recently came across the problem to prove the following: $$ \sum_{\left\|\mathbf{x}\right\|_{1}=m-1}2^{x_{1}}3^{x_{2}} = 3^{m}-2^{m}, \phantom{x} \mathbf{x}\in\mathbb{N}_{0}^{2} $$ A ...
acat3's user avatar
  • 11.9k
0 votes
0 answers
17 views

Seeking Formalization or Verification of an Inequality Involving Sums and Products

Body: Hello everyone, I've been working on an inequality involving sums and products over certain functions and indices, and I've come up with a proof sketch. However, I'm not entirely sure about its ...
Martin Geller's user avatar
0 votes
0 answers
120 views

Counting argument for an alternating sum identity $\sum_{b=0}^{\binom{a}{c}}(-1)^{b+1}f(a,b,c)=(-1)^{a+c}\binom{a-1}{c-1}$

Let $f(a,b,c)$ be the number of ways of writing a set of size $a$ as a union of $b$ distinct subsets of size $c$. I've noticed that $$\sum_{b=0}^{\binom{a}{c}}(-1)^{b+1}f(a,b,c)=(-1)^{a+c}\binom{a-1}{...
Jacob's user avatar
  • 2,407
-4 votes
1 answer
67 views

How many six-digit numbers are divisible by at least one of the numbers 24, 18? How many of them are divisible by exactly one of them? [closed]

I wrote a code that counts the number of these numbers and found out that the answer to the first question is 75000 and the answer to the second question is 62500. I also realised that I need to use ...
Dima Stadnik's user avatar

1
2 3 4 5
25