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

Question on counting

If 8 identical whiteboards must be divided among 4 schools, how many divisions are possible? For this, the answer is 11C3, and I know this is obtained using stars and bars counting method. However, ...
0
votes
5answers
218 views

How many non-ordered quadruples satisfy $a+b+c+d=18$?

How many non-ordered quadruples satisfy $a+b+c+d=18$? I know how to do this if this is ordered quadruples, but in non-ordered quadruples $(1,1,1,15)$ is the same as $(15,1,1,1)$ so you have to ...
1
vote
1answer
195 views

Number of ordered pairs $(x,y)$ of positive integers such that $x+y=90$ and their GCD is $6$

The number of ordered pairs $(x,y)$ of positive integers such that $x+y=90$ and their greatest common divisor is $6$ equals $8$. But I did this way: As $x$ and $y$ both are divisible by $6$, so let $...
1
vote
1answer
23 views

Probability of winning after x coin tossses

I'm not sure how to reason about this problem. Say we toss 12 coins in a row. What is the probability that 7 of those tosses were heads, and five were tails? I've tried thinking of it as the number ...
1
vote
1answer
190 views

How many symmetric and transitive relations are there on ${1,2,3}$?

I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one. I've counted ...
0
votes
1answer
144 views

Round table exponential generating function

Let $r(n)$ be the number of different ways to seat $n$ people around a round table. Find the exponential generating function for $r$. I believe $r(n)$ is just equal to $n!/n = (n-1)!$. So then I ...
1
vote
2answers
168 views

“Relatively Close” Soccer Game

A soccer game between 2 teams is "relatively close" if the scores never differ by more than 2. In how many ways can the game be "relatively close" for the first 12 goals? Just to clear it up, the ...
1
vote
1answer
109 views

Probability: 30 balls in a bucket, homework

i need some help with some homework, first time i am doing probability and statistics, id like to know if my 2 answers below are correct, and how i can solve the remaining 2. There are 30 balls in a ...
0
votes
0answers
70 views

Proportional growing number set $\mathbb{X}\subset\mathbb{N}$

