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
4 views

Combinatorics maths problem

Consider the design of a communication system in the United States. (a) How many three-digit phone prefixes that are used to represent a particular geographic area (such as an area code) can be ...
2
votes
1answer
36 views

Combinatorial proof $\sum_{i=1}^n i/(i + 1)! = 1 - 1/(n+1)!\quad\forall n\in\mathbb N$

I am trying to come up with a combinatorial (or at least partly combinatorial) proof of the equation $$\sum_{i=1}^n \frac i{(i + 1)!} = 1 - \frac 1{(n+1)!}\quad\forall n\in\mathbb N$$ I am thinking ...
1
vote
0answers
13 views

Enumerating functions modulo action on both the domain and codomain.

Let $Hom(A,B)$ be the set of functions from a finite set $A$ to a finite set $B$ and let $G_A \leq S_A$, $G_B \leq S_B$ be a subgroups of the permutation groups of $A$ and $B$. For $f,g \in Hom(A,B)$ ...
1
vote
2answers
12 views

Number of committees of size 5 with at least 2 women from a society with 10 men and 12 women

I've been thinking about this problem: A committee of size 5 is formed from a society with a membership of 10 men and 12 women, with the restriction that there are at least 2 women on the committee. ...
1
vote
2answers
27 views

Fundamentals of Probability

Suppose I have two boxes , containing white and black balls. In the first one , we have 8 white and 6 black balls. In the second one , we have 4 white and 7 black balls. Now if one ball is drawn at ...
0
votes
0answers
9 views

finding all $m\times k$ matrices with prescribed row and column sums and zero elements

I'm looking for an algorithm constructing non-negative integer matrices with prescribed row and column sums and some predefined zero entries. For example, if column sums are [1 1 2 1 1] and row sums ...
0
votes
2answers
15 views

Families of subsets whose union is the whole set

Let $n\geq k>0$, and consider the family $\mathcal{F}$ consisting of all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. Among the $2^{\binom{n}{k}}$ subsets of $\mathcal{F}$, how many ...
1
vote
0answers
8 views

How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)?

How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)? I'm starting with a class of a given size and a group of a giving ...
-2
votes
0answers
34 views

The number of all groups with n elements? [on hold]

Let $n$ be a positive integer number. How many groups of $n$ elements (which are not isomorphic) ?
1
vote
1answer
38 views

Greatest number of red coloured points

Problem: Let m and n be integers greater than 1. Consider an m×n rectangular grid of points in the plane. Some k of these points are coloured red in such a way that no three red points are the ...
4
votes
1answer
33 views

Proof of stars and bars formula

I am trying to prove a formula (for ways of distributing n identical balls among r persons when each person may get any number of balls) C(n+r-1, r-1). But I am not able to prove it. I may be doing ...
-1
votes
2answers
35 views

Distribution of identical objects among people

How to find the number of ways in which n identical objects can be divided among r persons where each person gets a maximum of k objects?
1
vote
2answers
37 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
22 views

Combinatorics - find subsets with one shared item [on hold]

I'm a computer science student. I played a game with my cousin, in which there were many cards with 8 item on each card, such that every 2 card share exactly 1 item. It made me wonder about this ...
5
votes
2answers
59 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
18 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
23 views

how many ways a captain be chosen? [on hold]

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
1answer
26 views

composition of an integer number into some limited parts

Given $k,m,n\in\mathbb N$, $n\ge m$, 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
34 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
40 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
23 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
189 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
20 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
64 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
35 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
31 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
18 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
28 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
48 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
34 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
270 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
108 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 + ...
1
vote
0answers
32 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
44 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
3answers
75 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
20 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
41 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
652 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
35 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 ...