Tagged Questions

This tag is for basic 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 (5)

2
votes
1answer
9 views

Poisson approximation to bound probability of balls in different bins

Suppose $n$ balls are thrown randomly and independently into $n$ bins. What is an upper bound that all balls land in different bins using Poisson approximation? The exact probability is $n!/n^n$, ...
0
votes
0answers
28 views

If $\binom{n-1}{r} = (k^2-3)\cdot \binom{n}{r+1}$. Then values of $k\in

If $\displaystyle \binom{n-1}{r} = (k^2-3)\cdot \binom{n}{r+1}$ and $k\in {\mathbb{R}}$. Then values of $k\in $ $\bf{My\; Try::}$ We can write it as $\displaystyle \frac{(n-1)!}{r!\cdot (n-1-r)!} = ...
1
vote
1answer
12 views

Last two bins have same number of balls

If we throw $n$ balls independently and randomly into $n$ bins, what is the probability that the last two bins have an equal number of balls? We can write that as the sum of the probability that each ...
0
votes
0answers
27 views

Combinatoric Easy Problem : How many number from these numbers?

I just want to compare your answer with my answer. As we know, this subject, combinatoric has different answer and different point of view for each person. So, I just wanna know is your answer is same ...
1
vote
1answer
44 views

Showing the equality of two rook polynomials.

I'm reading Barbeau's Polynomials. I've done the following: Taking an arbitrary chessboard $C$ with some of the squares forbidden (with $n$ being the number of squares and $F$ the number of ...
1
vote
1answer
55 views

What is meant by $ab$ on words $a$ and $b$ in $\{ab\ |\ a,b \in Σ^*\}$?

Given language $L$ := $\{ab\ |\ a,b \in Σ^*\}$, $Σ := \{blue, green\}$. Is the notation "$ab$" above taken to be word concatenation, such that $\{bluegreen\} \subset L$? What occurs when $L$ := ...
1
vote
1answer
26 views

The number of ways to paint 3 cubes using 3 cans of paint, so that two cubes are blue

I have a question about the usage of the probability formula (I believe that is what it is called). So, I have 3 cubes and 3 differently colored cans of paint (Let's say, Red, Yellow and Blue). I am ...
0
votes
3answers
33 views

Proof by Induction: Series of binomial coefficients with same k-length subsets

I have no idea how to prove this binomial equation identity. For reference this is included in Discrete Mathematics for Computer Scientists by Clifford Stein, Robert Drysdale and Kenneth Boggart, ...
0
votes
0answers
39 views

Problems about Linear Extensions

The following are exercises 57 and 58 from R. Stanley's Enumerative Combinatorics. I can't see to figure out how to explain an answer to 57, and I don't know where to begin with 58. $e(P)$ denotes the ...
4
votes
0answers
55 views

How to visualise Bollobas' 1965 theorem?

Theorem $[n]=\{1,\ldots,n\}$. Let $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ be such that $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$. Then $$\sum_{i \in I} ...
3
votes
2answers
50 views

How many binary sequences of length n are there that contain exactly m occurrences of the pattern 01?

I thought there were n-1 places between the first and last digit. In these places I hypothesized there are switches that change (from 0->1 or 1->0) For ...
2
votes
1answer
30 views

Enumerating Ideals in Posets

I am trying to work through Exercise 44 (a) in Ch.3 of R. Stanley's Enumerative Combinatorics. The problem is as follows: Let $w=a_1a_2\cdots a_n\in \mathfrak{S}_n$. Let $P_w=\{(i,a_i)\colon ...
1
vote
2answers
51 views

Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n, a_1=1, a_2=11.$

First I solved $a_n=4a_{n-1} -3a_{n-2}$: $$x^2-4x+3=0\Rightarrow (x-3)(x-1)=0\Rightarrow a_n=k_1(1)^n +k_2(3^n)=k_1+k_2(3^n)$$ The problem is, I have no idea how to handle that part which has made ...
0
votes
1answer
37 views

Recursion and divisibility by $2^n$

A team plays a series of games, each of which results in either a win (W), a draw (D), or a loss (L). Let $S_n$ denote the number of possible sequences for a team which never loses two successive ...
0
votes
0answers
16 views
+50

Probabilistic subset intersection

Let $\left \{ \left ( A_{i},B_{i} \right ),1\leq i\leq h \right \}$ be a family of pairs of subsets of the set of integers such that $\left | A_{i} \right |=k$ for all $ i$ and $\left | B_{i} \right ...
1
vote
1answer
32 views

Kraft-McMillan inequality

Let $F$ be a finite collection of binary string of finite lengths and assume that no two distinct concatenations of two finite sequences of codewords result in the same binary sequence. Let $N_i$ ...
0
votes
1answer
27 views

Intersections in polygons

I'm having troubles solving the following problem which is about combinatorics: let $n$ be a natural number $\ge 3$, and a convex polygon with $n$ vertices. Each vertices are supposed to connect ...
-1
votes
1answer
29 views

Subset of permutations and its cardinality [closed]

Let $ P \subset S_n $ be the set of permutations that decompose in exactly $(n-2)$ disjoint cycles. Prove that $|P| = \binom n 4 + 2\binom { n+1} 4$. Give me a hand.
7
votes
1answer
120 views

Number of $K_{10}$ always increases

Let $G=(V,E)$ be a graph with $n\geq 10 $ vertices. Suppose that when we add any extra edge to $G$, the number of complete graph $K_{10}$ in $G$ increases. Show that $|E|\geq 8n-36$. [Source: The ...
0
votes
0answers
18 views

Expected Probability of a Random Agent and a Probabilistic Agent

I'm running simulations on two agents: random agent and probabilistic agent. The world they are running in is the Wumpus World where the agent is dropped in a 4x4 grid where each cell has a 20% chance ...
0
votes
2answers
34 views

How many unique sets do you get if you pair 8 girls and 8 boys?

If I have 2 girls and 2 boys, let's call them Anne, Brooke, Andrew and Benjamin, we have 2 unique sets: Set 1: Anne - Andrew Brooke - Benjamin Set 2: Anne - Benjamin Brooke - Andrew Likewise, for 3 ...
0
votes
2answers
20 views

20 Company cars, 4 specific models.

Twenty cars to be bought by a company must be selected from up to four specific models. In how many ways can the purchase be made if a) no restrictions apply? b) at least two of each model must be ...
1
vote
1answer
46 views

