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)

2
votes
3answers
37 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 = ...
1
vote
2answers
33 views

How many maps $A \overset{f}{\rightarrow} A$ satisfy $f \circ f = f$ with the given set $A=\{a, b, c\}$. A few related questions inside.

I am trying to calculate how many maps $A \overset{f}{\rightarrow} A$ satisfy $f \circ f = f$ with the given set $A=\{a, b, c\}$. I would like to see the explicit mappings and learn how you ...
3
votes
1answer
23 views

Interesting 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?
3
votes
1answer
30 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$ ...
-5
votes
0answers
40 views

Using Pigeonhole Principle [on hold]

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 ...
1
vote
1answer
21 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
19 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 ...
1
vote
0answers
22 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
17 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
1answer
8 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
1answer
34 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
34 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, ...
0
votes
1answer
27 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
1answer
19 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 ...
1
vote
1answer
20 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
0answers
8 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 ...
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
0answers
42 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: ...
0
votes
0answers
12 views

Number of ordinal trees with n nodes, of depth d, with l leaves

Is computing the number of ordinal trees with $n$ nodes, of depth $d$, with $l$ leaves an open problem? I assumed at first that it was a known results but I could not find it, and neither did the ...
1
vote
0answers
22 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
19 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
2answers
24 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
1answer
38 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 ...
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 ...
3
votes
0answers
83 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 ...
0
votes
1answer
31 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 ...
0
votes
1answer
24 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 ...
12
votes
0answers
98 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
57 views

Optimizing Overwatch Team Composition by Player Hero Preference [on hold]

I am wordy by nature - my apologies. My attempt at a TL;DR - I want to design a small tool that optimizes the team composition of a video game based on minimizing the sum of provided player ...
0
votes
0answers
18 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)$ ...
1
vote
2answers
29 views

Probability of drawing in the right order and having the second draw be drawn before a fixed step

Suppose I am drawing objects uniformly at random, and I continue drawing without replacement until all objects are listed. So the object I draw at the first step is listed in the first place, the ...
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$ ...
-1
votes
1answer
16 views

planar graph ans complement Grapf [duplicate]

G=(v,e) is a simple planar graph with |v|>10 vertices. I need to prove that G#=(V,E#)-the complement of G- is not a plannar graph. I tried to use Euler's formuala, but it didnt went well.
0
votes
1answer
39 views

How many copies of P3 are there in K10

How many copies of P3 are there in K10? I can draw both of the graphs, but I don't know how you calculate this and assume there is a method that can be used to make this easier. Thanks
1
vote
1answer
32 views

identity on Pascal's triangle modulo 2

Consider Pascal's triangle with entries modulo $2$, and let $(k,l)$ denote the $l$-th entry in the $k$-th row by $(k,l)$. Show that, for all $n \in \mathbb{N}$, each entry of the triangle with ...
1
vote
1answer
36 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
20 views

Counting the isotropic points for both quadratic and hermitian forms.

Consider an octonion algebra $\mathbb{O} = \mathbb{O}_{\mathbb{F}_{q^2}}$ over a field of order $q^2$, $q = p^k$. Then we have a natural quadratic and hermitean (by this I actually mean hermitean ...
-2
votes
0answers
25 views

Counting Theory Question - Houses [on hold]

If there are 50 houses in a single street (not a circle) and 2 families. How many ways can the families be housed. Considering the following: Family 1 must be within the first 10 houses. Family 2 ...
1
vote
2answers
45 views

Finding the smallest composition of a natural number with limited basic set of summands

W.l.o.g. I have a set of natural numbers $$S = \{s_1, \ldots, s_n\}, \quad s_i \in \mathbb N$$ as well as an $x \in \mathbb N$ I would like to express as sum of $s_i$. How do I find the smallest ...
0
votes
2answers
35 views

100 shoelaces, pick 2 random ends and tie them together, what is the probability that a loop is created?

The question is: There are 100 shoelaces in a box. You pick two random ends and tie them together. Either this results in a longer shoelace (if the two ends came from different pieces), or it ...
0
votes
1answer
27 views

Find the number of such $4$-tuples $(a,b,c,d)$

If $a \in\{1,2\}$, $b \in\{1,2,4\}$, $c\in\{1,2,3,6\}$ and $d\in\{1,2,4\}$.Find the number of $4$-tuples $(a,b,c,d)$ such that lcm$(a,b,c,d)=12$.
1
vote
1answer
55 views

2048 Logic Puzzle

I thought up this logic problem related to the 2048 game. If all 16 tiles on a 2048 board all had the value 1024, how many ways are there to get to the 2048 tile? Here is what I am talking about in an ...
3
votes
0answers
22 views

Iterate Over Integer Partition Refinement in Sage

A partition of an integer $n$ is a non-decreasing list of positive integers summing to $n$. For example, $3$ can be partitioned as $1 + 1 + 1$, $1 + 2$ or just $3$, but $2 + 1$ is indistinct from $1 + ...
1
vote
3answers
56 views

Number of ways to write $n$ as sum of $k$ non-negative integers without 1

During my calculations I ended up at the following combinatorial problem: In how many way can we write the integer $n$ as the sum of $k$ non-negative integers, each different to one, i.e. calculate ...
7
votes
0answers
89 views

5x5 Bingo Puzzle [Logical thinking problem]

5 people participate in a custom game. They are given blank cards, in which they have to fill numbers from 1-25 in a 5x5 table. The host of the game, then calls out random numbers (between 1-25, ...
0
votes
0answers
9 views

incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
0
votes
1answer
43 views

How many diagonals does a decagon have?

How many diagonals does a decagon have? I have just learnt permutations, dispositions, combinations. How can I solve it with these concepts? I drew it and it was $35$ diagonals. How can I prove ...
0
votes
1answer
25 views

Problem on Inclusion & Exclusion Principle

Book has the following & solution to it too, pls clear my confusion: On rainy day , five gentlemen A, B, C,D, E attend a party after leaving their umbrellas in a checkroom. After the party is ...
3
votes
1answer
78 views

For which $n$ is the $n$-dimensional hypercube a planar graph?

I've been asked the following question: For which values of $n$ is $Q_n$ a planar graph, where $Q_n$ is the $n$-dimensional hypercube? I succeeded to prove that for $n$ equal or greater than $6$ it ...