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)

1
vote
1answer
38 views

Grasshoppers jumping on circle

Ten points $A_1,\dots,A_{10}$ are marked in clockwise order on a circle, so that $A_iA_{i+5}$ forms a diameter for all $1\leq i\leq 5$. Initially, a grasshopper is at each point. Every minute, one ...
0
votes
2answers
15 views

How can I count the number of anagrams of MISSISSIPPI where “I” cannot start or end the word?

In lecture I was given the following reasoning: There are 7 options for the first character, 6 options for the last character, and 9! combinations for the 9 characters in between. Then you divide out ...
1
vote
2answers
46 views

To find the number of ordered pair such that $B \cup C = A$

Let $A = \{a, b, c, d, e\}$. If two non empty subsets $B$ and $C$ of set $A$ are formed (without replacement of elements) such that $B \cup C = A$ then how to find the number of such ordered pairs ...
3
votes
1answer
53 views

Understanding counting.

I encountered this question recently: Suppose there are 3 benches in the front row and 7 benches in the second row, how many ways a group of 10 children can be seated in such arrangement? ...
3
votes
1answer
38 views

Set of size 3 is at least the score

Given $5$ triples of nonnegative numbers $(a_{11},a_{12},a_{13}),(a_{21},a_{22},a_{23}), \dots,(a_{51},a_{52},a_{53})$. Let $A=\{1,2,3,4,5\}$. For each $1\leq j\leq 3$, define the $j$th score $s_j$ to ...
0
votes
1answer
16 views

Find and solve a recurrence relation for the number of words of length n from letters A, B, C, and D