Proportion of asymmetric graphs

Wikipedia states, that the proportion $$p(n):=\frac{number\ of \ asymmetric \ graphs \ with\ n\ nodes}{number\ of\ graphs\ with \ n\ nodes}$$ satisfies $$\lim_{n->\infty }p(n)=1$$ I wonder ...
0
votes
0answers
27 views

n balls into m baskets

How can I write a given natural number into sum of required ($m$) natural numbers? Example: $$10=2+8+0$$ here $m=3$ Let $n_i$ be the values i.e. $2,8,0$ in the above example. I want to know whether ...
1
vote
0answers
26 views

Number of orbits of the Frobenius automorphism

Let $q=p^s$ be a prime power congruent to $1$ modulo $4$, let $\mathbb{F}_q$ be the finite field with $q$ elements, and let $\phi$ denote the Frobenius automorphism (that is $\phi(a)=a^p$ for every ...
-1
votes
0answers
37 views

A combination and number theory related problem

I'm given 2 numbers n and m.I have to make n with m numbers(only taking their sum).For example,if n=6,m=3,6 is formed with 3 numbers in the following way. a)1+1+4=6 b)2+2+2=6 c)1+2+3=6 For every ...
12
votes
3answers
146 views

Couple Probability

The problem states that there are 12 boys and 12 girls. Each boy chooses a girl at random and each girl chooses a boy at random. If a boy and a girl choose each other, they form a couple. It then asks ...
1
vote
1answer
21 views

Deriving Van der Waerden's theorem from Rado's theorem

In Ramsey Theory Van der Waerden theorem states that, Let $k,r$ be positive integers. Then in every partitioning of the positive integers into $r$ classes there is one class which contains an ...
4
votes
1answer
84 views

Partition in graph connecting itself and other half

Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta>10$. Prove that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A|\leq ...
0
votes
1answer
35 views

Generating functions for partitions of n with an even number of parts and odd number of parts, and their difference.

I've been trying to figure this out for more than 10 hours. So far I have, for even number of partitions, $$P_e(x)=\sum_{k\ge1}(x^{2k}\prod_{i=1}^{2k}\frac{1}{1-x^i})$$ and for odd numbers ...
1
vote
0answers
11 views

Bound on difference of two i.i.d. variables [duplicate]

Prove that for every two independent, identically distributed real random varaibles $X,Y$, $$Pr(|X-Y|\leq 2)\leq 3\cdot Pr(|X-Y|\leq 1)$$ [Source: The probabilistic method, Alon and Spencer]
0
votes
0answers
12 views

Composition of rational functions degrees

Consider rational function $r(x) = \frac{p(x)}{q(x)}$ with $\operatorname{degree}(p(x)) = n_1, \operatorname{degree}(q(x)) = n_2$ and $gcd(p(x),q(x))=1$. Let degree of $r(x)=n_1+n_2$ (sum of degrees ...
1
vote
0answers
48 views

Maximizing Stirling numbers of the second kind

In Stanley's Enumerative Combinatorics, there is a question on Chapter $1$ which goes as follows: Let $S(n,k)$ denote a Stirling number of the kind (ie, $S(n,k)$ is the number of ways to to ...
0
votes
1answer
18 views

Distributing Apples and oranges. confused about solution

How many ways are there to distribute 4 identical oranges and 6 distinct apples into 5 distinct boxes I know you find number of ways for apples which is 5^6. The solution tells me that the ways for ...
0
votes
1answer
36 views

number of pairs of integers whose sum is even

Given the set of integers from 1 to 9, how many combinations sum to an even number? I got 511. Here's my approach: I first consider 3 sets: $X$: the non empty set of all even numbers: ...
-2
votes
1answer
27 views

round robin combinatorics problem [closed]

15 players played round robin one-on-one basketball, and they all won a different number of games. how many games did the fifth place player win?
1
vote
0answers
20 views

Approximate Solution to Backwards Recurrence of Dynamic Game

Suppose we keep tossing a fair dice until we reach some cumulative sum greater than or equal to $N$. Then, let $S_k$ be the expected value of the final sum, given that the current sum is $k$. We have ...
1
vote
1answer
31 views

Expected number of returns to zero in a symmetric random walk - closed form

The expected number of returns of a symmetric random walk is given by $\sum_{k=0}^n \binom{2k}{k} / 2^{2k} -1$ The exercise is to compute an explicit form for this. I tried to do this in the ...
3
votes
2answers
117 views

Probability that each bucket has $\geq 3$ balls

There are $30$ buckets. John throws $20$ balls, each time landing uniformly among the buckets. What is the probability that no bucket contains $\geq 3$ balls? If the question were $\geq 2$ balls, we ...
2
votes
1answer
42 views

Beautiful logical combinatorics problem

TV series were aired for 5 years. Every day at most 2 episodes were shown. Every year, starting from the second one, either 40% more, or 40% less episodes, than the previous year, were aired. The ...
-1
votes
1answer
28 views

Question in permutations

When we use this law? And in any case we use it? Thank you and I wish clarification.
0
votes
1answer
37 views

Beautiful problem about 11 statements

11 pieces of paper are on a line. On each of them one of 11 statements is written (all are different on each paper): 1)No false pieces of paper to the left 2)Exactly 1 false paper to the left ...
0
votes
1answer
24 views

