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

Hadamard matice decomposition to sparce matrices

$H_2=\begin{pmatrix} 1 & 1\\1 & -1 \end{pmatrix}$ and $H_{2n}=H_2\otimes H_n$. I am looking for decomposition of $H_n$ to sparce matrices and its proof. Is there any good source to suggest ? ...
0
votes
4answers
27 views

No: of ways to distribute cards .

In how many ways can a person send invitation cards to $6$ of his friends if he has $4$ servants to distribute the cards ? $a.)\ 6^{4}\\ \color{green}{b.)\ 4^{6}}\\ c.)\ 24\\ d.)\ 120$ As the ...
3
votes
0answers
39 views

Number of players with most wins in tournament

$n\geq 2$ tennis players play each other once, and there are no draws. For which $1\leq k\leq n$ is it possible that exactly $k$ players have the (joint) highest number of wins? For example, $k=1$ is ...
0
votes
1answer
20 views

How many ways are there to make a row of three books in which exactly one language is missing (order matters)?

Given 10 different English books, 6 diff. French books, and 4 diff. German books... The way I went about this one I split into three cases. English missing, French missing, etc. Case #1: EGL misssin ...
0
votes
1answer
17 views

Degree of a self-complementary graph with $4k+1$ vertices [on hold]

How can we prove that every self-complementary graph on $4k+1$ vertices has a vertex of degree $2k$ ?
-4
votes
0answers
11 views

Condition about regular graphs

prove that in graph r regular there are route that in length of at least 2r-1 I don't know how to prove it some one can help me please I have a home work to suggest
0
votes
2answers
29 views

Grouping 15 rating grades in 10 buckets

I am trying to group 15 corporate rating grades into 10 buckets. The grouping cannot be done in a random way - for example the rating grades 1 and 14 cannot be in a single bucket (constraint). The ...
1
vote
2answers
43 views

Find $a_i, b_i$ such that they are all distinct

Very tough, I spent at least an hour, not solving this! From the set of integers $ \{1,2,3,\ldots,2009\}$, choose $ k$ pairs $ \{a_i,b_i\}$ with $ a_i<b_i$ so that no two pairs have a common ...
0
votes
0answers
18 views

Which correct sentence to explain the function $g(\nabla I)=\frac{1}{1+\beta |\nabla(G_{\sigma}*I)|^2}$

I have a edge indicator function that has formula as $$g(\nabla I)=\frac{1}{1+\beta |\nabla(G_{\sigma}*I)|^2}$$ where $\nabla$ is gradient operator, $*$ is convolution operator, $G_{\sigma}$ is a ...
2
votes
0answers
47 views

Combinatorics: Permutation Problem, how to know if a solution is correct or wrong

Question: Find the number of ways of arranging 8 Men and 2 Women in a row such that 2 Women are never together. For the above question, I thought of 2 ways to proceed 1> Arrange 8 men in 8! ...
3
votes
3answers
33 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? ...
1
vote
1answer
31 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
24 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
14 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 ...
-1
votes
0answers
39 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
76 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
18 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
18 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
39 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
18 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
19 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
1answer
16 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 ...
-1
votes
0answers
39 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
46 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
40 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
39 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?
3
votes
2answers
54 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? The condition is that the vertices must be distinct. In ...
-2
votes
0answers
30 views

Combinatorics - find subsets with one shared item

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
86 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
22 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
26 views
-1
votes
3answers
24 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
29 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} ...
4
votes
1answer
36 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
50 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
30 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
195 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 ...
3
votes
0answers
89 views
+250

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
67 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
40 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
22 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
36 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
19 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
29 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
49 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
36 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
272 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
34 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
31 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
109 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 ...