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

How to prove$\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$

I saw a combinatorial identity when i study linear-algebra, But the author didn't explain how to get it. $\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$ I tried $n=10$ or ...
1
vote
0answers
6 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for $y=(y_1,y_2, ..., ...
2
votes
1answer
27 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}$, ...
2
votes
1answer
38 views

Sweet Graph Theory Problem

Here is a nice graph theory question for you all: Suppose we have the complete graph K(n). We then label each edge on this graph with either a 1 or a 0. A path is "sweet" if we are able to start at a ...
0
votes
0answers
9 views

Solution of recurrence relation for roots having multiplicity $ \ge 1 $

If there is a recurrence relation of the form $ a_n = c_1 a_{n-1} + c_2 a_{n-2}+ ... + c_k a_{n-k} $, then if b is a non zero complex root of the recurrence relation with multiplicity t, $t \ge 1 $, ...
2
votes
1answer
36 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 ...
1
vote
1answer
13 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
16 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 ...
-2
votes
0answers
25 views

Counting math problems

1) Ann, Bobby, and Cece are randomly placed in a line with 26 people total. What is the probability that Ann is to the left of Bobby, and Bobby is to the left of Cece? Express your answer as a common ...
5
votes
1answer
51 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 ...
0
votes
0answers
8 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 ...
0
votes
2answers
29 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 ...
3
votes
0answers
12 views

Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form: $$\sum_{n=1}^k ...
3
votes
0answers
20 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 ...
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
25 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
35 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
12 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
28 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
39 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
16 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
40 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
32 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
29 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
20 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
13 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
33 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
74 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
38 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
17 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
0answers
12 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
37 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
44 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
39 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
2answers
43 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
29 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
3answers
83 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
25 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
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} ...
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
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
28 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 ...