Find and solve a recurrence relation for the number of words of length $n$ from letters $A, B, C,$ and $D$ which contain at least one $A$ and the first $A$ comes before the first $B$ (if there are any ...
0
votes
0answers
10 views

Chromatic number of finite directed graph

Graph has 51 vertices. Each node has 3 outgoing edges. Find minimal number of groups of vertices. Such that each group doesn't have edges between vertices of this group. Each node can only be part of ...
12
votes
3answers
6k views

I have a problem understanding the proof of Rencontres numbers (Derangements)

I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation $$D_{n,0}=\left[\frac{n!}{e}\right]$$ where $[\cdot]$ denotes the rounding function (i.e., ...
1
vote
2answers
31 views

In how many ways can 10 married couples line up for a photograph if every wife stands next to her husband?

In how many ways can $10$ married couples line up for a photograph if every wife stands next to her husband? I've given this a shot, now I just wanna compare my answers to see if I'm correct. ...
0
votes
1answer
35 views

In how many ways can 100 identical chairs be distributed to five different classrooms …

In how many ways can 100 identical chairs be distributed to five different classrooms if the 2 largest rooms together recieve exactly half of the chairs? ive worked out a couple of these problems. ...
0
votes
1answer
435 views

I need a formula for how many ways I can choose k balls (two balls each time from the same box) from n boxes?

We have n (can take any value 1,2,3,...) boxes each has the same number of distinct marbles, say b marbles, so the total number of marbles S=n*b. we can choose marbles from boxes with the following ...
1
vote
1answer
19 views

If $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $. How is the upper bound achieved?

Trying to show that if $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $ using a tree, I do know that taking the shortest path gives a lower bound of the number of steps equivalent to ...
3
votes
0answers
36 views

Covering pairs with permutations

I'm looking for a set $S$ of (ordered) lists of $n$ numbers such that: Each number appears at least once as the first numbers. Each number appears at least once as the last numbers. Each possible ...
0
votes
3answers
53 views

Explanation of an Easy Proof of Variance of Bernoulli Trials

I am taking a course in Combinatorics, and I've got two proofs I can use to support the Bernoulli trial variance formula, $\operatorname{var}(X) = np(1-p)$, and I would like to use the one where I ...
1
vote
0answers
21 views

Combinatorial problem of tournament

Suppose there are $n$ teams playing a tournament. Each team plays exactly one game against each of the other teams. In each game the winner is awarded $1$ point, the loser gets $0$ point and each of ...
-2
votes
1answer
38 views

Repeated letters in a word [on hold]

I am forming words of length N from an alphabet of p letters. What is the probability of getting exactly k non-repeated letters? Thanks
1
vote
0answers
14 views

Eigenvalues of “almost” complete bipartite graph ?!

Definition Let $G=U\cup V$ be a bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. $K_{p,q}$ is bipartite graph where every vertex in $U$ is connected to every ...
3
votes
1answer
45 views

Filling holes with balls

I have a simple problem that a high school student could easily solve, but my high school maths classes are far... Here is my problem: I have 8 holes that I must fill with 6 balls. EDIT: Each hole ...
1
vote
0answers
10 views

Maximum of twisted binomial coefficients

For any integer $n$, define $$\mu(n)=\text{arg max}_{1\leq k\leq n}\binom{\frac{n+k}{2}}{k},$$ where the binomial coefficients are set to $0$ if $n+k$ is odd. Question: Is the sequence ...
2
votes
3answers
55 views

How many ways are there to distribute 26 identical balls into six distinct boxes such that…

How many ways are there to distribute $26$ identical balls into $6$ distinct boxes such that: (a) The number of balls in each box is odd (b) The first three boxes contain at most $6$ balls each I ...
0
votes
0answers
8 views

Optimization of 3 hours block bid with multiple constraints

I have the following problem. Given $K, Q, q_{0}$ og $s(1), s(2),..., s(24)$ \begin{aligned} \underset{q( \cdot )}{\max} \sum_{t=1}^{24} & q(t)[s(t)-K] \\ \text{s.t.} & \\ q(t) & \leq Q, ...
3
votes
2answers
91 views

Prove these identities using Jacobi's triple product identity.

I am requesting help with deriving some identities from Jacobi's triple product identity: $$\sum_{n=-\infty}^{\infty}z^nq^{n^2}=\prod_{n\geq 0}(1-q^{2n+2})(1+zq^{2n+1})(1+z^{-1}q^{2n+1})$$ Here is ...
0
votes
1answer
15 views

Stirling number of first kind monotone for a half

Show that every $n>0$, there is some m(n) such that $$s_{n,0}<s_{n,1}<... s_{n,m(n)}>s_{n,m(n)+1}>...>s_{n,n}$$ Where either $m(n)=m(n-1)$ or $m(n)=m(n-1)+1$ and $s_{n,k}$ is ...
0
votes
1answer
38 views

Combinatorics problems involving permutations

Let $A= \{ 1,2,3,...,n\}$ a set and $f:A \to A$ a permutation of the set A. We call a number $x \in \{ 2,3,...,n-1 \}$ special if $f(x)>\max \{f(x-1),f(x+1) \}$ or $f(x)<\min \{f(x-1),f(x+1) ...
2
votes
0answers
21 views

Prove that there exists a one-color $K_3$ in a $K_{17}$ which is colored with three colors

Assume that we have a $K_{17}$ and we color every edge of it with 3 colors ( Like Red, Blue & green ). Prove that for every coloring of $K_{17}$ with 3 colors, After coloring, We have a ...
-2
votes
0answers
16 views

how to do such type of PNC? [duplicate]

A closet has 5 pairs of shoes. The number of ways in which 4 shoes be chosen from it so that there will be no complete pair is ?
0
votes
1answer
26 views

Let $5 \leq k < n$. Then $2k$ divides $n(n - 1)… (n - k + 1)$. What should I use permutations or polynomials?

Let $5 \leq k <n$. Then $2k$ divides $n(n-1)\cdots(n-k + 1)$. Is it true? Please provide a proof. I am confused about using induction, polynomial properties or permutations to solve this problem.
0
votes
1answer
16 views

calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$

Is there any formula for calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$?
3
votes
0answers
45 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
-1
votes
3answers
44 views

In how many ways can an investor invest $\$30,000$ among $5$ possible investment in units of $\$1000$? [on hold]

An investor has $\$30,000$ to invest among $5$ possible investments. Each investment must be in units of $\$1000$. a) If the total of $\$30,000$ is to be invested how many different investment ...
0
votes
1answer
15 views

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game: In a pile there are two red balls, four green balls, four blue balls, and ...
0
votes
0answers
12 views

explicit expression

Hi could someone guide me through how to find this explicit expression? I have the definition of F(x) = ae^(gx) + bh(e^(hx)) but need to show the explicit expression now through F(0) and F(1) ...
53
votes
18answers
16k views

Good Book On Combinatorics

What is your recommendation for an in-depth introductory combinatoric book? A book that doesn't just tell you about the multiplication principle, but rather shows the whole logic behind the questions ...
-1
votes
0answers
61 views

Prove an identity [on hold]

Anyone has any idea on how to prove $$\sum \limits_{i=0}^{l} \sum\limits_{j=0}^i (-1)^j {m-i\choose m-l} {n \choose j}{m-n \choose i-j} = 2^l {m-n \choose l}\;?$$
1
vote
1answer
25 views

Is this true that $\sum_{v=0}^k (-1)^v{a+v-1 \choose v}{b+k-v-1 \choose k-v}$ is the coefficient of $t^k$ in $(\frac{1}{1+t})^a(\frac{1}{1-t})^b$

I was reading a paper, in which the author assumed that $$\sum_{v=0}^k (-1)^v{a+v-1 \choose v}{b+k-v-1 \choose k-v}$$ is the coefficient of $$t^k $$ in ...
0
votes
0answers
22 views
+50

Number of paths between two points in the first Quadrant.

[Extension of this] We can move in 4-directions and we need to reach $(0,b)$ from $(a,0)$ in exactly $n$ steps keeping in the first quadrant ($x\ge0$ and $y\ge0$) [$a,b\ge0$] Similar to previous ...
3
votes
3answers
45 views

An induction problem that I can't think of an approach.

Prove that if $n$ people are standing on line at a ticket counter, and the first person on line is a woman and the last is a man, then somewhere on the line there is a man standing directly behind a ...
1
vote
1answer
57 views

Are $6$ hotels enough to separate $n$ mathematicians?

A convention of mathematicians will have rooms available in $6$ hotels. There are $n$ mathematicians and, because of personality conflicts, various pairs of mathematicians must be lodged in different ...
3
votes
1answer
38 views

Combinatorial proof or meaning of the identity [duplicate]

I have to give a combinatorial proof and the meaning of the following identity. $$\sum_{k = 1}^n (-1)^k k !S(n,k) = (-1)^n,$$ where $S(n,k)$ is the Stirling number of the second kind. Could anyone ...
0
votes
0answers
16 views

Number of paths in a graph as a function of depth

This problem has been bugging me for weeks now. Consider a infinite graph, with a given degree distribution. Now, for the sake of intuition, consider that each vertex includes a match. We pick a ...
0
votes
0answers
20 views

Bound the vc dimension of hypothesis class

Given some set $V$ of size $n$, define the domain $X = V \times V$. In addition, define the hypotheses class $H$ to be all the equivalence relations over $V$ with at most $k$ equivalent classes. I am ...
1
vote
0answers
23 views

Reference for Coefficient Extraction of Multiple Sum

In a post here, the final answer is obtained by coefficent extraction of the quadruple sum. ...
2
votes
1answer
54 views

What is the probability that a five-card poker hand has four ACES?

What is the probability that a five-card poker hand has four ACES? When I was solving the above stated problem, I got confused while trying different methods : Assume a normal $52$ deck of ...
10
votes
1answer
1k views

Why isn't there only one way of painting these horses?

If you have $11$ identical horses in how many ways can you paint 5 of them red 3 of them blue and 3 brown? My intuition instantly tells me there is only one way of doing this. I mean if the ...
4
votes
3answers
86 views

Winning All Levels in a Game

There are $L$ levels in a game. In each turn of the game, you go through each level one by one and try to complete it. The goal is to complete all levels of the game. The probability of completing any ...
5
votes
2answers
376 views

Number of unit squares that meet a given diagonal line segment in more than one point

Let $l$, $b$ be positive integers. Divide the $l \times b$ rectangle into $lb$ unit squares in the usual manner. Consider one of the two diagonals of this rectangle. How many of these unit squares ...
7
votes
4answers
924 views

Why does it have to be an integer?

Let $k$ and $n$ be integers greater than 1. Then $(kn)!$ is not necessarily divisible by A. $(n!)^k$ B. $(k!)^n$ C. $n!\cdot k!$ D. $2^{kn}$ I believe option D is correct ...
10
votes
2answers
513 views

Combinatorics: Number of possible 10-card hands from superdeck (10 times 52 cards)

I have the following problem from book "Introduction to Probability", p.32 A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. ...
0
votes
1answer
22 views

How many different permutations p with the length n are there, so that the cycle that contains 1 has length b (1<=b<=n) and so that p(1)=2

How many different permutations $p$ with length $n$ are there, so that the cycle that contains $1$ has length $b$ ($1\leq b\leq n$) and so that $p(1)=2$? I have tried for hours and still I couldn't ...
1
vote
2answers
56 views

What is the probability to fill rows of a cinema hall?

This is the problem I'm trying to solve, but I'm not sure I'm on the correct path! would appreciate your feedback guidence and help. So the problem is: there're 3 rows in a cinema hall. the first one ...