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
1answer
24 views

Number of subsets of $\{0,1,2,…,9\}$ with symmetric difference $\leq 2$

There is a problem asking to prove that among any 100 subsets of $\{0, 2, 3, \dots , 9\}$ there will be two with cardinality of their symmetric difference less than or equal to two. It is proven by ...
0
votes
1answer
20 views

Solving a series in the proof of the expectation of the binomial distribution

I am studying the expectations and variances of the most common distributions. For the binomial distribution the mean is equal to $np$. Considering $p$ and $q$ independent variables and ...
4
votes
5answers
49 views

Counting clarification

In the text I am reading there's a question: From the digits $0, 1, 2, 3, 4, 5, 6$, how many four-digit numbers with distinct digits can be constructed? How many of these are even numbers? I get the ...
2
votes
0answers
26 views

Maximum independent sets of $k$-partite graphs

Consider a $k$-partite graph $G=(V,E)$. This means that its vertices can be partitioned into $k$ different independent sets, say $V_1,\dots, V_k$. Assume further that $|V_1|=\dots = |V_k|$. Under ...
31
votes
7answers
18k views

What is the math behind the game Spot It?

I just purchased the game Spot It. As per this site, the structure of the game is as follows: Game has 55 round playing cards. Each card has eight randomly placed symbols. There are a total of 50 ...
3
votes
2answers
97 views

Prove ten objects can be divided into two groups that balances each other when placed on the two pans of balance. [closed]

There are 10 objects with total weight 20, each of the weight being a positive integer. Given that none of the weights exceed 10, prove ten objects can be divided into two groups that balances each ...
0
votes
2answers
46 views

How many 2 digit even numbers can be formed from these numbers?

