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

Upper bound on the list chromatic number of $d$-degenerate graphs

It can be proved that $\chi(G)\le d+1$ if $G$ is $d$-degenerate, but can we also say that $\chi_\ell(G)\le d+1$, in general[note 1]? Here, $\chi(G)$ is the chromatic number of $G$ and $\chi_\ell(G)$ ...
4
votes
0answers
156 views

An optimization problem involving Latin Squares

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write ...
2
votes
4answers
62 views

prove $\sum_{k = 0}^{n} \binom{n}{k} \binom{m-n}{n-k} = \binom{m}{n}$

prove $\sum_{k = 0}^{n} \binom{n}{k} \binom{m-n}{n-k} = \binom{m}{n}$ Attempt:I was thinking of trying to prove this through induction, but I am having trouble with a base case: base case: let $n = ...
0
votes
0answers
17 views

Permuting a cycle when assignments exist.

There are $n$ agents total and $n$ objects total. Each agent ranks objects uniformly at random independent of other agents. Suppose I fix a subset of $k$ agents $a_1,..,a_k$, and $k$ objects ...
52
votes
10answers
22k views

Taking Seats on a Plane

This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless Imagine there are a 100 people in line to ...
1
vote
1answer
25 views

Combinatorics [sandwich toppings]

I'm trying to figure out how to solve this excercise; You can order a sandwich from 5 different types of bread, you can have butter, lettuce or neither. You get to choose from 3 types of meat, and ...
3
votes
1answer
51 views

Question about regular languages

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?
2
votes
1answer
540 views

What is number of perfect matchings in a bipartite graph

Let's $G=(U,V,E)$ be a random balanced Bipartite graph graph which $|U|=|V|=n$. What is the number of random graphs that has a perfect matching? I think that the number of possible graphs is ...
4
votes
1answer
42 views

Number of ways to make a bracelet with n beads and m colors

I was solving a problem on the Art of Problem Solving website that was posed like this: How many ways can the $7$ spokes of a wheel be painted such that each spoke can be either red, green, or blue? ...
-5
votes
0answers
73 views

Using Pigeonhole Principle

10 runners in a round stadium. each one runs in a constant speed $\ r_i>0 $ and all of them start running at the same time. Prove that for every $\epsilon>0$ exists time $\ t>1 $ such that ...
14
votes
4answers
5k views

Is there a “most random” state in Rubik's cube?

Is there a state in Rubik's cube which can be considered to have the highest degree of randomness (maximum entropy?) asssuming that the solved Rubik's cube has the lowest?
2
votes
1answer
41 views

Counting the numnber of (labelled and unlabelled) rooted trees on $n$ vertices with height $h$

As far as I know, the number of labelled rooted trees on $n$ vertices is $n^{n-1}$. Is there a known result for counting the number of (labelled and unlabelled) rooted trees on $n$ vertices having ...
1
vote
1answer
84 views

Ternary strings (combinatorics, recurrence)

The questions is: for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$. Provide answer in form of: a) recurrence relation b) combinatorial expression After that, ...
3
votes
1answer
37 views

Probability to pick couples of numbers from a set of the first $n$ natural numbers

I am stuck on the following problem: I have a set $A$ of the first $n$ natural numbers. I define a new set $B$ picking randomly $m$ numbers from $A$. What is the probability to have at least $k$ ...
1
vote
1answer
23 views

Minimum length $m$ of $n$ string with pairwise Hamming distance $m/2$

I want to construct $n$ binary strings, each of the same length $m$ (to be determined), such that each pair of string has Hamming distance exactly $m/2$ (i.e. the strings disagree on $m/2$ positions). ...
0
votes
1answer
26 views

How do we solve these permutation and combination questions? [on hold]

Q1 In how many ways a panel of six doctors is selected from five surgeons and six physicians if condition is surgeons are more than physicians. A 82 B 81 C 65 D 135 Q2 Find the no. of ...
8
votes
4answers
1k views

How many different dice exist? That is, how many ways can you make distinct dice that cannot be rotated to show they are the same?

Dice are cubes with pips (small dots) on their sides, representing numbers 1 through 6. Two dice are considered the same if they can be rotated and placed in such a way that they present ...
0
votes
1answer
22 views

Focus of arithmetic progression applied to Van der Waerden's Theorem

So Im working through my notes which prove Van der Waerden's Theorem for the case $m=3$. The method my lecturer has chosen is to first prove the Lemma below. The Lemma is proved by induction but I ...
5
votes
1answer
50 views
+100

