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)

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 ...
0
votes
2answers
38 views

Number of divisors $d$ of $n^2$ so that $d\nmid n$ and $d>n$

I just wanted to share this nutshell with you guys, it is a little harder in this particular case of the problem: Find the number of divisors $d$ of $a^2=(2^{31}3^{17})^2$ so that $d$ does not ...
2
votes
1answer
35 views

Find the number of functions

How many functions $f : \{0,1\}^n \mapsto \{0,1\}$ have the equal number of function values $0$ and $1$? I have the answer to the question: $ \sum_{k=0}^{2^{n-1}} 2^{n-1}\binom{2n}{2k}\binom{2k}{k}$, ...
5
votes
1answer
58 views

Proof of Vandermonde's Identity using a “different approach” using complex integration

Hi I'd like to know if the following proof of Vandermonde's Identity is correct (is really easy): Let $m,n,r$ be natural numbers such that $r\le \min \{m,n\}$. The Vandermonde's Identity gives us ...
1
vote
1answer
17 views

Cardinality of the set $D$

Let , $D$ be the set of tuples $(w_1,w_2,\cdots,w_{10})$ , where $w_i \in \{1,2,3\},1\le i\le10$ and $w_i+w_{i+1}$ is an even number for each $i$ with $1\le i\le 9$. Then find the cardinality of ...
2
votes
1answer
41 views

In how many ways can the letters of the word $PATNA$ be arranged?

In how many ways can the letters of the word $PATNA$ be arranged ? $a)\ 60 \\ b)\ 120 \\ c)\ 119 \\ \color{green}{d)\ 59 }\\ $ I thought it would be $\dfrac{5!}{2}=60$ but in book answer is ...
2
votes
1answer
29 views

How to solve this kind of combinatorics problem?

I have a question about combinatorics. Here is the question: A waiting area outside the doctor's office contains a row of 7 chairs. In how many different ways can a man, a woman and a boy occupy 3 ...
0
votes
0answers
10 views

Number of possible non crossing paths on a grid of $m$ by $n$ size?

Given two points on 2 dimensional m by n grid, moving in units of 1 in either direction, how many non intersecting paths exist between the two points? in other words, with taxi cab metric, on a m by ...
3
votes
0answers
25 views

Number of $m$-subsets $Y$ satisfying $|A\cap Y|\le t$

Let $X$ be a finite set with $n$ elements and $A$ be a subset of $X$ with $a$ elements. Let $m,t\le n$. I'm interested in counting the number of subsets $Y$ of $X$ with $|Y|=m$ satisfying $|A\cap ...
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
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 ...
-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 ...
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. [closed]

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 ...
7
votes
4answers
12k views

How many distinct functions can be defined from set A to B?

In my discrete mathematics class our notes say that between set A (having 6 elements) and set b (having 8 elements), there are $8^6$ distinct functions that can be formed, in other words: $|b|^{|a|}$ ...
0
votes
1answer
47 views

Generating function counting quaternary sequence.

I have the following problems: $1.$ Calculate the number of the n-digits Quaternary sequence containing even $"2"$ and $"1"$ and at least one $"3"$. (When a sequence is made by the digits $1,2,3,4$) ...
1
vote
2answers
108 views

More Generating Functions problems

(a) For this problem, define a nonstandard die as a 6-sided die that is equally likely to come up on each side, but has a different set of numbers than the usual 1,2,3,4,5,6 on its sides. A standard ...
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 ...
0
votes
1answer
40 views

What will be Terms after repeating this step(Differentiation and multiplication) F times.

I was solving a probability problem and got stuck on the following situation, where each x_i is independent of others: $$f=(x_1+x_2+..x_k)^N$$ I'm interested in the expression obtained after ...
5
votes
2answers
85 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$)?
3
votes
0answers
85 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 ...
0
votes
1answer
14 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$ ?
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 ...
-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
1
vote
2answers
41 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 ...
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? ...
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! ...
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 ...
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
23 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}$ ...
3
votes
4answers
75 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 ...
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
38 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 ...
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 ...
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)$ ...
2
votes
1answer
328 views

Count ways to reach last layer

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$. The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex ...
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 ...
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 ...
-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
38 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?
2
votes
3answers
13k views

Counting functions between two sets

We got this question in homework (excuse my poor translation): This question deals with counting functions between two sets: A. How many functions exist between the set $[1,2,...,n]$ and the ...
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} ...
6
votes
3answers
81 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 ...
6
votes
5answers
3k views

Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if ...
6
votes
1answer
490 views

101 positive integers placed on a circle

A Pigeonhole Principle problem: 101 positive integers are placed on a circle whose sum is 300. Prove that it is possible to choose from these numbers some consecutive numbers whose sum is ...
3
votes
1answer
298 views

Number of ways of placing $n$ distinguishable balls in $k$ indistiguishable bins where the maximum size of a bin is $m$

I know that the number of ways of placing $n$ distinguishable balls in $k$ indistinguishable bins is given by the Stirling number of the second kind. But I don't know how to modify it to include the ...
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$ ...