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
3answers
153 views

Proving prime number combinatorics

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, ...
1
vote
1answer
10 views

What is $R(k,l)$?

I'm reading Landman/Robertson's: Ramsey Theory on the Integers. It states the following theorem: Theorem 1.15 (Ramsey's Theorem for Two Colors). Let $k,l \geq 2$. There exists a least positive ...
1
vote
1answer
30 views

How to find a formula for these generating sequences?

It is given that $a_{0}=1$ , $b_{0}=0$ , $c_0=0$ $$ c_n= xc_{n-1}+x(x-1)a_{n-1}(3b_{n-1}+(x-2)a_{n-1}^{2})) $$ $$ b_n=xb_{n-1}+x(x-1)a_{n-1}^{2} $$ $$ a_n=xa_{n-1}+1 $$ where x is any constant. ...
0
votes
2answers
314 views

In how many ways can we arrange 40 boys and 20 girls in 5 groups of 12 members each, so that each group contains at least one girl.

My approach There are 5 groups with 12 members each,so if there was condition like there should be 3 girls and 2 boys i would do (20C3)*(40C2) But here it is given as atleast one girl,how to ...
0
votes
1answer
35 views

Ordering People

How many ways are there to order $3$ boys and $3$ girls when the girls sit together and same for the boys. How many ways are there to order $3$ boys and $3$ girls when $2$ boys can not sit ...
4
votes
2answers
53 views

Expected value of max of three numbers

This is a combo problem that a friend came up with some time ago, and recently showed to me. He claims he solved it when it first occurred to him, but can no longer remember the solution, and neither ...
1
vote
1answer
45 views

Binomial Theorem…extra indexed term.

I have the following expression: $$\sum_{i=0}^{n}\binom{n}{i}(2x+1)^{n-i}(-1)^ii!$$ Without the $i!$, the above expression would simply reduce to $(2x)^n$, but is there a way, or method for ...
0
votes
1answer
21 views

How to select four points so that origin is not contained in convex hull of these points?

I have a regular 12-gon $A_1A_2...A_{12}$ with centre $O$. How to select four points so that centre $O$ doesn't lie in and lie on quadrilateral? I tried. With diameter $A_{12}A_6$, consider ...
-1
votes
1answer
42 views
0
votes
1answer
32 views

How many ways can $3$ black counters and $5$ red counters be selected from a bag containing $7$ of each? [closed]

In how many ways can we choose 3 black counters and 5 red counters from a bag containing 7 black counters and 7 red counters?
4
votes
2answers
159 views

Is there a simple expression of this sum related to the coefficients of a generating function of $e^{x+x^2/2}$?

