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
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
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 ...
0
votes
0answers
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!
0
votes
1answer
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 ...
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
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 ...
4
votes
0answers
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 ...
12
votes
0answers
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 ...
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
vote
0answers
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 ...
3
votes
1answer
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 ...
1
vote
2answers
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 ...
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
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.
1
vote
2answers
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 ...
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
0answers
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 ...
-2
votes
0answers
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 ...
0
votes
2answers
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 ...
4
votes
1answer
104 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
60 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 ...
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$.
-3
votes
1answer
52 views

What is the probability of getting intial state (read details)? [closed]

Alex, Bob and Charlie each have 5 different colored marbles in their bags(same 5 colors in each of those bags though). Alex randomly picks a marble from Bob's box and puts it into his bag. Then ...
5
votes
2answers
114 views

How many ways are there for W women and M men to sit on N chairs, if no man can sit next to woman?

So, we have: W - count of women M - count of men N - count of chairs standing in a row (N > M + W) Each person sits on her chair, and only two men or two ...
-4
votes
1answer
56 views

The total number of subsets of a set of size 1001 is odd. [closed]

Given the statement "The total number of subsets of a set of size 1001 is odd." determine its truthfulness. I believe the answer is that the statement is false. Could someone please provide a ...
-2
votes
2answers
50 views

What is the Result of this Factorial Identity?

Provide a solution for the following sum: (c) $$\sum\limits_{i=0}^n \binom{2n}{2i} $$ Hint: use this identity: (b) $$ \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$ Could you help ...
1
vote
1answer
56 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
2answers
139 views

How large can a set of pairwise disjoint 2-(7,3,1) designs (Fano planes) be?

As wikipedia defines well, the Fano plane is a small symmetric block design, specifically a 2-(7,3,1)-design. The points of the design are the points of the plane, and the blocks of the design are the ...
7
votes
1answer
83 views

Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$

Consider the following iterative process. We start with a 2-element set $S_0=\{0,1\}$. At $n^{\text{th}}$ step $(n\ge1)$ we take all non-empty subsets of $S_{n-1}$, then for each subset compute the ...
1
vote
3answers
57 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 ...
3
votes
0answers
23 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
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
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
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 ...
0
votes
0answers
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 ...
4
votes
0answers
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 ...
-3
votes
0answers
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 ...
2
votes
2answers
2k views

Lexicographical rank of a string with duplicate characters

Given a string, you can find the lexicographic rank of the string using this algorithm: Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 ...
4
votes
1answer
39 views

How many 4 digit pins on set {0-9}

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