How many even 2 digit numbers can be formed from the numbers 3,4,5,6,7? The digits cannot repeat (you can't have 44 or 66 for example). I know the answer to this is 8, because I just wrote them all ...
1
vote
2answers
73 views

combinatorics contest problem

Question: Calvin has a bag containing $50$ red balls, $50$ blue balls, and $30$ yellow balls. Given that after pulling out 65 balls at random (without replacement), he has pulled out $5$ more red ...
6
votes
0answers
80 views
+50

Does there exists a positive $t$ that satisfy this given condition?

I am curious about the validity of my claim concerning the equations: $(2k-1)t+1$ (1) $(2k^2-2k)t+(2k-1)$ (2) where $k=2,3,4,...$ My claim is for almost all $k$ or for infinitely many $k$, there ...
1
vote
2answers
47 views

How many dice would I need to get an $n$ of a kind 100% of the time?

For example, if I wanted to get two of a kind, I would need seven dice. This is because even if the first six were 1, 2, 3, 4, 5, 6, the next one would have to make a pair out of the previous dice. ...
1
vote
2answers
42 views

how many ways to partition a set with k subsets, each of fixed size?

if $(v_1,...,v_k)$ is a partition of $n$, how many ways $M((v_1,...,v_k),n)$ is there to create a set (partition) of $k$ elements, each of size $v_i$ , i=1,...,k from $n \geq k$ distinct elements ? ...
1
vote
1answer
37 views

Proof Bell-Number $B(n+1)=\sum\limits_{i=0}^n\binom{n}{i}B(i)$

Let B(0) := 1 und B(n) for n$\geq$1 the counts of all sets partitions of [n]. The numbers B(n) are the Bell-numbers. For $n \geq 0$ prove that: \begin{equation} ...
1
vote
1answer
38 views

How many class schedules are possible?

You have $5$ choices of a math class, $2$ choices of history class, and $6$ choices of writing class. If you are planning to take one of each class, how many possible schedules could you have? What I ...
1
vote
1answer
33 views

Closed formula for ordinary power series generating function

To find the ordinary power series generating function of $\left\{\frac{1}{n+1}\right\}_2^\infty$, I tried to solve it like this, let $$\begin{align} f &= \frac{x^{n-2}}{n+1}, \text{ where }n \ge ...
-1
votes
1answer
50 views

prove $\sum \limits_{k=1}^n A(n,k){x+k-1 \choose n}=x^n$

A descent in the permutation $\sigma = a_1 \cdots a_n \in S_n$ is an index $i\in[n-1$] for which $a_i > a_{i+1}$. Let A(n, k) be the number of permutations of $[n]$ with $k-1$ descents where $n ...
0
votes
0answers
39 views

A Good book for Combinatorial Theory

I am looking for a good book on Elementary Combinatorics (Olympiad level). For some reason I do not like Lint. I am currently reading "A Walk Through Combinatorics" by Miklos Bona and I find it really ...
1
vote
1answer
22 views

Incomplete beta integral

Let n be greater than one, and B be the beta integral, $$\sum _{j=0}^{\infty } C_j B_{\frac{1}{n}}(j+1,j+2)=\frac{1}{n}$$ Is it correct to call this an inversion formula? What possible ideas are ...
1
vote
1answer
38 views

Combinations for pairing groups

I have a little bit of a complex question and I don't know anything about combinatorics, but I'm working on software problem and I'm trying to figure out how my algorithm will scale. I'm having to ask ...
3
votes
0answers
40 views

Is there an established notation for this “replacement” operation?

If $S$ is a set, define $$(x \to y) \cdot S := \begin{cases} (S \setminus \{x\}) \cup \{y\} & \text{ if } x \in S \text{ and } y \not \in S; \\ S & \text{ otherwise.} \end{cases}$$ In other ...
1
vote
1answer
3k views

Counting overlapping figures

How many four-sided figures appear in the diagram below? I tired counting all the rectangles I could see, but that didn't work. How do I approach this?
1
vote
5answers
108 views

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000$.

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000.$ My attempt: False, Let set $z = \{1,2,3\}$ then $|z|^{|x|}$ is set of function $y:x\to z.$ $|x| = n$ and $|z| = ...
3
votes
2answers
97 views

Reducing the form of $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$.

I've been toying around with simplifying the expression $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$ (for integer only $n$) for a while, as I was hoping it ...
0
votes
0answers
15 views

Size of remaining search space for Vehicle Routing Problem given a partial solution

The vehicle routing problem is a NP-hard problem that, in its most basic form, involves scheduling routes for v vehicles that have to make n deliveries in total. So a solution (schedule) has the form ...
1
vote
3answers
28 views

Probability of choosing two bulbs with the same rating given that one has a specific rating

I am trying to teach myself statistics, and working through Jay DeVore's excellent text of "Probability and Statistics for Engineering and the Sciences". The problem is as follows: We have box of the ...
0
votes
1answer
32 views

Counting Positive Integer Divisors

Let $A$ be the set of all positive integer divisors of $3^6 5^8 11^{10} 17^{15}$. Define the relation $R$ on $A$ as follows. For $x, y \in A, xRy$ when $x | y$. Determine the number of ordered pairs ...
1
vote
1answer
27 views

Determining how many combinations there are when every item has a pair it can't exist with.

If we had 25 people all who have 2 different balls, how would you work out how many combinations there would be if we want to choose 25 balls, but no person can have both of their balls in the choice? ...
1
vote
1answer
266 views

How many different ways are there to organize 2 groups?

In how many different ways can you split 10 people into two groups with the same amount of people? My attempt: Since the order in which you choose someone doesn't matter, I chose to calculate the ...
0
votes
1answer
28 views

What is maximum value of “m” for following equation?

QUESTION: What is maximum value of "m" for following equation? $$\Sigma\ (^{10}C_i)( ^{20}C_{m-i})$$ where i is from 0 to m. (A) 5 (B) 10 (C) 15 (D) 20 MY ATTEMPT: I have written equation as, ...
0
votes
0answers
103 views

Combinatorial algorithm problem of a symmetric matrix.

Given a matrix A of a strongly $k $ regular graph G(srg($n,k,\lambda ,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $ ...
-1
votes
1answer
25 views

College Students Seated at a Dinner Table [on hold]

A group of college students are going to a party. They are all sitting at the dinner table. Suppose that: There are $7$ girls who have a girl on their right side $12$ girls who have a guy on their ...
5
votes
3answers
76 views

Suppose a city with Three type of coins ?!

in a city we have tree type 1 dollar, 2 dollar, 3 dollar of coins. we want to pay for a 20 dollar product. how many ways we can pay for a 20 dollar product, if the seller has no money and number of 1 ...
1
vote
0answers
64 views

Simple $\{-1,0,1\}$ equation set

I'm trying to find the shortest path, getting from $x=0$ to $x=k$ in a certain problem, where I can slowly accelerate and decelerate. It comes down to finding the smallest $n$ and set of values ...
11
votes
3answers
804 views

How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...
1
vote
2answers
71 views

Closed form of sum with binomial

I want to find closed form of the following expression : $$\sum\limits_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{2k+1}$$ I have no idea how to do it.
0
votes
0answers
37 views

Combinatorics, distributing distinctive balls into identical containers

Here is a problem I am trying to solve: Determine the number of ways to distribute 6 balls into 5 containers if the balls are all different and the containers are all identical. The answer is, that ...
0
votes
1answer
35 views

How many different groups of two people can be selected from a group containing $n$ people? [on hold]

Lets say you 2 men and 1 women. Isn't there some formula for calculating how many different groups of 2 there are? I know I can manually write it with this small sample but when it gets bigger this is ...
1
vote
1answer
36 views

Sum of the series with Stirling numbers of the first kind.

Yesterday I worked on one problem in discrete math and in the process of decision I came across this series. Try to do it with generating functions, but there is no success for me. So, what do you ...
-4
votes
1answer
28 views

Four letters {A, B, C, D} are arranged in a line. What is the probability that A and B will be next to each other? [closed]

Four letters $\{A, B, C, D\}$ are arranged, with no repetitions and always using the four. What is the probability that $A$ and $B$ will be next to each other?
2
votes
2answers
261 views

Combinatorics of a tournament where one wins by taking either three games in a row or four in total

Two teams play each other repeatedly until either one of them wins three games in a row or one of them wins a total of four games. What are all the ways in which the tournament can be played? What ...
4
votes
1answer
31 views

Counting problem - verification please?

A question we did in class asks: "In how many ways can we put 4 girls and 4 boys on a row (so order matters) so that a certain girl and a certain boy are always seated next to each other, and no 2 ...
0
votes
3answers
2k views

How many different phone numbers are possible within an area code?

A phone number is composed of 10 digits. The first three are the area code the other 7 are the local telephone number which cannot begin with a 0. How many different telephone numbers are possible ...
0
votes
0answers
25 views

In how many ways can five different keys be put in a flat leather key case? [on hold]

In how many ways can five different keys be put in a flat leather key case?
-4
votes
1answer
33 views

In how many ways can two chocolate chip, three raisin, and one peanut butter cookie be distributed to six children? [on hold]

A mother has six cookies, two chocolate chip, three raisin, and one peanut butter. In how many distinct ways can she pass them out to six children so that each gets one? Assume that those of the ...
1
vote
2answers
28 views

Conditional probability with students seating

There are 14 students and 9 of them are friends. Students purchased tickets to movie and they got seats in a row of 14 seats. 8 friends got seats next to each other. What is the probability that ...
-2
votes
1answer
17 views

Questions regarding seating arrangements [on hold]

Consider there are $9$ people and $3$ tables that sits the following way ($5$ chairs, $3$ chairs and $2$ chairs). How many combinations if order matters to the people being seated and no chair can be ...
1
vote
2answers
75 views

Probability in a Restaurant

In a revolving restaurant, there are four round tables each with three seats. How many different ways can $12$ people sit in this restaurant? This is what I think the answer is: $$\binom{12}{4} ...
1
vote
0answers
23 views

How to find a set of integer vectors (of length L) such that all its subsets with size L are linearly independent?

Given a number $M\geq L$, how to find a set of $M$ vectors in $\mathbb{Z}_{\geq0}^{L}$, say $S=\{\mathbf{a}_1,\cdots,\mathbf{a}_L\}$, such that: 1-All subsets of $S$ with size $L$ are linearly ...
3
votes
1answer
45 views

Why this solution of the birthday problem is wrong? [duplicate]

If we have $n$ people there are $n(n-1)/2$ possible pairs that we can find. The probability that any two people have the same birthday is $1/365$. So for $n$ people the probability of finding at least ...
1
vote
4answers
40 views

How many ways can you choose $4$ teams of $2$ from $8$ people.

How many ways can you choose $4$ teams of $2$ from $8$ people. My thoughts were that you have $8$ slots to be filled so you have $8!$ ways to arrange them but this overcounts by a factor of $2$ since ...
0
votes
0answers
44 views

When will the game end? [closed]

Two men are playing a game. They have a card deck consisting of exactly 10 cards, numbered from 1 to 10, and all values are different. On each turn a fight happens. Each of them picks one card from ...