Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially 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.
57,810
questions
0
votes
0
answers
20
views
Prove that the general formula for a sequence $a_n$ is $\frac{(-1)^n}{n!}$
Here is a sequence $a_n$ where the first five $a_n$ are:
$a_1=-\frac{1}{1!}$
$a_2=-\frac{1}{2!}+\frac{1}{1!\times1!}$
$a_3=-\frac{1}{3!}+\frac{2}{2!\times1!}-\frac{1}{1!\times1!\times1!}$
$a_4=-\frac{...
0
votes
1
answer
24
views
Ordering problem / Probabilities and Statistics
Question Source
Four types of molecules are labeled A, B, C and D. If these four molecules form a chain how many distinct chains are there? For this question you may assume that is matters which ...
- 1
0
votes
0
answers
9
views
Equivalent Card Combinations for n-Cards
I'm hoping to develop a formulaic approach to answering a problem to do with dealing card games. I will be using the output of this formula as a checksum against an algorithm that I made. Thanks in ...
- 1
1
vote
1
answer
25
views
Maximal counterexample for a greedy approach with a non-canonical coin system
Let $1 = c_1 < c_2 < \dots < c_n$ be an integer coin system. This coin system is not necessarily canonical (that is, a greedy algorithm will not necessarily yield the fewest number of coins ...
1
vote
0
answers
47
views
Set Problem:find the minimum number of d
$\Omega =\left \{1,2,3\dots,n\right\}$,$(k<n)$,$\Gamma$ is the set of the k-subsets of $\Omega$. Let us fix d partitions $(G^{(i)})_{1,2\dots,d}$ of $\Omega$ where each $(G^{(i)}$ is a partition in ...
- 11
-4
votes
0
answers
16
views
Exploring Ramsey Theory in Grahps
In the context of Ramsey theory, let R(m,n) denote the minimum number of vertices N for which graph with N vertices is guaranteed to contain either a clique of size m or an independent set of size n.
...
- 1
0
votes
0
answers
67
views
How many times can a digit appear in the page numbers of a book containing $n$ pages?
For example: we have a book that contains 64 pages, we want to know how many times the digit 6 appears in the page numbers of the the book. The qualifying page numbers are {6,16,26,36,46,56,60,61,62,...
- 11
1
vote
0
answers
30
views
Exploring the Relationship Between Stirling Numbers of the Second Kind and Bell Numbers
Stirling Numbers of the Second Kind $S(n, k)$ represent the number of ways to partition a set of $n$ objects into $k$ non-empty subsets, while Bell Numbers $B(n)$ count the number of ways to partition ...
- 634
2
votes
0
answers
69
views
Regarding number of non negative solutions to $\sum a_i\cdot x_i = n$.
Similar questions have been asked before and from there I have learn that the number of solutions to the equation
$$\sum_i a_i\cdot x_i = n \ \ \ \ \ x_i \in Z_{\geq 0}$$
is the coefficient of $y^n$ ...
- 1,130
0
votes
0
answers
34
views
Simple double counting in a circular permutation problem
Question: In how many ways are there to arrange 6 boys and 8 girls (each of them are unique) on a round table ?
Clearly the answer is $13!$ by circular permutation.
But here’s another argument that I ...
- 55
4
votes
2
answers
80
views
Show $\sum_{i=0}^n{i\frac{{n \choose i}i!n(2n-1-i)!}{(2n)!}}=\frac{n}{n+1}$
How can this identity be proved?
$$\sum_{i=0}^n{i\frac{{n \choose i}i!n(2n-1-i)!}{(2n)!}}=\frac{n}{n+1}$$
I encountered this summation in a probability problem, which I was able to solve using ...
- 115
1
vote
1
answer
72
views
Number of dinners
How many dinners consist of 2 optional appetisers, 3 main courses and 4 optional beverages?
My result is $2\cdot 3\cdot4 + 2\cdot3 + 3\cdot4 + 3 = 45$. Where the first product $2\cdot3\cdot4$ ...
- 519
1
vote
0
answers
24
views
Finding the maximal graphs to find the Ramsey number $R(P_4,C_7)$
For my introduction to combinatorics class, we are being asked to compute the Ramsey number for $R(P_4,C_7)$ where $R(P_4,C_7)=k$ is the minimum number of vertices needed such that the 2-coloring of $...
- 440
9
votes
0
answers
123
views
Amazing property of Pascal's triangle: the product of the numbers along each median is always the same. Is there an intuitive explanation?
On Pascal's triangle with any number of rows, draw the three medians.
For each median, calculate the product of the numbers that zig-zag along that median.
The three products are always equal! (proof ...
- 16.6k
1
vote
1
answer
22
views
Gallai--Milgram theorem: relation between path cover number and independence number?
Gallai--Milgram theorem states that for any directed graph $D$, there exists a family of vertex-disjoint paths $P_1,\dots, P_k$ such that $\cup_{i=1}^nV(P_i)=V(D)$ and there exists an independent set $...
- 1,933
0
votes
1
answer
42
views
A problem on counting total number of ways of arranging numbers in a grid.
Let $N$ be the number of ways to place the integers $1$ through $12$ in the $12$ cells of a $2×6$ grid so that for
any two cells sharing a side, the difference between the numbers in those cells is ...
- 469
-1
votes
1
answer
118
views
Number of integer solutions to $x_1+x_2+x_3+x_4=20$ [closed]
I am studying for an exam and have the question:
How many integer solutions are there to $x_1+x_2+x_3+x_4=20 \text{ where }0\leq x_1\leq3,0\leq x_2\leq4,0\leq x_3\leq5$?
I first thought I needed to ...
- 197
0
votes
1
answer
40
views
Counting the number of binary solutions to system of equations by finding the coefficient of a term in a generating function
I am trying to solve the number of binary solutions to a system of linear equations, the same as in this question: number of binary solutions under linear restrictions.
Shortly:
Consider $ x1,…,x_n ∈ ...
- 3
1
vote
1
answer
59
views
Closed Set in Product Topology
I am trying to understand the Compactness Argument in a Graph Theory Problem using Probabilistic Methods. $V$ is infinite set.
For each finite subset $X \subset V$, let $C_X \subset [2]^V$ be the ...
2
votes
1
answer
76
views
Formulas for Trace expressions like $\operatorname{Tr}(AA^TA)$ for Gaussian $A$
Suppose $A$ is an $n\times n$ matrix with IID standard normal entries and I'm given a sequence like $A,A^T,A,A,A,A^T$. How would I obtain the formula for $E\operatorname{Tr}(AA^TAAAA^T)$ in terms of $...
- 4,953
6
votes
1
answer
181
views
+50
Bayes' theorem and card colors
This is an expansion/generalization of a previous question I've asked here. Some of the simplifications I made in the original question turned out to be too simplifying, so I'm trying again. The most ...
- 43
3
votes
3
answers
76
views
Probability of getting a correct Bit
I have a probability problem that goes like this: I want to sent a bit across a channel that has a certain error rate. The probability of getting a bit wrong is $0.3$, and so to increase the chances ...
- 335
0
votes
1
answer
94
views
Binomial identity?
$${n+k-1 \choose k}=\sum_{m=1}^{min(k,n)}{k-1 \choose m-1}{n \choose m} $$
Is there a simple way to demonstrate this equality?
Context
These are two ways of expressing the $x^k$ coefficients in $(1+x+...
1
vote
1
answer
64
views
Probability of each boy standing diametrically opposite to a girl in a round table
There are 9 girls and 5 boys (all 14 of them are unique) are standing next to each other forming a circle with random placement.
If the probability of each boys are standing directly opposite to girl ...
- 55
1
vote
0
answers
47
views
I'm trying to prove that $ (n+1)!-1 = \sum_{i=1}^n i • i! $ combinatorially [duplicate]
I'm trying to prove this identity combinatorially:
$$ (n+1)!-1 = \sum_{i=1}^n i • i! $$
I tried to ask and answer the question:
In how many ways can we list (n+1) different numbers such that we don'...
- 61
3
votes
1
answer
93
views
Balls are pulled and distributed randomly into the boxes. What is the probability that in no boxes there will be balls of the same color?
Full Question: The pool of 100 balls contains 20 pink balls, 10 yellow balls, 20 purple balls, 15 indigo balls and 35 green balls. We randomly pull 10 balls out of 100 and randomly distribute them ...
- 31
2
votes
0
answers
26
views
Graph class where Hamiltonian Path is polynomial and Path cover is NP-complete?
Path cover asks, what is the minimal number k such that G can be covered by k vertex-disjoint paths. (Path cover of G has size 1 if and only if G has a Hamiltonian path).
Is there a graph class (...
- 21
0
votes
1
answer
64
views
Does the Arctic Circle Theorem have anything to do with the geographical Arctic Circle?
Does the Arctic Circle Theorem have anything to do with the geographical Arctic Circle?
- 608
0
votes
1
answer
55
views
Some help on a combinatoric problem
Problem
Solution
I don't understand the solution. I haven't studied much combinatorics so I do not no what they mean by "5-cycle" and "3 and 2-cycle", how there is 4! 5-cycles ...
- 87
2
votes
1
answer
128
views
Let G be a connected graph in which every vertex has degree three. Show that if G has no cut-edge then every two edges of G lie on a common cycle.
"Let $G$ be a connected graph in which every vertex has degree three. Show that if $G$ has no cut-edge then every two edges of $G$ lie on a common cycle."
I have an idea for this proof but I'...
- 85
0
votes
1
answer
50
views
Number of injective functions between sets
Let A = {1, 2, 3, 4, 5, 6, 7} a B = {1, 2, 3, 4, 5, 6, 7, 8, 9}. How many injective functions f : A → B exist such that f({1, 2, 3, 4, 5}) ⊇ {1, 2, 3}?
My approach:
Since I have to choose 3 positions ...
2
votes
3
answers
87
views
Prove that $\sum_{i=0}^{\lfloor n/2 \rfloor }\sum_{j=0}^{\lfloor n/2 \rfloor-i}{n \choose 2i}{n-2i \choose 2j}2^{n-2i-2j}=4^{n-1}+2^{n-1}$
I was working on problem 1 from the IMC 2020 and got the following expression for the solution:
$ \sum_{i=0}^{\lfloor n/2 \rfloor }\sum_{j=0}^{\lfloor n/2 \rfloor-i}{n \choose 2i}{n-2i \choose 2j}2^{n-...
- 31
2
votes
1
answer
42
views
Computing $E[\|ABB^TA^T\|_F^2]$ for Gaussian $A,B$
Suppose $A$ and $B$ are $n\times n$ matrices with IID standard normal entries.
What is the value of the following expression as the function of $n$?
$$E[\|ABB^TA^T\|_F^2]$$
The first few values are ...
- 4,953
0
votes
1
answer
31
views
About upper asymptotic density.
Let $A$ be a subset of $\mathbb{N}$ and $(p_i)_i$ a strictly increasing sequence of positive integers. We define
$\overline{d}(A|(p_i)_i):=\limsup_n \frac{\left| A \cap \left\{ p_1,\cdots , p_n \right\...
- 11
0
votes
1
answer
24
views
form a subgroup by picking simultaneously 3 students among a group of 8 students, how many subgroups we can make?
I am just a bit puzzled by this question even when it is easy:
"How to form a subgroup by picking simultaneously 3 students among a group of 8 students. How many different subgroups can we form?&...
- 491
1
vote
1
answer
32
views
Showing the isomorphism between (the geometric lattice)$\pi_n$ and the lattice $\mathcal{L}(M(K_n)).$
Here is the question I am trying to solve:
Show that the lattice of flats of $M(K_n)$ is isomorphic to the partition lattice $\pi_n$. Definition: $\pi_n$ is the set of partitions of $[n]$, partially ...
- 3,653
0
votes
0
answers
73
views
Extracting coefficients with the power series $(1-x)^{-n}$
Given polynomials of the form $$(1+x+x^2+x^3+\cdots+x^k)^n $$ We can calcualte the coefficients by writing it in the form $$(1-x^k)^n \over (1-x)^n$$ and using the power series $(1-x)^{-n}$, as has ...
0
votes
1
answer
26
views
What is the difference in my reasoning for sampling with replacement and the correct reasoning?
I am currently reading Blitzen and Hwang's Introduction to Probability book, and am on Theorem 1.4.7, which states that when you are sampling n objects and making k choices from them one at a time ...
- 69
0
votes
1
answer
64
views
probability distribution of total number of cells with 1/2 probability of dividing.
There is a cell that has a 1/2 probability of dividing into two daughter cells (the parent cell disappears) and a 1/2 probability of stop dividing. And each daughter cell has a 1/2 probability of ...
- 103
-3
votes
0
answers
32
views
proof of an inequality of power function
I was reading a book and was stopped by the following inequality:
$$\frac{x+1}{x+1-k}\geq\left(\frac{x+1}{x}\right)^k$$
for all $x,k\in\mathbb{N}$, $k\leq x$, $x\neq 0$.
Is there a hint to prove this ...
0
votes
0
answers
31
views
Multinomial Theorem expansion in Combinations Problem
While studying application of Multinomial theorem in PnC I got stuck in two questions :
In how many ways the sum of upper faces of four distinct dice can be six ?
The textbook gave the following ...
0
votes
0
answers
23
views
Counting the number of words without a specific substring using recurrence relation [duplicate]
Suppose your alphabet is $\{A, C\}$. Every combination of letters is a word. How many words of length $N$ are there such that they do not have "ACA" as a substring?
It is required that the ...
- 455
3
votes
1
answer
144
views
Proving $\sum_{i=0}^{n}\sum_{j=0}^{n}\binom{i+j}{i}\binom{n-i}{j}\binom{n-j}{i}\ =\ \sum_{k=0}^{n}\binom{2k}{k} $
Prove that $$\sum_{i=0}^{n}\sum_{j=0}^{n}\binom{i+j}{i}\binom{n-i}{j}\binom{n-j}{i}\ =\ \sum_{k=0}^{n}\binom{2k}{k} $$
This one I have no idea how to crack.
Induction doesn't seem to be a sensible ...
- 205
8
votes
1
answer
181
views
Two element subset of $\{1,2,\dots,100\}$ with sum of elements being a square
Prove that every 50-element subset of $\{1,2,\dots,100\}$ contains two
elements $a,b$ such that $a+b$ is a square of integer.
Any 50-element subset of the set $\{1,2,\dots,100\}$ has $\binom{50}{2}=...
- 205
3
votes
1
answer
301
views
How many Katamino solutions are there on a $5 \times 12$ board?
Katamino is the puzzle of placing twelve polygonal pieces so as to form a $5\times 12$ rectangular array. The pieces consist of all possible arrangements of five connected $1\times 1$ squares. For ...
- 33
0
votes
1
answer
43
views
Why doesn't n choose k work for selecting a 3-committee form 6 people?
We have 6 people, A,B,C,D,E,F in a committee and we're to select a chair, secretary and a treasurer. In how many ways can this be done?
My initial attempt was: Ok easy, we just count how many ways we ...
- 519
0
votes
1
answer
68
views
"easy counting argument" to show some large subset is not a subcover
I am reading Camina and Evan's paper "Some Infinite Permutation Modules".
In the proof of Lemma 2.2, they use the following combinatorial argument:
[...] $S$ is a collection of $k$-subsets ...
- 460
1
vote
1
answer
61
views
Probability of a 2 Period in a Random Function
Source: Similar to problem 3.1.11 in Donald Knuth's The Art of Computer Programming. Here, let $[m]=\{ 1,2,\dots,m \}$ denote the set of the first $m$ natural numbers.
Suppose we pick a function $f: [...
- 730
2
votes
4
answers
62
views
Probability of one correct answer among 10 questions
I'm not sure how to obtain the answer to problem 6.5.30 R Johnsonbaugh, Discreete Mathematics, 8 ed: "An unprepared student who takes a 10-question true–false quiz and guesses at the answer to ...
- 519
1
vote
1
answer
42
views
Prove existence of traversal in case subset has a traversal
The family of sets $(X_1, \dots, X_r, \dots, X_n) $ has a traversal. From this traversal, we can construct a traversal $x_1, \dots, x_r$ on the subfamily of sets $(X_1, \dots, X_r)$.
Question:
Is this ...
