For 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)

0
votes
0answers
12 views

Combinatorial problem of choosing points inside an equilateral triangle without them being too close.

Determine the smallest integer $m_n$ which satisfies the following property: If $m_n$ points are chosen inside an equilateral triangle of sides 1, then at least two of them are at distance ...
2
votes
1answer
36 views

Use the 'rule of sum to prove that $\sum_{k=0}^n 2^k=2^{n+1}-1$.'

I'm attempting a combinatorics problem that asks to use the 'rule of sum to prove that $\sum_{k=0}^n 2^k=2^{n+1}-1$.' The rule of sum says that 'if $S=\cup_{i=1}^t S_i$ is a union of disjoint sets ...
1
vote
0answers
16 views

Sampling substrings of a beaded necklace to determine the necklace composition

I have a necklace composed of 100 beads, where each bead is one of 13 colors. If I am only able to look at one 4 bead sub-sequence at a time (connected, as they would be on the necklace) , how many ...
1
vote
1answer
162 views

Would this proof strategy work for proving the lonely runner conjecture?

The problem is the lonely runner conjecture. This conjecture states that if $k$ runners begin running down a circle of unit circumference with random speeds, it will always the case that all runners ...
1
vote
0answers
19 views

The probability that two matrix vector products are equal

Consider a random $n$ by $n$ circulant matrix $M$ whose first row entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first ...
2
votes
4answers
60 views

Show that there is a number on the form $11 \dots 000 \dots 0$ divisible by 2014

Show that there is a number on the form $11 \dots 000 \dots 0$ (some number of $1$s followed by $0$s) divisible by $2014$. I'm helping someone practise for the math olympiad, and this question has me ...
1
vote
2answers
34 views

Looking for set of combinatorics problems

I'm preparing to Mathematics for Computer Science exam. What I learned from past edition of exams is fact of very often occurence of old problems. I mean more or less known problems, but possible to ...
0
votes
1answer
20 views

Number of partitions containing $k$ occurrences of a given number

Consider the ordered partitions of $N$ with size $m$ ($m \leq N$), that is, the set $\mathcal{P}_m^N$ of all vectors $\vec{n} \in \mathbb{N}^m$ such that $\sum_{i=1}^m n_i = N$. In how many of these ...
2
votes
0answers
28 views

Number of “left-to-right” walks on a line graph

Let $G_n$ be the line graph on $n$ nodes. An example when $n=4$: Let $a_n(k)$ be the number of walks on this graph of length $k$, which start at node $1$ and end at node $n$. $a_n$ satisfies a ...
0
votes
1answer
17 views

What is the number of unique labeled connected graphs with N Vertices and K edges?

I've seen this question several times, and this one caught my attention. I'm now aware that there is no closed formula for this. My knowledge of graph theory is limited, and I wasn't able to find an ...
0
votes
2answers
26 views

Anagrams contained within random strings

What is the probability that a random string of length $n$ will contain an anagram of a shorter string of length $k$? E.g., you generate a string of 50 random letters, repetitions allowed, what are ...
0
votes
2answers
47 views

Calculating the number of ways to arrange a set of letters such that no two identical letters can occur consecutively

How can I find the number of ways in which the letters $$z,z,y,y,x,x,w,w,v,v$$ can be arranged so that two letters of the same kind never appear consecutively. I am not confident that my approach is ...
2
votes
1answer
28 views

count permutations that do not contain repeated combinations

I am trying to count the number of permutations that do not contain order specific groupings that have occurred in permutations that have already been counted. Example: For the set {A B C D E}; if ...
2
votes
1answer
269 views

Probability or Set

I'm really good at probability, but this time I seems like I'm not. My friends asked me a very tricky question, and I want to see if there's anyone who can find out the answer. Here's the ...
1
vote
2answers
30 views

Why the Ramsey number $R(2,4)$ is not equal to $2$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. Here: I don't understand: For all $2$-colorings, it must have a $K_p$ and $K_q$ or it must have a $K_p$ or a $K_q$? I'm ...
1
vote
1answer
30 views

elementary problem in combinatorics

Let $X=\{1,2,3,4,5,6,7,8,9,10\}$ and $R$ be a set defined by $$\{(x,y)\in X\times X: \text{$x$ and $y$ have the same remainder when divided by $3$}\}$$ Then what's the numbers of elements in $R$? My ...
3
votes
5answers
101 views

Proof check: $(4n)!$ is divisible by $2^{3n}3^{n}$