Filling and painting bowls

I only know basic things about combinatorics, but I encountered a problem. You have 60 bowls. Then you do the following: Fill 30 bowls with one ball Fill 20 bowls with two balls Fill 10 bowls with ...
2
votes
1answer
61 views

Finding number of ways to get a sum of $100$

If we are given to find the number of ways 10 positive integers can sum to 50, we simply find the coefficient of $x^{100}$ in $(x+x^2+...+x^{90})^{10}$, which turns out to be $\binom{99}{90}$. But ...
1
vote
1answer
19 views

Mix of permutation and combination

a car can hold 3 people in the front seat and 4 in the back seat. In how many ways can 7 people be seated in the car if John and Samantha must sit in the back seat and there is only one driver? the ...
1
vote
2answers
91 views

Combinatorics question. Probability of poker hand with one pair

If we assume that all poker hands are equally likely, what is the probability of getting 1 pair? So the solution is I understand nominator part, but I do not understand why in denominator we have ...
1
vote
1answer
27 views

Proving the binomial coefficients by induction (half-done, but need help)

Defining the binomial coefficients $n \choose k$ as follows, i) for all $n \in \mathbb{N}$, $\binom{n}{0} = \binom{n}{ n} = 1$ (ii) for all $2 \leq n \in \mathbb{N}$ and for all $ 1 \leq k \leq n-1, ...
-1
votes
2answers
77 views

Placing Rooks on 8x8 board [closed]

In how many way can 5 indistinguishable rooks be placed on an 8x8 board so that no rook can attack another and neither the first row nor first column is empty?
0
votes
1answer
8 views

Number of Distinct Elements in Set of Products of 2 Matrices

Let $X=\begin{pmatrix}\cos\frac{2\pi}{5} & -\sin\frac{2\pi}{5}\\\sin\frac{2\pi}{5} & \cos\frac{2\pi}{5}\end{pmatrix}$ and $Y=\begin{pmatrix}1 & 0\\0 & -1\end{pmatrix}$. Find the ...
1
vote
1answer
39 views

Counting and probability gift exchange problem

There are 50 people (numbered 1 to 50) and 50 identically wrapped presents around a table at a party. Each present contains an integer dollar amount from $1 to $50, and no two presents contain the ...