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
2answers
22 views

How many ways can we form two non-intersecting triangles from an $n$ sided regular polygon

Say I wish to form exactly two non-intersecting triangles using vertices of an $n$ sided polygon. How many ways would there be of doing this? I have below an example of a 'good' set of triangles. ...
-2
votes
0answers
15 views

Combinatorics - find subsets with one shared item

Given a set with n items, find x subsets, each one of them of size y, such that every two subsets share exactly one item.
5
votes
1answer
37 views

Number of matrices $A \in M_n(\mathbb{F}_q)$ where $A^2 = 0$.

What is the number of matrices $A \in M_n(\mathbb{F}_q)$ for which $A^2 = 0$ (as a function of $n$ and $q$)?
0
votes
1answer
11 views

Going from one corner to another, using D and R. Is there a nicer way?

Suppose I have an $m \times n $ grid and I want to get from the top left corner to the bottom right corner, but only being allowed to go down and right. If we consider a sequence of $m$ R's and $n$ ...
-1
votes
1answer
24 views
-1
votes
3answers
22 views

how many ways a captain be chosen?

from a group of $40$ players a cricket team of $11$ players is choosen. Then one of the $11$ is choosen as the captain of the team. How many ways this can be done ?
1
vote
0answers
16 views

composition of an integer number into some limited parts

Given $k,m,n\in\mathbb N$, $m\ge n$, is there a way to find the "leading solution" with respect to the reverse lexicographic order for the following problem? $$\left\{\begin{array}{ll} \sum_{i=0}^{k} ...
2
votes
1answer
30 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
38 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
20 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
178 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
62 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
21 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
29 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
27 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
102 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
21 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 ...
2
votes
0answers
19 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 ...
1
vote
0answers
39 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
646 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
32 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
70 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$ ...