Question: Show that $(4n)!$ is a multiple of $2^{3n}3^{n}$ for all $n$. Proof: It's easy (involves kinda messy calculation tho) to show by induction that $(4n)!$ is a multiple of $2^{3n}$. Now, since ...
2
votes
2answers
37 views

Soft Question: Combinatoric reading material

I am curious if anyone can recommend a good introductory text on combinatorics in similar vein as Richard J. Trudeau's Introduction to Graph Theory put out by Dover. For those who have not read it, ...
-1
votes
1answer
46 views

Polynomial in $x$ problem

please help me solve this problem: a polynomial in $x$ is defined by $$a_0 + a_1x + a_2x ^ 2 + ... + a_{2n} \, x^{2n} = (x + 2x^2 + ... + nx^n) ^ 2 .$$ Show that: $$\sum_{n + 1}^{2n}a_i = n(n + ...
0
votes
0answers
31 views

Gambler's Ruin With a Pay Schedule

I am curious about how to calculate the expected number of games until a gambler with $B$ dollars gets to $M>B$ dollars, or gets ruined. I am also curious how to calculate the probability of ruin. ...
4
votes
1answer
42 views

How many ways to arrange m chosen objects when there are n total objects, and some are indistinguishable?

I have $n$ different types of objects, where each member of a type is indistinguishable from every other member. There are $k_1$ of the first type, $k_2$ of the second type, and so on, up to $k_n$ of ...
6
votes
2answers
57 views

How to draw the 5 dimensional hypercube graph with 56 edge crossings?

I'm probably doing something stupid but I can't seem to think of a way to draw $Q_5$ with $cr(Q_5) = 56 $. In this paper the author says drawing a hypercube graph with $\leq56$ edge crossings is easy ...
0
votes
1answer
20 views

Different sums by adding the currency.

How many different sums can be formed by the following $5$ dollar, $1$ dollar, $50$ cents, $25$ cents, $10$ cents, $3$ cents, $2$ cents, $1$ cent. As there are $8$ different things and at ...
1
vote
0answers
18 views

Euler Integral of a self-overlapping tube with a cusp singularity

I am studying in depth the following paper on Euler calculus applied to target enumeration: https://www.math.upenn.edu/~ghrist/preprints/eulerenumerationpart1.pdf Within this paper there is an ...
1
vote
1answer
38 views

How many ways can an integer $i$ appearing in a sequence with multiplicty at least $j$, be minimal

Let us construct an integer sequence of length $n$, where the integers are chosen from $\{1, 2, ..., k\}$, with i.i.d. uniform probability $\frac{1}{k}$. I want to compute the probability ($p_{ij}$) ...
2
votes
3answers
29 views

The number of times will an individual child goes to the cinema before a group is repeated.

$1.)$ A mother with $7$ children takes $3$ at a time to a cinema.She goes with every group of $3$ that she can form.How many times can she go to cinema with distinct groups of $3$ children? ...
-8
votes
0answers
47 views

identity permutations [on hold]