Maximum value of the smallest number of operations to obtain configuration from original configuration

Let $n$ be a positive integer. There are $n(n+1)/2$ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing $n$ marks. Initially, each ...
1
vote
0answers
27 views

Clarification of Sperner's Lemma

From Graph Theory by Bondy, Murty Image from wikipedia I don't see how the picture holds according to the definition from the Graph Theory book. Specifically, the definition says to assign ...
0
votes
1answer
22 views

Show that if $u, v \in V(G)$, $u \not= v$, with $G$ a $k$-critical graph, then $N(u) \not\subseteq N(v)$

I tried considering $\chi(G-u) = k-1$ and using the same for $v$, And when I quit a vertex $u$ or $v$ I make a proper partition in $k-1$ color classes, saying that this differ in one the color of ...
0
votes
2answers
52 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
1answer
29 views

Finding maximal product of numbers of permutations

Let $n\geq 1$ be a total number of objects that must be taken from $m\geq 1$ sets of objects. For all $i \in \{1,\cdots,m\}, \ M_i \in \mathbb{N}^*$ denotes the number of objects present in the set ...
0
votes
1answer
9 views

Relation between size and order of a graph k- chromatical critical

How can i prove the following statement? Let $G$ be a graph k-critical of order = $n$ and size = $q$. Show that $k \le \frac{2q + n}{n}$
0
votes
2answers
406 views

Determine the number of positive integer x where x<= 9,999,999 and the sum of the digits in x equals 31.

Determine the number of positive integer x where $$x\le 9,999,999$$ and the sum of the digits in x equals 31 How do you approach this question? TEXTBOOK SOLUTION: Let x be written in base ...
0
votes
1answer
36 views

2 classes in the same classroom each with 100 seats and the same 100 students, find the probability that no one has the same seat for both classes

The question is as follows: Harvard Law School courses often have assigned seating to facilitate the “Socratic method.” Suppose that there are $100$ first year Harvard Law students, and each ...
2
votes
0answers
35 views

$a(n+1, k) = ka(n,k) + a(n,k-1)$

While working a combinatorial problem, I have encountered the recurrence relation $$a(n+1, k) = ka(n,k) + a(n,k-1)$$ where $a(0,0) = 1$ and $a(0,k)=0$ if $k \ne 0$. Except for the $k$ multiplier, ...
2
votes
3answers
1k views

Proving Pascal's identity

So I came across Pascal's identity: Prove that for any fixed $r\geq 1$, and all $n\geq r$, $$ \binom{n+1}{r}=\binom{n}{r}+\binom{n}{r-1}. $$ I know you can use basic algebra or even an inductive ...
3
votes
1answer
453 views

How many ways can you choose team of 5 people out of 7 men and 6 women in which there are at least 3 men?

I am confused by this question. I solved it by selecting 3 men first out of 7 men and then selecting 2 people out of 10 remaining person ( 4 men and 6 women ) . So my answer is C(7,3) * C(10,2) = ...
0
votes
1answer
29 views

Number of ways to put n labeled balls distributed among k unlabeled boxes. All boxes should be non-empty.

There are $n$ labeled balls and $k$ unlabeled boxes. The balls should be distributed among the $k$ boxes. All boxes should contain at least one ball. Question: In how many different ways the balls ...
0
votes
0answers
62 views

Sequence of integers in given range that sums up to given value

I'm trying to find out, if there is a way to find the total number of possible combinations of integers $x_i \in [l,u] \cap \mathbb{Z}$ for all $i = 1,\ldots,n$ that sum up to $A$. Generally, ...
0
votes
1answer
40 views

A binomial sum identity

Let \begin{align*} f(n, r, \pi, k) &= \sum_{z=0}^{n}\sum_{s=0}^{r}\binom{z}{s}\binom{n}{z}\binom{n-z}{r-s}(-1)^{r+s}\left(\frac{\pi}{1-\pi}\right)^{r/2-s}\pi^{z}(1-\pi)^{n-z}z^k \end{align*} I am ...
6
votes
1answer
510 views

Different Perspectives of Multinomial Theorem & Partitions

There are 2 important interpretations of the multinomial theorem and coefficients. 1: Determining the number of ordered strings that can be formed using a set of letters. For example, with 1 m, 4 ...
1
vote
0answers
10 views

Maximize the mutual permutation disparity

