Tagged Questions

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.

14 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, ...
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 ...
450 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) = ...
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 ...
24 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 ...
61 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, ...
27k views

Do men or women have more brothers?

Do men or women have more brothers? I think women have more as no man can be his own brother. But how one can prove it rigorously? I am going to suggest some reasonable background assumptions: ...
8 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 ...
10 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 ...
32 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 ...
509 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 ...
5 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 ...
301 views
+50

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 ...
23 views

Ordered and unordered choices

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 ...
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 ...
29 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 ...
10 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: ...
108 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 ...
8 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 ...
17 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 ...
16 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!
36 views

prove simple sum, combinatorics

I want to prove that $\sum_{i = 1}^{n} \binom{n}{i}\binom{n}{i-1} = \binom{2n}{n-1}$ On the right hand side we simply have the coefficient of $x^{n-1}$ of the term $(1+x)^{2n}$ But on the other ...
51 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 ...
83 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, ...
21 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 ...
26 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 ...
24 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 ...
23 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 ...
24 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 ...
14 views

Find Unique Index for a Subset S

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 ...
77 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 ...
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?
14 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$ ...
41 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 ...
74 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 ...
14 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)$ ...
24 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 ...
3k views

In the card game Set, what's the probability of a Set existing in n cards?

Given $n$ randomly drawn Set cards on a table from a standard 81-card deck, how can I determine the probability of one or more Sets existing on the table? First, for those who may not be familiar ...
14 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.
57 views

number of function $f$ from $f:\mathbb{A}\rightarrow \mathbb{A}$ and satisfying $f(f(x))=x$

Let $A=\{1,2,3,4\}\;,$ Then total number of function $f$ from $f:\mathbb{A}\rightarrow \mathbb{A}$ and satisfying $f(f(x))=x$ $\bf{My\; Try::}$ If $f(x)=x\;,$ Then $f(f(x))=x.$ So there are ...
32 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 ...
33 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
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 ...
14 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 ...
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 ...
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 ...
Two couples of boys and girls, $(b_1,g_1)$ and $(b_2,g_2)$, are dividing a pile of books. Every book will go to one of the couples, and they'll read it together. Each person has a (nonnegative) value ...