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)

2
votes
1answer
8 views

Combinatorics question on group of people making separate groups

If there are $9$ people, and $2$ groups get formed, one with $3$ people and one with $6$ people (at random), what is the probability that $2$ people, John and James, will end up in the same group? ...
0
votes
1answer
19 views

Probability that in bridge game the Players N,E,S,W have a,b,c,d spades respectively.

There are 52 cards in bridge and 13 cards of each suit. The formula for numerator is: $${13\choose a}{39 \choose 13-a}{13-a\choose b}{26+a\choose 13-b}{13-a-b\choose c}{13+a+b\choose 13-c}$$ But i ...
2
votes
1answer
14 views

Generating function for tuples of objects based on their maximal size

This is a question which arose while working through Flajolet-Sedgewick's Analytic Combinatorics. In their terminology, the cartesian product of two combinatorial classes $\mathcal{A},\mathcal{B}$ ...
0
votes
0answers
9 views

Problem on costructing flows in a network with multiple sources and sinks

Problem : Formulate and prove a theorem that gives necessary and sufficient conditions so that a network with multiple sources and sinks has a flow that simultaneously meets all prescribed demands ...
-3
votes
0answers
29 views

number of phone prefixes satisfying given conditions [on hold]

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 ...
3
votes
4answers
65 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
16 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
13 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
37 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
12 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
16 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
9 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
39 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
37 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
37 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
40 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
61 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$)?
1
vote
1answer
20 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
25 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
27 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} ...
3
votes
1answer
35 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
24 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
25 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
65 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
33 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 ...