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
4answers
53 views

Circular Arrangement with numbers

The number of ways of arranging 2 women and 7 men around a circular table containing nine numbered chairs such that the women are not together. I am getting answer as 7!*7c2(arranging 2 women in the ...
3
votes
1answer
51 views

Combinatorial proof for a non obvious binomial identity

I think I got some serious problem with those combinatorial proofs. Why would the following be true ($1\leq r\leq k\leq n$): $$\sum_\limits{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}?...
2
votes
1answer
27 views

Finding a recurrence for number of paths in a certain tree

I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
0
votes
1answer
48 views

Size of family $\mathcal F = \{F_1, \ldots, F_m\}$ is at least $\lceil \log_2n\rceil$.

A family $\mathcal F = \{F_1, \ldots, F_m\}$ of subsets of $\{1,2,\ldots,n\}$ is said to be separating if for any two elements $1 \leq i < j \leq n$, there is some set $F \in \mathcal F$ such ...
1
vote
1answer
48 views

Combinatorial identity $\sum_{k=0}^{n}\frac{n-k}{k+1}\binom{n}{k}^2 = \binom{2n}{n-1}$

I have an identity $$\sum_{k=0}^{n}\frac{n-k}{k+1}\binom{n}{k}^2 = \binom{2n}{n-1}$$ for which I'm looking for a combinatorial proof. Any ideas? I was thinking about separating $2n$ on boys and ...
7
votes
2answers
182 views

Find number of integral solutions of a*b*c*d = 600

The number of ordered solutions comes out to be 800. I need to find the number of distinct solutions but I'm stuck at calculating the possible combinations. Any ideas on how to proceed further?
7
votes
4answers
148 views

Find the probability that a word with 15 letters (selected from P,T,I,N) does not contain TINT

If a word with 15 letters is formed at random using the letters P, T, I, N, find the probability that it does not contain the sequence TINT. (I just made up this problem.)
0
votes
2answers
56 views

A soccer squad contains $3$ goalkeepers, $7$ defenders, $9$ midfielders and $4$ forwards.

A soccer squad contains $3$ goalkeepers, $7$ defenders, $9$ midfielders and $4$ forwards. So I understood the first part of the question: $(i)$ In how many ways can a team of $1$ goalkeeper, $4$ ...
1
vote
1answer
394 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
3
votes
2answers
85 views

Schedule 8 teams for 6 events. Each team plays each event twice.

I have a seemingly simple question. I'm holding a Beer Olympics at my house tomorrow. There are 8 teams competing in 6 different events (Beer Pong, Beerball, Can Jam, Corn Hole, Beersbee, and Flip Cup)...
0
votes
1answer
24 views

Combinatorial interpretation of multinomial function. [closed]

Given $n$ items if we pick $k$ we use binomial function. What is the analogy with multinomial function?
1
vote
1answer
52 views

Dice rolls - Combinatorics with limitations

Given 2 players, one rolling $x$ d6 dice and the other rolling $y$ d6 dice, what is the probability of a match between the two players? I'm getting stuck on the sub-set comparisons - I can calculate ...
3
votes
1answer
595 views

Distinct combinations of non distinct elements

Is there any way to count the number of distinct combinations of a set of objects where some objects may be identical? We have the basic formulas for $nPr$ and $nCr$, and I understand how to modify ...
3
votes
1answer
125 views

How many possible functions?

Take $f:\{1,2,3,4,5,6,7\}$ to $\{0,1,2,3,4\}$ How many such functions satisfy the cardinality of the pre-image of the set $\{3\}$ is equal to $3$. I thought it would be $35$, i.e :$7\choose{3}$ ...
2
votes
3answers
84 views

Formula for $\sum_{i\geq 0} i{n \choose 2i}$?

So I know that $\sum_{i\geq 0}{n \choose 2i}=2^{n-1}=\sum_{i\geq 0}{n \choose 2i-1}$. However, I need formulas for $\sum_{i\geq 0}i{n \choose 2i}$ and $\sum_{i\geq 0}i{n \choose 2i-1}$. Can anyone ...
1
vote
1answer
29 views

Number of distinct equivalence classes of $\mathbb Z_n$ of the “ associate ” equivalence relation

Define an equivalence relation on $\mathbb Z_n$ as : For $a,b \in \mathbb Z_n $ , $a\sim b$ iff $\exists k \in U_n=\mathbb Z_n^{\times}$ such that $a=kb$ (i.e. $a,b$ are related if they are "...
5
votes
1answer
79 views

Upper bound on the minimum distance between $N$ points chosen inside the unit circle?

I guess this is a well-known problem but I'm not sure where to find it on the web. $N \ge 2$ points are chosen in the interior or the boundary of the unit circle. What is the best upper bound on the ...
2
votes
2answers
373 views

How many ways are there to distribute pens between two girls and one guy?

There are two girls and one guy and 121 pens. How many ways are there to distribute pens between two girls and one guy, so that the girls have the same number of pens. The pens all are identical. ...
-1
votes
0answers
70 views

Colouring a Tree

There are k different colors available. How many ways are there to color each vertex of the tree in one of the k colors such that for any pair of vertices having same color, all the vertices belonging ...
0
votes
0answers
14 views

Deduce Max flow min cut from Menger's theorem

I want to deduce the max flow min cut theorem from Menger's theorem, both on arc-connectivity in digraphs. Given a network with integer capacities c, one may replace each arc a by c(a) parallel arcs ...
1
vote
1answer
42 views

Summation of factorial.

$$2(\frac{1}{3!\times7!}+\frac{1}{1\times9!})+\frac{1}{5!\times5!}=\frac{2^a}{b!}$$ find $a,b$ by some predictions I see $b=10$ but what about numerator. I think we have to $\sum {N\choose r}=2^N$ but ...
1
vote
1answer
23 views

Finding number of subsets of set S that have r elements in common with set T

I've been going crazy trying to solve this. The question asks For some $0 \le r \le k \le n$, how many subsets of {1...n} have r elements in common with the set {1..k}. Describe two sets S and T such ...
-1
votes
0answers
31 views

Problem in solving a question of combinatorics. [duplicate]

In how many ways can $20$ indistinguishable pencils be distributed among four children $A$,$B$,$C$ and $D$ such that each children gets at least one pencil? My Work : At first I distribute $4$ ...
1
vote
2answers
71 views

In how many ways can $20$ indistinguishable pencils be distributed among four children $A$,$B$,$C$ and $D$? [closed]

In how many ways can $20$ indistinguishable pencils be distributed among four children $A$,$B$,$C$ and $D$? What is the actual technique for solving such problems?Please help me.
8
votes
3answers
199 views

Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$

Question: Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$ there exist two of them which share at least $r$ ...
1
vote
1answer
24 views

# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ...
1
vote
7answers
99 views

9 people sit in a row. 2 dressed in Red, 7 blue and 14 yellow. What is the P that at least 2 guys in yellow will sit next to a another in yellow?

1There are $\frac{21!}{2!3!} = 120$ total positions (disregarding order within same colour). I imagine labelling the people Y (yellow) and NY (not yellow), so I imagine I have $4$ copies of the letter ...
0
votes
1answer
42 views

Characterization of bicycle graphs

By "bicycle graph" I mean a minimal connected simple graph with at least two cycles. From Wikipedia: There are three possible types of bicycle: a theta graph has two vertices that are connected ...
15
votes
3answers
2k views

Minimum number of integer-sided squares needed to tile an $m$ by $n$ rectangle.

Let $T(m,n)$ for integers $m,n$ be the least number of integer-sided squares needed to tile an $m\times n$ rectangle. Clearly $T(kx,ky)\leq T(x,y)$. Are there integers $x,y,k\gt 1$, such that $T(kx,ky)...
0
votes
0answers
60 views

Does there exists a closed expression for the following sum? [closed]

Does there exists a closed expression for the following sum? $\sum_{i = 1}^n i {m \choose i}$
-1
votes
1answer
61 views

How many of the integers are multiples of $10$ or $9$ but not a multiple of $90$? [closed]

Good evening, dear people! Who can help me with this job? Among $410$ integers, $237$ are divisible by $10$, $137$ are multiples of $9$, $53$ are multiples of $100$, $111$ are multiples of $90$, $49$ ...
7
votes
3answers
143 views

How many integer solutions are there of the equation $|x_{1}|+|x_{2}|+\cdots +|x_{k}|=n$?

How many solutions are there to the equation $$|x_{1}|+|x_{2}|+\cdots +|x_{k}|=n$$ for $n,k\in \mathbb N$ and $\forall\ 1\leq i\leq k,\ x_{i}\in \mathbb Z$? Any ideas? I don't know how to ...
1
vote
2answers
526 views

Number of binary search trees on $n$ nodes of height up to $h$

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$? For example, if ...
0
votes
2answers
61 views

the sum of all four digit multiples of 6

The sum of all four digit multiples of $6$ is equal to: A. $8~274~489$ B. $8~247~498$ C. $8~241~996$ Can you help me with this question? I've tried $$S_n= \frac{n(a_1+a_n)}{2}$$ with $...
1
vote
4answers
90 views

Expected number of rolls

A fair m-sided dice is rolled and summed until the sum is at least N. What is the expected number of rolls? In other words what is the number of rolls if we roll a m-sided dice and the sum of rolls ...
25
votes
6answers
39k views

Combination of smartphones' pattern password

Have you ever seen this interface? Nowadays, it is used for locking smartphones. If you haven't, here is a short video on it. The rules for creating a pattern is as follows. We must use ...
3
votes
1answer
37 views

Uniqueness of graph neighbourhood sizes

I was thinking about graphs the other day, and had the following questions which I suppose fall under the topic of graph reconstruction. I am not very familiar with the literature, so in case this ...
0
votes
1answer
41 views

How to find the General expression of $\sum_{k=0}^ {\lfloor n/3\rfloor} {n \choose 3k}$ [duplicate]

Well as the title says I'm having problems trying to derive a general expression for this sum which involves cubic roots of unity $$\sum_{k=0}^ {\lfloor \frac n 3\rfloor} {n \choose 3k}$$ Need help ...
1
vote
1answer
37 views

Probability of picking balls with same color with replacement and without replacement

This is one of our probability exercise: We have an urn with m green balls and n yellow balls. Two balls are drawn at random. What is the probability that the two balls have the same color? (...
1
vote
1answer
85 views

Counting the number of partitions

Let $P$ be a set of $7$ different prime numbers and $C$ a set of $28$ different composite numbers each of which is a product of two (not necessarily different) numbers from $P$. The set $C$ is divided ...
1
vote
1answer
58 views

Proving a polynomial with binomial coefficients has non-real roots

I have the following family of polynomials: $$p_n(x) = \sum_{k=0}^n {n \choose k} \frac{n+2}{n+2-k} x^k$$ I conjecture that it has non-real roots for all $n \geq 2$. This holds for all the small ...
4
votes
3answers
77 views

Probability question - how many cycles before all items are chosen

I have a container of 100 yellow items. I choose 2 at random and paint each of them blue. I return the items to the container. If I repeat this process, on average how many cycles will I make ...
2
votes
1answer
434 views

Let $A$ be the set of all $4$ digit numbers $a_1a_2a_3a_4$ such that $a_1 < a_2 < a_3 < a_4$, then what is $n(A)$ equal to?

How can you solve this problem relatively quickly using combinatorics? I found it really interesting. Let $A$ be the set of all $4$ digit numbers $a_1a_2a_3a_4$ such that $a_1 < a_2 < a_3 < ...
1
vote
1answer
36 views

Finding the combination where p of the items are identical.

Suppose we have $n$ objects in which $p$ items are identical. Of course, $n-p$ elements are distinct. Then what is the combination of $n$ objects taken $r$ at a time? That is, what is $C(n,r)$, but ...
1
vote
0answers
58 views

What is the Star of David theorem?

I came across a MathWorld entry for the Star of David Theorem, but it doesn't provide much context. I have never heard of this before, can somebody explain its significance and any applications it ...
4
votes
1answer
64 views

Splitting Line Segments and Finding Expected Value

Consider a line segment which has a length of $2n-3$. It is split into $n$ segments at random. It is guaranteed that $n\ge 3$ and $n\in \mathbb{Z}$. These smaller lines are then used as the sides of a ...
0
votes
0answers
29 views

Counting balls in face centred cubic close packing

Possibly too easy for stack exchange, but... Consider a cubic close packing, or face centred cubic, arrangement of balls or radius $1$ in dimension $3$. Suppose that the origin is the centre of one ...
2
votes
2answers
110 views

Count the permutations which are products of exactly two disjoint cycles.

Let $a_n$ be the number of those permutation $\sigma $ on $\{1,2,...,n\}$ such that $\sigma $ is a product of exactly two disjoint cycles. Then find $a_4$ and $a_5$. Calculating $a_4$: Possible ...
-1
votes
3answers
111 views

Number of permutations which are products of exactly two disjoint cycles. [duplicate]

Let $l_{n}$ denote the number of those permutations $f$ on the set $A=\{1,2,....,n\}$ such that $f$ is the product of exactly two disjoint cycles. Show that $l_{5}=50.$ I tried a lot but reached ...
0
votes
0answers
23 views

Tight lower bound on falling factorial

I have the term $$p=\left(\frac{1}{n-b}\right)^a\cdot[n]_a, 0<b<a,\ b \in \mathbb{R} \text{ fixed}$$ and want to find a tight lower bound such that I will then be able to solve for n. For ...