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
0answers
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, ...
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
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) = ...
50
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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, ...
153
votes
17answers
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: ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
6
votes
1answer
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 ...
0
votes
0answers
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 ...
16
votes
1answer
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 ...
0
votes
1answer
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 ...
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
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 ...
0
votes
0answers
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: ...
3
votes
2answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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!
4
votes
2answers
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 ...
0
votes
1answer
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 ...
7
votes
0answers
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, ...
0
votes
2answers
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 ...
4
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
12
votes
0answers
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 ...
13
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?
1
vote
0answers
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$ ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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)$ ...
1
vote
2answers
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 ...
15
votes
4answers
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 ...
-1
votes
1answer
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.
1
vote
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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
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
0answers
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 ...
-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 ...
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 ...
13
votes
2answers
433 views

Dividing books between two couples

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 ...
1
vote
1answer
61 views

How many partial derivatives does a multivariate polynomial have?

My motivation for this question is from the following toy example; define the (nondeterministic) finite state machine generated by the polynomial $f(x_0 , ... , x_n) \in \mathbb{Z} [x_0 , x_1 , ... , ...
1
vote
0answers
58 views

Lower bound related to Goldbach conjecture

I am curious to know if a lower bound on the number of ways (call this $\beta$ and assume $p_1 + p_2$ distinct from $p_2 + p_1$) in which two primes $p_1, p_2$ that add up to a given even integer $n$, ...
1
vote
3answers
22 views

How many duplicates are eliminated via sorting?

This is a problem I've encountered when using a set as a key for a lookup table. Say I have to map a set of letters (lets say, $4$) to some (unspecified) result with a dictionary/array/etc. For ...