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

Why doesn't this alternative method work? Chance of getting four of a kind in a hand of $5$ cards?

Please note: This is not a duplicate since it is asking about an alternative method of solving the question What is the probability of getting four of a kind in a hand of $5$ cards from a standard ...
3
votes
2answers
106 views

Find all solutions to $2 x + 3 y + 4 z = 10$

I do not have a background in math, and am wondering what type of question this is. I looked combinatorics optimization, and the knapsack problem, but found the vocabulary too dense. The problem: ...
0
votes
3answers
84 views

How many ways are there to choose 5 ice cream cones if there are 10 flavors?

I had this on a test and I gave answer as: (10 C 5) but it was incorrect. Why? Isn't this just a typical combination problem where you select 5 objects of 10 objects! Correct answer: $_{(10+5−1)}C_{ ...
-1
votes
3answers
51 views

Suppose that an ice-cream café has 10 different flavors of ice cream. [closed]

In how many different ways one can choose 3 scoops of ice-cream, so that order of flavors does not matter?
5
votes
1answer
62 views

On “good” numbers and $m \times n$ real matrices

Let $m,n > 1$ be odd integers. Different real numbers are written in the cells of the $m \times n$ table ($m$ rows and $n$ columns). The number is called "good" if 1) It is the largest in its ...
2
votes
1answer
33 views

Can't understand one chance in R of winning where R is some result of factorials.

In lotto game, let you select six no. from 51 no. on a card and the Lotto managers pick six no. at random. If your choice exactly matches theirs, you win a few dollars. If you have to pick 6 values ...
2
votes
0answers
40 views

The number of partitions of $n$…Subbarao

(Subbarao) The number of partitions of $n$ in which each part appears two, three, or five times equals the number of partitions of $n$ into parts congruent to $2, 3, 6, 9,$ or $10$ modulo $12$. ...
6
votes
3answers
58 views

In how many ways can an inspector visit $4$ normal sites and $1$ “suspicious” one?

I cannot figure out why my answer to the following question is wrong: Suppose that a weapons inspector must inspect each of five different sites twice, visiting one site per day. The inspector is ...
0
votes
3answers
31 views

Find the number of all possible valuations that will satisfy given expression.

This part concerns the 256 possible truth valuations of the following eight propositional letters A, B, C, D, E, F, G, H. For each of the following expressions, say how many of the 256 valuations ...
0
votes
1answer
31 views

Committee selection problem

The problem goes as follows: A committee of $7$ is to be formed from $9$ boys and $4$ girls. In how many ways can this be done when the committee consists of 1. At least $3$ girls? 2. ...
1
vote
1answer
18 views

What's the formula to map between multiindices and indices?

What is the formula to map between multiindices and indices? By multiindex, I mean a variable $I\in\mathbb{N}^d$ where $|I|=\sum\limits_{i=1}^d I_i=n$. Here, $d$ denotes the dimension. Basically, ...
2
votes
1answer
24 views

How many ways can a committee of six be made from 4 students and 8 teachers if the committee contains at least three students?

How many ways can a committee of six be made from 4 students and 8 teachers if the committee contains at least three students? The obvious answer would be to select 3 students and 3 teachers or 4 ...
1
vote
1answer
25 views

Number of monotonic paths in a rectangular grid avoiding certain points

In a rectangular grid of size $m \times n$, the number of paths from $(0,0)$ to $(m,n)$ (without backtracking) is ${m+n \choose {n}} = \frac{(m+n)!}{(m!*n!)}$. Now if there are certain points in the ...
1
vote
1answer
36 views

How many distinct directed acyclic graphs are there?

Given $|V|=4$ and $|E|=3$, how many distinct directed acyclic graphs can be formed? Isomorphic graphs should be counted as one. There is one where three periphery nodes point to a central node. ...
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
64 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 ...
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 ...
0
votes
1answer
47 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$ ...
1
vote
1answer
70 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
58 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 ...
0
votes
1answer
42 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\,\,\,\,\...
0
votes
1answer
44 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 ...
0
votes
2answers
38 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 ...
3
votes
1answer
52 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
52 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
49 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 ...
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 ...
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?
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 ...
0
votes
2answers
47 views

No of integral solutions to an equation confusion?

For an equation like ${ x }_{ 1 }+{ x }_{ 2 }+{ x }_{ 3 }=60$, I am seeing that in some books they are using $( (60 + 4 - 1) C (4) )$ as solution whereas in some book they are using $( (60 + 4 - 1) C (...
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$ ...
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?
7
votes
4answers
149 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.)
1
vote
1answer
46 views

Notation for probability: $C_n^r$, $P_n^r$, $A_n^r$?

I was told that $C^{n}_{k}$ refers to combinations or choose k elements from n elements, $\bar{C^{n}_{k}}$ refers to combinations with repetitions (i.e. $C^{n+k-1}_{k}$), and $P^{n}_{k}$ refers to ...
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}$ ...
-1
votes
0answers
71 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 ...
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
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 ...
2
votes
2answers
374 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
vote
1answer
30 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 "...
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
27 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.
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
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$ ...
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
2answers
62 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 $...
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 ...