# 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.

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 ...
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 ...
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 ...
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: ...
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 ...
24 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 ...
22 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!
55 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 ...
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 ...
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 ...
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 ...
56 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 ...
108 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 ...
121 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 ...
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$ ...
74 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 ...
81 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 ...
33 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 ...
17 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.
60 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 ...
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
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 ...
23 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 [closed]

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 ...
37 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 ...
104 views

33 views

### expect number of multipe draws

There are 100 numbered balls in an urn. We make 100 random draws with replacement. Of course, we can not expect to draw every number exactly once, there will be multiples. What is the expected value ...
39 views

### Count integer squares coordinates

Let $n$ be given an natural number. We want to find the number of squares which have corners with integer coordinates between $0$ and $n$. For example $n=1$, there is only one square; $n=2$ there are ...
44 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 ...
65 views

### Count how many “free words” of a certain length reduce to the identity

Let $F_n$ be the free group with $n$ generators $g_1,\ldots,g_n$. I'm trying to settle the following: Question. For a fixed even integer $m$, is there a systematic way to count how many words ...
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 ...
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 ...
16 views

### Evaluation sum indexed by non decreasing sequences

During solving a problem from probability theory, I've met the following sum to evaluate: p_n(N) = \frac{1}{N!}\sum_{0\leqslant k_1\leqslant\ldots\leqslant k_n\leqslant N}\frac{k_1\cdot\ldots\cdot ...
26 views

### Find most varied match assignments for a 4-player card game

I'm a programmer and confronted with a particularly hard (at least for me) problem I couldn't find an answer for. This is not a school task or anything. It is something I need personally. I've ...
37 views

### Connectivety of the Erdős–Rényi random graph [closed]

Let G be a graph in G(n, p) (Erdős–Rényi model) I want to prove that that P( G(n, p) where p ≥ ( lnn/10n) and number of tree components on 11 vertices = 0 ) converges to 1 and lnn/n is a ...
A password can be any 4 digit {0...9}. 1.)How many possible passwords are there? for this I did $10^4 = 10,000$ 2.) How many possible passwords with no repeated digits? $10*9*8*7 = 5040$ 3.) How ...