I need some help with the following question : For the permuation $ π $ on n elements we define the term : $ π^k=i $ if the composition of π on it self k times is the identity permutation . (where ...
0
votes
0answers
38 views

Number of ways to put hat(s) in $5$ boxes.

If their are two kinds of hats , red and blue and at least $5$ of each kind, in how many ways can the hats be put in each in each of the $5$ different boxes. I assumed that their are $10$ hats ...
21
votes
3answers
645 views

Counting matchings, the modern way

A hundred years ago, if you had $k$ men and $k$ women and wanted to marry them all off in pairs, it was easy to see that there are exactly $k!$ ways to do that. Today, however, societal standards ...
2
votes
2answers
33 views

How to prove that the subsets of $\mathbb{N}$ that don't contain arithmetic progressions of some length form closed sets of a topology?

I have exactly the same problem as this person, which I will rewrite below:Topology and Arithmetic Progressions. The reason I'm posting this is that I'm stuck at a later stage than the OP of that ...
0
votes
0answers
31 views

Properties of Coefficients of Order Polynomials

I am working on a problem involving determining the order polynomial $\Omega_P(k)$ of a partial order $P$, which counts the number of order-preserving transformations/maps from $P$ to the $k$-chain ...
2
votes
1answer
54 views

How to show $\binom{2n}{n} \ge \prod_{n < p \le 2n} p $?

What is the best way to show \begin{equation} \binom{2n}{n} \ge \prod_{n < p \le 2n} p \end{equation} for prime $p$. I know that $ 2^{2n} = (1+1)^{2n} \ge \binom{2n}{n}$. and \begin{equation} ...
2
votes
0answers
23 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
3
votes
3answers
69 views

Simplifying $\sum_{i=0}^n i^k\binom{n}{2i+1}$

What is the formula for \begin{eqnarray}\sum_{i=0}^n i^k\binom{n}{2i+1}?\end{eqnarray} I tried to use the identity $$ ...
4
votes
3answers
56 views

Chart of Rounds for a Game

I need to solve the following problem for actual use. 10 people will be playing a game. They play the game 4 people at a time. Each time they play they garner points within the game. Each person ...
2
votes
4answers
61 views

Random number function (counting)

I have task I can't get my head around, even with a suggested answer. You have a function the generates a random integer between $0 - 65535$. Your task is to generate random integers $125-525$ ...
-2
votes
0answers
63 views

the identity permutation [on hold]

for the permuation $ \pi $ on n elements we define the term : $ \pi^k=i $ if the composition of $ \pi $ on it self k times is the identity permutation . A. let $ a_n $ be the number of permutation of ...
0
votes
0answers
26 views

Locks and Keys using permutation and combination [on hold]

This is a problem using permutations, combinations and factorial. There are four bankers in charge of a bank vault. We can not trust all of the bankers (2 of them are untrustworthy, we don't ...
3
votes
0answers
31 views

Maximum difference between tails in absolute value

I toss a fair coin $n$ times. Some notation: $S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$. $M_n=\max(S_1,S_2,\dots,S_n)$, ...
1
vote
2answers
41 views

Probability that among 3 random digits two different one

I have been trying to solve the following problem: What is the probability that among 3 random digits, there appear exactly 2 different ones? The formula for no repititions is: ...
14
votes
13answers
3k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [on hold]

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142. But I ...
0
votes
0answers
22 views

How to enumerate (not count) combinations and permutations? [duplicate]

I’d like to ask if there is any formula or method to enumerate combinations and permutations such that if I know that there are X unique combinations/permutations, I could take a number between 1 and ...
10
votes
0answers
69 views
+100

Congruent quadrilaterals in a tri-colored $72$-gon

I recently watched a movie (A Brilliant Young Mind) in which this problem appeared: Let the vertices of a regular $72$-gon be colored red, blue, and green in equal parts. Show that there are $4$ ...
0
votes
0answers
40 views

What is the maximum value of $M$ when $T$ is set of $\{2,4,8,16,… 2^n\}$ and $S$ is subset of $T$ by given conditions

Qns $T$ is set of $\{2,4,8,16,... 2^n\}$ and $S$ is a subset of $T$ if the sum of no two elements of $S$ is greater than $2^n-2$. let $m$ be $M$ number of elements in $S$. what is ...
1
vote
1answer
30 views

Chessboard pawns arrangement clarification

I have a 8 X 8 chessboard, and 8 identical pawns. These pawns are arranged at random. What is the probability that the pawns are arranged in such a way that each row and column have only one pawn? My ...
2
votes
2answers
51 views

Two problems on combinatorics

Suppose we have a bag which has chips of four colors numbered $1$ to $13$, i.e. in total $52$ balls. Now what is the difference between these two problems. Problem-$1$- In how many ways can you ...
-3
votes
1answer
67 views

Pigeonhole Principle proving [on hold]

Suppose that there are 30 people in the room. Assume that everyone in the room has at least one acquaintance. Show that there are two persons in the room who have equal numbers of acquaintances. Since ...
0
votes
0answers
34 views

Comparison of entries of a real matrix

Let $A$ be an $m$ by $n$ real matrix and let $p$, $q$ be positive integers with $p\leq n$, $q\leq m$. In $A$, mark $p$ smallest entries of each row with red color and mark $q$ smallest entries of each ...
0
votes
2answers
77 views

How many pairs $(m, n)$ exist?

For certain pairs $ (m,n)$ of positive integers with $ m\ge n$ there are exactly $ 50$ distinct positive integers $ k$ such that $ |\log m - \log k| < \log n$. Find the sum of all possible ...
0
votes
0answers
41 views

partitions and generating functions ( combinatorics ) [on hold]

Given partition into distinct parts, let’s say the the ODD parts are: the biggest part, the $3$-rd biggest part, the $5$-th biggest part, etc.; and the EVEN parts are: the $2$-ne biggest part, the ...