Suppose you have a formula $$ \sum_{n\geq 0}f(n)\frac{x^n}{n!}=\exp\left(x+\frac{x^2}{2}\right). $$ There is a recurrence for $f(n)$ found by differentiation, $$ \sum_{n\geq ...
2
votes
1answer
55 views

Arrange the 26 letters of the alphabet in a row such that certain words do not occurr

How many ways are there to arrange the 26 letters of the alphabet in a row such that none of the following words are formed by consecutive letters in the arrangement INCH, LOST, or THIN? The answer ...
4
votes
2answers
84 views

Matrices and Combinatorics are a bad combination.

Let $\scr A$ be the set of all $n\times n$ symmetric matrices all of whose entries are either $0$ or $1$ and such that if $n$ is even, $n^2/2$ of these entries are $1$ and $n^2/2$ of them are $0$, and ...
2
votes
0answers
60 views

Tricky combinatorics problem

I'm trying to solve the following problem: You get $15$ free spins on a slot machine, with a $0.01$ chance of re-triggering a further $15$ spins when a certain symbol falls on the centre reel. You ...
0
votes
2answers
30 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...
-1
votes
0answers
15 views

Select k non overlapping rectangles in a $n \times m$ grid

We are given a given a $n \times m$ grid with $nm$ points. We have to select $k$ rectangles(obviously with corners lying at lattice points) such that no $2$ of them overlap. We can give a recurrence ...
1
vote
0answers
14 views

The maximum size of an antichain in a poset

Given $A$ as an n-element set and $X=p(A)$, I need to show that if $F$ is an antichain in the poset $(X,\subseteq)$ such that the maximum size of $F$'s elements is $n/2$ then $\mid F \mid \leq (_k^n)$ ...
1
vote
1answer
43 views

Distributing identical objects into distinct boxes

The problem I'm trying to solve is: find the number of ways of distributing $r$ identical objects into $n$ distinct boxes such that no box is empty, where $r \geq n$. I've found conflicting answers ...
1
vote
1answer
37 views

Splitting parties into committees

I feel like this should be an extremely simple problem, but I can't quite figure it out. How many ways are there to split $2n + 1$ places in a committee among $3$ nonempty parties, such that a ...
2
votes
3answers
30 views

Proving the combinatorial expression

Ok I've been reading in my probability book about the different methods on how to count and I'm just trying to dissect the usual combinatorial formula: $$\binom {a} {b} = \frac{a!}{b!(a-b)!}$$ ...
1
vote
2answers
39 views

How many five digit positive integer numbers are possible that each of the digits but the last one, is $\ge$ the next digit?

How many five digit positive integer numbers are possible that each of the digits but the last one, is $\ge$ the next digit? How do I approach this problem?
0
votes
1answer
113 views

If a coin is flipped 25 times with eight tails occurring, what is the probability that no run of $6$ or more heads occurs?

I'm trying to approach this question using generating functions. I set the problem up similar to a "toss $17$ balls into $9$ bins, what's the probability that no bin gets $6$ or balls in it." as the ...
0
votes
1answer
25 views

Counting binary strings of length n with no two adjacent 1's

I need to calculate the total number of possible binary strings of length $n$ with no two adjacent 1's. Eg. for n = 3 f(n) = 5 000,001,010,100,101 How do I solve ...
2
votes
2answers
36 views

Finding Number of Ordered Solutions to Equation

$$ A \times B \times C \times D \times E \times F = 7 \times 10^7 $$ How can I find the number of ordered solutions for integers (I mean for integers $A,B,C,D,E,F$) so that they can satisfy the ...
1
vote
1answer
29 views

Select $k$ non overlapping segments from $n$ points

We have $n$ points , say labeled from $1$ to $n$. We have to select $k$ segments from it so that no $2$ overlap. One possible solution would be by using a recurrence relation $f(k,n)=\sum ...
1
vote
0answers
65 views

The best strategy to increase StackExchange Reputation [closed]

I do not have a lot of background in game theory, but I am curious how would one formally pose the title problem and mathematically describe possible strategies. Are the problems of this type best ...
4
votes
4answers
70 views

Proof of an equation involving Stirling numbers of the second kind

I found this equation involving Stirling numbers of the second kind on Math World: $$\sum\limits_{m=1}^n (-1)^m(m-1)!\,S(n,m)=0 \ .$$ However, I do not know why this is true. I am looking for a proof ...
2
votes
2answers
105 views

A question about $ (2 \times 3) $-rectangles.

The following is a problem from TopCoder: Problem. Given the width and the height of a rectangular grid, return the total number of non-square rectangles that can be found on the grid. For ...
9
votes
5answers
871 views

A seemingly easy combinatorics brain teaser

So I have a brain teaser that goes like this: There's a school that awards students that, during a given period, are never late more than once and who don't ever happen to be absent for three ...
0
votes
0answers
31 views

How to asses the order of combinations

Let $\{a_i\}_{i=1}^m$ be some increasing sequence, bounded away from zero. How to see that as $n\to\infty$, we obtain $$\begin{pmatrix} n\\ m \end{pmatrix}^{-1}\sum_{i=1}^m\begin{pmatrix} ...
1
vote
0answers
57 views

Multinomial Theorem for Negative Exponents

Using an analog to Newton's binomial theorem with negative exponents, is it true that $$ \begin{align} \left(\sum_{k=0}^mx^k\right)^{-n} & = \sum_{0\le ...
0
votes
0answers
11 views

TREE-SEARCH finding key $k$

Prove that the TREE−SEARCH algorithm finds a key, if this belongs to a binary search tree to which the algorithm is applied. I am unsure how to answer this. In our notes it says: If $k$ is the key ...
1
vote
0answers
18 views

Interpretations of a weighted adjacency matrix's eigenvectors and eigenvalues?

Suppose that I have weighted undirected graph $G$, and the corresponding adjacency matrix which is a symmetric matrix $A$. Suppose that the edge between node $i$ and $j$ has weight $w_{ij}$, then $$ ...
0
votes
0answers
36 views

$M$ numbered balls (1 to $M$) drawn from urn (without replacement) - probability that at least one ball number matches its pick number

There is an urn with $M$ numbered balls ($1$ to $M$). All balls are drawn without replacement. Find the probability that at least one ball number matches its pick number. I tried to find the ...
2
votes
0answers
30 views

Generalization of Cauchy-Davenport inequality to $\mathbb Z_p^d$

Is there some generalization of Cauchy-Davenport inequality to the group $\mathbb Z_p^d$? ($p$ prime number, $d \ge 3$) For example, Kneser Theorem says that if $G$ is any abelian group and ...
2
votes
0answers
19 views

Find ordering of directed weighted graph maximizing sum of edges 'going up'

Consider the following problem. Given a weighted directed graph $G=(V,E)$ with $n = |V|$, find an ordering $\pi: \{1,...n\} \to V$ of the vertices that maximizes $$ \sum_{i<j} w_{\pi(i),\pi(j)}. $$ ...
5
votes
4answers
261 views

Finding out this combination

In how many ways three non-empty strings of length less than or equal to $N$ using $k$ different characters can be selected so that in each case, among the three strings, no string is prefix (not ...
1
vote
1answer
86 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
4
votes
1answer
46 views

Complement Probability- Choose A Ball

An urn contains $n$ balls, one of which is special. If $k$ of these balls are withdrawn one at a time, with each selection being equally likely to be any of the balls that remain at the time, what ...
5
votes
2answers
100 views

Solve the following summation

$S = \dfrac{n \choose 0}{1} + \dfrac{n \choose 1}{2} + \dfrac{n \choose 2}{3}+\dotsb+\dfrac{n \choose n}{n+1}$
1
vote
1answer
47 views

Trouble Understanding a Combinatorics Problem

This question appeared on my combinatorics exam. I did not even understand the question. Determine the number of functions, $f:\{1,2,3\} \to \{1,2,3\}$, that satisfy $$f(1)+f(3)\equiv0\ (\text{mod ...
2
votes
1answer
217 views

Number of zero entries in symmetric (0-1)-matrix with full diagonal

Let $S$ be an $n\times n$ symmetric matrix whose diagonal consists only of $1$s and whose other entries are either $0$ or $1$ . If the determinant and rank of $S$ are known, what can be said about ...
5
votes
3answers
448 views

Tricky Rectangle Problem [closed]

How many rectangles are there which do not include any yellow squares?
1
vote
1answer
47 views

Win $n$ out of $2n+1$ [closed]

Two teams play the best of $2n+1$. Team 1 has cheated and wins when they have won $n$ times and Team 2 wins if they have won $n+1$ times. What is the chance that Team 1 will be the winner of the ...
1
vote
3answers
181 views

Probability to pick at least one pair of socks

There are 10 pairs of socks. What is the probability that in 4 socks chosen at random there is at least one pair. My try: Let $A$ be an event of choosing exactly one pair of socks among 4 socks and ...
0
votes
2answers
42 views

Combinatorial sequence [closed]

Say we have $n$ songs, each song is qualified to be a 'rubbish' song ($k$ times) or to be a 'pleasant' song ($n-k$ times). The shuffle modus plays the songs randomly after each other. Determine the ...
0
votes
0answers
29 views

Number of patterns

A pattern consist of three non-empty strings $s_1$ , $s_2$ , $s_3$ such that no string is prefix of another. Strings can have length $\leq n$ and consist of first $k$ english letters of the alphabet. ...
5
votes
1answer
68 views

Combinatorial Proof - choose k out of n+k

I want to prove the following identity combinatorial: \begin{align} {n + k \choose k} = \sum \limits_{i=0}^n {n -i +k -1 \choose k -1}. \end{align} We want to choose k out of $n+k$. I want to use the ...
5
votes
1answer
920 views

Show that triangle-free planar graphs are four-colorable

Prove that every planar graph without a triangle (that is, a cycle of length three) has a vertex of degree three or less. Then, prove that all planar graphs without triangles are four-colorable ...
0
votes
1answer
22 views

How many ways can N labelled balls be placed in M unlabelled boxes, provided each box has at least P balls inside?

How many ways can $N$ labelled balls be placed in $M$ unlabelled boxes, provided each box must have at least $P$ balls inside? Naturally $N > M \times P$. Any closed form solutions would be ...