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

n points permuted on a circle

Here is a combinatorics problem that bothers me a lot. I am looking forward to a quick reply. Thanks in advance. Here goes the problem. Initially there are $n$ points on a circle. We do permutation to ...
6
votes
3answers
14k views

How Many Symmetric Relations on a Finite Set?

How many symmetric relations are there for an $n$-element set? Thank you.
1
vote
1answer
67 views

Exact Expected Value of Random Walk?

i just read in Noga Alon's Book That the exact expected value of a random walk is which was a question in putnam competition... Sn=X1+X2+...Xn Which Xi are independent uniform random in {-1,+1} ...
3
votes
1answer
42 views

Is there a “balanced knapsacks” problem with a known result?

You're going on a trip with some friends and want to share the load of the camping gear as evenly as possible. Each of you is equally strong, and each of your knapsacks is identical. Can the fairest ...
0
votes
1answer
46 views

Work and efficiency puzzle

There are $2$ people $A$ and $B$. $A$ requires $a\;$ days to complete certain amount of work and $B$ requires $b\;$ days to complete the same amount of work. If $A$ begins the work a day before $B$ ...
4
votes
2answers
63 views

Let $S$ be a set consisting of all positive integers less than or equal to $100$.

Let $S$ be a set consisting of all positive integers less than or equal to $100$. Let $P$ be a subset of $S$ such that there do not exist two elements $x,y\in P$ such that $x=2y$. Find the maximum ...
1
vote
1answer
29 views

Catalan Sequence on a Circle

A Catalan sequence of length $2n$ is a sequence of $1$'s and $0$'s such that no initial segment of the sequence has more $0$'s than $1$'s. The number of such sequences is given by the Catalan number ...
4
votes
2answers
43 views

Hall's marriage thereom with max-flow-min-cut

I heard that Hall's marriage theorem can be proved by the max-flow-min-cut theorem. Could you outline how that is possible? Hall's theorem says that in a bipartite graph there exists a complete ...
1
vote
1answer
35 views

Hamming's code is perfect

How does one prove that Hamming's code is perfect (i.e. it is the 1-error correcting code that has the smallest possible size). I haven't found a complete proof using Google.
1
vote
1answer
143 views

Combinatorial proof for $\sum_{i=r}^{n}(2i-r)\binom{i-1}{r-1}^2=r\binom{n}{r}^2$

I cfound the following identity, but I'm having trouble finding a combinatorial interpretation. Can someone help me? $$\sum_{i=r}^{n}(2i-r)\binom{i-1}{r-1}^2=r\binom{n}{r}^2$$
5
votes
6answers
1k views

How many different ways can I get up a flight (of stairs) with 11 steps?

You can climb either $1$ or $2$ stairs at a time, at any given time. How many ways can you get up $11$ stairs? I've tried using different cases to solve this. So I did: Case 1: All $1$ steps --> $...
0
votes
2answers
57 views

How many different chains in a Poset? [duplicate]

I found that problem and I could use some help. I have a partial order $(2^S,⊆)$ and |S| = n. How many different chains are there in that poset? If I had the Hasse diagram or knew the ...
6
votes
1answer
120 views

Picking pairs of socks from a drawer.

There are $n$ socks in a drawer, of $m$ different colours. Initially, the probability of picking a sock of colour $c_i$ at random is $\mathbb{P}(c_i) \cdot 2r$ socks are picked at random, without ...
0
votes
1answer
41 views

Partial sums of periodic sequences

Let $a_i$,$b_i$ be two periodic real sequences with a period of $n$. For $k\leq n$, denote the $k$-length partial-sums starting at $j$ by $a[j:k],b[j:k]$, i.e: $$a[j:k] = \sum_{i=j}^{j+k-1}a_i\,\,\,\,\...
13
votes
9answers
929 views

Probability: 10th ball is blue

The following is a question I've made myself, but I need help in solving it: Suppose there are 100 balls in a box. 20 balls are blue, 30 balls are green and 50 balls are yellow. Now we randomly pick ...
0
votes
1answer
36 views

Rough equivalence of integer lattices?

Above is shown the meaning of having two resistive networks being roughly embedded. Roughly equivalent means there is rough embeddings both ways. I wish to show that this distinguishes $\mathbb{Z}^d$...
1
vote
1answer
611 views

MISSISSIPPI combinations with the S's separated

How many combinations are there to arrange the letters in MISSISSIPPI requiring that the 2 S's must be separated? I found there are 34650 combinations to arrange without restriction. How to ...
0
votes
1answer
474 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
2
votes
4answers
897 views

Arranging the word 'MISSISSIPPI'

"How many ways are there to arrange the letters in the word 'MISSISSIPPI' in such a way that there are no three consonants in a row?" I am thinking like this. The following are 'slots' for the ...
0
votes
0answers
32 views

How many passwords are possible if the characters may be used more than once? [closed]

I've solved the first two, the only information needed is the password must be 7 characters in length. What I think is for each slot a character may be repeated more than once in any spot. We only ...
0
votes
2answers
36 views

Expected value of colors picked from basket

I have a basket with 4 balls with different colors. What is the expected value of distinct colors I can see after picking 4 times from bin. I return the ball back after each try. I tried computing ...
0
votes
1answer
43 views

Probability book choosing questions

So I am doing homework and have the following question If 3 books are picked at random from a shelf containing 5 novels, 3 books of poems, and a dictionary. What is the probability that (a) the ...
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 ...
1
vote
0answers
70 views

Maximal unit lengths in 3D with $n$ points.

Given $n$ points in 3D space (V), what is the maximal number of unit distance lengths (E) between those points? Here are a few possibilities. Some of them are chromatic spindles. ...
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
47 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
146 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
83 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
78 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
372 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
197 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, ...