I am trying to work on a problem that needs me to find the top-k most disparate permutations for a n-tuple (hence n! possible choices). The disparity measure between two permutations I'm thinking of ...
16
votes
1answer
317 views

What is the number of $n \times n$ binary matrices $A$ such that $\det(A) = \text{perm}(A)$?

Recall that the permanent is the 'positive analog' of the determinant whereby the signs in the cofactor expansion process are taken as positive. That is, the permanent is the immanant corresponding to ...
0
votes
1answer
27 views

Ordered and unordered choices [on hold]

How do I use one of the following formulas: $$n^r$$ $${n+r-1 \choose r}$$ $$\frac{n!}{(n-r)!}$$ $${n \choose r}$$ (Where $n$ is the set size and $r$ is the number of elements being chosen) to ...
1
vote
1answer
38 views

Count total combinations

Suppose you have K distinct characters. Using these characters you can make various strings of length 1 to N and characters can be repeated in these strings. Now you have to count total combinations ...
1
vote
0answers
49 views

Computing a sum involving binomial coefficients

I am doing some (pretty heavy) computations, and I am stuck at a point that can be rephrased as follows: Let $m>n\ge0$ be two integers. Compute ...
0
votes
0answers
18 views

How do I calculate such possible number of total and serial schedule?

Consider the following two transactions $T_1$ and $T_2:$ How many non serial schedules are possible, if we execute both transactions concurrently? $3000$ $3001$ $3002$ $3003$ My try: ...
3
votes
2answers
110 views

Example in Combination, is there any solution?!

Is there any idea to solve such a question? I have $40$ pens that includes $20$ white pens and $20$ black pens, I decide to distribute these pens among $4$ students that every student gets at least ...
1
vote
0answers
23 views

planar graph- combinatorics

Let n be the the number of points in a plane so there are no 3 points in the same straight line. d is the minimal distance between any distinct pair of points in the plane. I need to prove that ...
1
vote
0answers
20 views

How many bit strings of length eight contain three consecutive 1s? [on hold]

Can you help me answer how many bit strings of length eight contain three consecutive 1s? Thank you!
0
votes
1answer
52 views

What are some efficient ways to go about a problem where you cannot exceed the other by 2?

I need an efficient way to go about this problem, for practice for my problem solving test. This is not a part of the actual test. This is the type of question that I am struggling with There are two ...
0
votes
2answers
26 views

For irrational real number $r$, find $n \in \mathbb{Z}$ such that $|nr - [nr]| < 10^{-10}$.

This problem is from the book "A Walk Through Combinatorics" by Richard Bona. For any irrational number $r$, there exists a positive integer $n$ such that the distance of $nr$ from the nearest ...
0
votes
2answers
26 views

Can anyone explain why the combinatorical identity $\sum_{t=2}^{l_1} \binom{n-t}{k-2} = \binom{n-1}{k-1}-\binom{n-l_1}{k-1}$ is true?

When I type $\sum_{t=2}^{l_1} \frac{(n-t)!}{(n-t-k+2)!}$ into Wolfram alpha, I get an answer that simplifies to $\binom{n-1}{k-1}-\binom{n-l_1}{k-1}$. Can anyone explain why this simplifies so ...
0
votes
1answer
25 views

counting the forecasts of 20 chess games

I have a Question... The results of 20 chess games (win, lose, draw) have to be predicted. How many different forecasts can contain exactly 15 correct results? I don't really understand this ...
0
votes
1answer
49 views

There are 40 available time slots for examinations. You need to schedule the A and B exams according to the following rules:

NOTE: This is homework so would appreciate if I could get some explanations instead of just straight answers. Really struggling with this question and to be honest, don't really know where to even ...
3
votes
0answers
103 views

Find Unique Index for a Subset S [on hold]

I'm looking for a way to assign a unique number to a particular subset of S. S is a set of n distinct integers from 1 through n. Now, take the set of all subsets of length k where order doesn't ...
12
votes
0answers
117 views

Moving half of the nuts

An even number of nuts is divided into three nonempty piles. In each step, we are allowed to take half the nuts from a pile with an even number of nuts, and put them on another pile. Can we always ...
1
vote
0answers
15 views

Finite prime field representation of uniform matroid $U_{2,n}$

Suppose I have a uniform matroid $U_{2,n} = (E, I)$ (so $F \subset E$ has $F \in I \iff |F| \leq 2$) and want to represent it over $GF(p)$, i.e. I would like to construct a map $\phi : E \to GF(p)^2$ ...