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
2answers
47 views

Prove that a graph has a cycle of length no more than $14$

A graph contains $2016$ vertices, its chromatic number is $5$, prove that this graph has a cycle of length $\leq 14$. Where do I start?
0
votes
1answer
764 views

Probability of Obtaining A Particular Sum from Successive Dice Rolls

Suppose you have a regular die with 6 faces numbered 1 through 6, respectively, and roll the die 4 times. What is the probability that the sum of the 4 rolls is 14? This problem is equivalent to ...
1
vote
0answers
31 views

The relation between Weyl character formula and Frobenius characteristic map

Let $\mathfrak{gl}(n)$ be the general linear Lie algebra of rank $n$, and $\mathfrak{S}_d$ be the symmetric group of rank $d$. It is well-known that the Schur-Weyl duality provide a equivalence ...
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 ...
5
votes
5answers
88 views

How to find number of solutions of an equation?

Given $n$, how to count the number of solutions to the equation $$x + 2y + 2z = n$$ where $x, y, z, n$ are non-negative integers?
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, ...
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 (...
4
votes
3answers
572 views

Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
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 ...
1
vote
1answer
43 views

Subtle Sample Space

I have been self-studying probability and statistics using Sheldon Ross's "A First Course in Probability" for a while, yet I still have problems on recognizing sample spaces in some probability ...
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_{ ...
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. ...
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 ...
-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?
3
votes
1answer
2k views

hat matching problem (Ross, p.41)

I'm studying Ross's probability book, and kind of got stuck on the matching problem. Suppose that each of $N$ men at a party throws his hat into the center of the room. The hats are first mixed up, ...
4
votes
1answer
93 views

Probabilistic method: vertex disjoint cycles in digraphs

Let us say that a di-graph is $k$-regular if every vertex has precisely $k$ out-edges. The following theorem appears in a book I am currently studying Theorem. Every $k$-regular graph $D$ has a ...
1
vote
3answers
348 views

Three meetings where each attends exactly two

Suppose three meetings of a group of professors were arranged in Mumbai, Delhi and Chennai. Each professor of the group attended exactly two meetings. $21$ professors attended Mumbai meeting, $27$ ...
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 ...
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$. ...
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
2answers
36 views

How many ways are there to distribute $2$ indistinguishable white and $4$ indistinguishable black balls into $4$ indistinguishable boxes?

How many ways are there to distribute $2$ indistinguishable white and $4$ indistinguishable black balls into $4$ indistinguishable boxes? If the question was asked as "distinct boxes", I can solve. ...
0
votes
2answers
112 views

Round table seating - expected value

There are $p$ women, $s$ men and $p+s$ seats in a round table. Let $X$ be the number of women who sit between two men. Find the expected value of $X$. I know that expected value of $X$ is given by ...
0
votes
2answers
133 views

Some men and women are randomly assigned seats at a round table and no two persons of the same sex are seated next to each other. Probability of this?

Four women and four men are assigned seats at random at a round table. what is the probability that no two persons of the same sex will be sitting next to each other?
0
votes
0answers
270 views

seating at two round tables

We have $n$ people sitting in two round tables like the picture. We randomly change the place of the people we decide two of them and change their places. We can only change the place of the ...
0
votes
1answer
65 views

How do I calculate all possible combinations for a player creator in a game?

I'm currently working on a character creator for a game, but I don't know how to calculate all possible character combinations the player can create. In the creator, the player is required to choose ...
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
3answers
41 views

Number of ways to partition a set with $2n$ elements

In how many ways can I partition $S = \{1,2,\cdots,2n\}$ into $n$ disjoint $2$ element subsets. Suppose if I subsets of $S$ were $S_{1},S_{2},\cdots,S_{n}$, then I can choose $S_{1}$ in $\binom{2n}{2}$...
1
vote
3answers
66 views

Number of non-negative distinct integer solutions of $x+y+z+w=10$

I understand that there are already many questions relating to this, but my question is regarding some concept of mine that should be working but doesn't produce the right result. So, I follow an ...
2
votes
4answers
333 views

Distributing Objects into Boxes (Discrete Mathematics)

I am trying to solve this question: "How many ways are there to pack eight identical DVDs into five indistinguishable boxes so that each box contains at least one DVD?" I am very lost at trying to ...
0
votes
4answers
75 views

How many $3$ member subsets $\{x, y, z\}$ of positive natural numbers have the sum $x + y + z = 100$?

I have a math homework problem where I think I have to use Permutation/Combination. The question is: How many $3$ member subsets $\{x, y, z\}$ of positive natural numbers have the sum $x + y + z = ...
2
votes
4answers
97 views

Number of positive unordered integral solutions

What are the number of positive unordered integral solutions for $a+b+c=36$ Solution given is $108.$.But I am getting $91$ as $$\frac{\binom{35}2-3\times16-1}{3!}.$$ $3\times16($ for $a=b$ cases and ...
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 ...
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 ...
6
votes
3answers
15k 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
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
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
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$ ...
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 ...
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
144 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
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\,\,\,\,\...
13
votes
9answers
931 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 ...
1
vote
1answer
39 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
616 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 ...