1. Question: Is there such a set of numbers $\mathbb{X}\subset\mathbb{N}$, in which the proportion of product and sum of all natural numbers $n\in \mathbb{N}$ grow proportional? $$\begin{equation*} f(...
1
vote
1answer
61 views

Simplifying Sum of Subsets

Given sets $A$ and $R$ such that $R \subseteq A$ and a number $x \leq |A|$, I am trying to simplify the following sum: $$\begin{equation*} \sum_{R \subseteq W \subseteq A : |W| = x} \Big( \sum_{Y \...
0
votes
1answer
171 views

Combinatorial proofs - how?

I'm suppose to proof the following with combinatorial proofs. 1)$$\sum_{i=0}^{n} {a+i \choose i} = {a+n+1 \choose n}$$ 2)$$\sum_{i=0}^{n} i{n \choose i} = n2^{n-1}$$ 3)$$\sum_{i=0}^{n} {n \choose i}...
1
vote
1answer
50 views

Advice on proving a tricky inequality

Im a little out of my depth here and am not well versed in combinatorics. Im not sure if this problem is too hard to solve or if there exists well known results to prove it. Here is part 1 which might ...
2
votes
1answer
103 views

How to answer the following question related to counting the number of trees of a graph?

I am asked to prove the equality $$ 2(n-1)n^{n-2} = \sum_{k=1}^{n-1} \binom{n}{k} k(n-k)T(k)T(n-k) , $$ where $T(k)$ is the number of different trees with $k$ numbered vertices. I think the ...
11
votes
6answers
817 views

Book on combinatorial identities

Do you know any good book that deals extensively with identities obtained using combinatorial and/or probabilistic arguments (e.g., by solving the same combinatorial or probability problem in two ...
2
votes
1answer
1k views

Pigeonhole Principle Question: Given any 5 points inside a square of side length 2, there is always a pair whose distance apart is at most $\sqrt2$

The question I am looking at: Prove that given 5 points inside a square of side length 2, it is always possible to find two of them whose distance apart is at most $\sqrt2$. This looks to me like I ...
0
votes
1answer
63 views

How many ways are there to arrange the train?

There are $14$ intermediate stations between city $A$ and city $B$ on a rail track. A train is to be arranged from $A$ to $B$ so that it halts at exactly $3$ intermediate stations, no two of which ...
0
votes
2answers
276 views

Problem with Set Theory Counting Principle

I'm trying to apply the counting principle to the following: "Of 300 people: 35 - bicycle and car. 40 - car and bus. 60 - bicycle and bus. 90 - bicycle. 70 - car. 105 - bus. 25 - bicycle, car, and ...
3
votes
5answers
85 views

How to find the coefficient of $x^8$ in $\prod\limits_{i=1}^{10}{\left(x-i\right)}$?

How to find the coefficient of $x^8$ in $(x-1) (x-2) . . .(x-10)$. Is there any general formula to solve this kind of problems?
0
votes
1answer
97 views

How to use burnside lemma?

How would you use burnside lemma to find the number of circular arrangements possible of 2 blue items, 2 red items, and 3 yellow items assuming that items of same color are indistinguishable? I ...
4
votes
0answers
112 views

Multiplicative subgroup of a finite field with prescribed trace.

Any suggestions/methods/estimates for the following problem would be very appreciated. $l,p$ are primes with $p \equiv 1 \!\! \pmod l$. $r$ is a positive integer with $r \equiv 1 \!\! \pmod p$ and $q ...
0
votes
1answer
41 views

Throw 3 balls into 3 bins find range, distribution, and partition based on following information

There are 3 indistinguishable balls and 3 distinguishable bins. Let random variable X = #balls in bin 1 and random variable N = #occupied bins Range(X) = {0,1,2,3} Range(N) = {1,2,3} A0 = No balls ...
0
votes
1answer
72 views

Combination of Combinations

I am working on solving a problem involving groups of combinations. For example, There are 25 males and 25 females involved in a study. Eight people are expected to be selected for this study. What ...
2
votes
1answer
70 views

Binomial coefficients inequality

It seems to me that there should be a simple way to prove that $$ \binom{n}{s+1+a} + \binom{n}{a} \leq \binom{n}{s} $$ For $s > n/2$ and $a < n-s$. However it looks like I'm missing it. Any ...
2
votes
2answers
468 views

Arranging indistinguishable objects in a circle

A senate committee has 5 democrats and 5 republicans. Each of the democrats and republicans are indistinguishable from the other democrats and republicans respectively. In how many ways can they sit ...
2
votes
2answers
2k views

Show how the probability that an 8 character password contains exactly 1 OR 2 integers is .630

A password is 8 characters long. Each character can contain 26 lower case or 26 uppercase letters or a integer from 0-9. What is the probability that an 8 character password contains exactly 1 OR 2 ...
0
votes
1answer
53 views

Count the number of ways of painting the strip with 3 colors

How many ways there are to paint the strip of N cells, using NOT LESS than A yellow cells, B red cells, C blue cells? I found similar question, but my case is different How many ways there are to ...
0
votes
2answers
72 views

A problem about irrational number

I'm dealing with the following problem: By using piegonhole principal, prove that for any positive irrational number $r$ and positive real numbers $x,y \in \left( {0,1} \right)$, $x < y$, there ...
1
vote
1answer
58 views

How many ways there are to paint the strip of n cells with 3 colors

How many ways there are to paint the strip of N cells, using R red cells, B blue cells, <...
1
vote
0answers
169 views

Minimum Number of Possible Combinations to Predict Results of Double-Outcome Events

There are "n" different events. Each event can result in two possible outcomes (ie Yes or No). You make a guess for each event and list this (ie YYNYYNN for 7 events). To guarentee to correctly guess "...
1
vote
1answer
29 views

Quartets and parity

There are 229 girls and 271 boys at a school. They are divided into 10 groups of 50 students each, with numbering 1 to 50 in each group. A quartet consists of4 students from 2 different groups so that ...
0
votes
1answer
77 views

How many ways can this quadrilateral be formed if no two of its vertices are next to each other?

A quadrilateral is formed by joining four vertices of a convex decagon. In how many ways can such a quadrilateral be formed if no two of its vertices are next to each other (that is, no two vertices ...
3
votes
2answers
49 views

How is this exactly equal to $N_1+N_2+\dots+N_r$?

There are $N$ boxes, each containing at most $r$ balls. If the number of boxes containing at least $i$ balls is $N_i$ for $i=1,2,\dots,r,$ then the total number of balls contained in these $N$ boxes ...
1
vote
1answer
394 views

a spider has 1 sock and 1 shoe for each leg. then find out the the total possibilities.

a spider has one sock and one shoe for each of its 8 legs.in how many different orders can the spider put on its shocks and shoes; assuming that on each leg ;the shock must be put on before the shoe? ...
1
vote
2answers
235 views

How many balls here can't be in the bag?

A bag contains colored balls of which at least $90\%$ are red. Balls are drawn from the bag one by one and their color noted. It is found that $49$ of the first $50$ balls drawn are red. Thereafter $7$...
4
votes
1answer
129 views

Counting Periodic Orbits on a regular Hexagon

An orbit on a polygon is a path that a "billiards ball" (a point) would follow if it obeyed Snell's law of reflection (the angle of incidence is equal to the angle of reflection). A periodic orbit is ...
0
votes
1answer
63 views

maximal independent set in a graph

Let $G$ be a graph and $A$ is a subset of vertex set of $G$. $A$ is said to be independent if for any $x, y \in A$, $(x,y) \notin E(G)$, i.e $x$ and $y$ not connected by an edge. Further A is said to ...
1
vote
1answer
1k views

How many n-digit numbers contain at least one 2 and at least one 3, but no 7’s?

Additional rule: each digit is one of $\{0,1,2...9\}$ and the first digit is nonzero. I think this question isn't hard, I just don't seem to be clear about the question. My interpretation: How many ...
2
votes
1answer
1k views

Number of 5 letter words with at least two consecutive letters same

How many 5-letter words have at least two consecutive letters which are the same? I tried to break this up into the following cases: 2 consecutive letters same: $4*26*1*25^3$ 3 consecutive ...
2
votes
1answer
136 views

Characterizing a certain set of matrices arising from binary trees

Suppose I have a binary tree, like v1 v4 \ / -------- / \ v2 v3 I can write a matrix for this tree whose $(i,j)$th ...
1
vote
1answer
320 views

Paths on a Rubik's cube

Here is the Question i'm trying to solve: An ant is initially positioned at one corner of the Rubik's cube and wishes to go to the farthest corner of the block from its initial position. Assuming ...
3
votes
3answers
2k views

Number of ways to form a 3-letter word with repetition allowed?

The additional rule is: no letter can be used more often than it appears in MILLENNIUM? (Which is pretty logical I guess) MILLENNIUM = MM, II, LL, NN, E, U My logic: Case 1: Double letters + 1 ...
0
votes
2answers
260 views

No. of 5-digit monotonic numbers

The monotonic number is made of digits 1, 2, …, 9, such that each subsequent number equal to or greater than the previous number. Examples: 11119, 12369, 18999 etc. I understand that I can isolate ...
1
vote
1answer
71 views

Combinatorics Parity Problem

There are 229 girls and 271 boys at a school. They are divided into 10 groups of 50 students each, with numbering 1 to 50 in each group. A quartet consists of4 students from 2 different groups so that ...
14
votes
1answer
66k views

How many possible combinations in 8 character password?

I need to calculate the possible combinations for 8 characters password. The password must contain at least one of the following: (lower case letters, upper case letters, digits, punctuations, special ...
0
votes
1answer
91 views

Count Integers satisfying the conditions

Given some constraints ,I need to find possible ways that these conditions are satisfied. I need to find four POSITIVE integers a,b,c,d such that ad-bc > 0 and also a+d=N for a given value of N. How ...
1
vote
1answer
754 views

bijection between lattice path and permutations

I am studying Viennot's combinatorial model for the Laguerre polynomials this semester under the guidance of my math professor. If I understand correctly, a bijection exists between the number of ...
1
vote
1answer
164 views

Number of permutations of AABBBCC, taking 7 letters at a time, when repititions are allowed

What is the number of permutations of the word AABBBCC, taking 7 letters at a time, repetitions being allowed? I think it should be $3^7$, but I can't see why. Also what would be the number of ...
1
vote
2answers
180 views

A combinatorics question on a $n \times n$ grid

In the book 'Foundations of Data Science' by Hopcroft and Kannan, they have the following exercise (Ex. 5.46): Let G be a $n \times n$ lattice and let $S$ be a subset of $G$ with cardinality at ...
2
votes
0answers
39 views

How many commutative block ciphers are there?

Let $K$ and $M$ and be two finite sets. Let $(G,\circ)$ be the group of permutations over $M$ under composition. Let a (implicitly: block) cipher with key in $K$ and message in $M$ be any application $...
2
votes
0answers
115 views

A probability problem with multivariate Gaussian distribution

I am a computer science guy, not a mathematician so kindly excuse me if there is any ridiculous error in my problem description. I have two clusters $C_1$ and $C_2$ in a feature space spanned by $k$ ...