This tag is for basic 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
33 views

Counting points in/on cuboid

Given a cuboid that extend in x,y,z axis such that |x|≤N, |y|≤N, |z|≤N where N is given and can have value up to 10^9.Now a shooter is standing at origin (0,0,0).He need to shoot on any of the ...
2
votes
1answer
29 views

Finite projective planes

How big a set of points in general position (i.e., no three collinear) can be found in a finite projective plane of order $n$? I hope the answers won't be too technical, as I know almost nothing ...
3
votes
0answers
34 views

Generalization of small set/large set

A small set is a subset of the positive integers, such that the infinite sum of the reciprocals of the members of the set converges. Conversely, the sum of the reciprocals of a large set diverges. ...
1
vote
0answers
22 views

Combinatorial proof of Rothe-Hagen

Wikipediate states the Rothe-Hagen identity below generalizes Vandermonde convolution: ...
3
votes
3answers
120 views

Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$

I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k ...
3
votes
3answers
57 views

difficult problem about binomial coefficients

If $r,m,n\in \mathbb N$ so that $r\le \min \{n,m\}$, then $$\binom{n+m}{r} = \binom{n}{0}.\binom{m}{r}+\binom{n}{1}.\binom{m}{r-1}+...+\binom{n}{r}.\binom{m}{0}.$$ If $\min \{n,m\} < r$, then how ...
1
vote
3answers
89 views

Password combinatorics.

Sorry for yet another password/combinatorics problem but I haven't seen this one answered yet. Let's say I must pick a $12$-character password that has $2$ uppercase, $2$ lowercase, $2$ digits, and ...
2
votes
2answers
71 views

Growth Rate of Alternating Sign Matrices

I am trying to compute the best growth rate for the following sequence $$ a_n=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} $$ This sequence counts the number of $n\times n$ alternating sign matrices: ...
-1
votes
1answer
47 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
1
vote
0answers
18 views

Gallai & Milgram path covers theorem from Diestel

I have a question about the theorem of Gallai and Milgram stating that every directed graph has a path cover $P$ such that one can make an independent set of $G$ by picking vertices from each of the ...
2
votes
2answers
69 views

Why does this sum equal to (4^n -1)

How do I get to this solution? $\sum _{k=1}^n\left(\binom nk 3^{n-k}\right)=\left(4^n-1\right)$ I believe it's connected to this, which I know is true: $\sum \:_{k=1}^n\binom nk=2^n-1$
0
votes
1answer
42 views

A combinatorics problem involving geometry

Find the number of triangles that can be formed in a regular polygon of $2n+1$ sides such that the center of polygon lies inside the triangle. (The triangles are to be formed using the vertices of ...
2
votes
3answers
63 views

Placing symbols so that no row remains empty.

Q.1.The symbols +, + , #, # , *, $ ($6$ in total) are to be placed in the squares of the given figure. Find the number of ways of placing the symbols so that no ...
0
votes
1answer
24 views

path finding: calculating the optimal path, where “optimal” means maximum distance within a given time

Not sure if this is the right place to ask this, but here's my problem: I have a large set of points, where each point represents a coordinate. I need to develop an algorithm that calculates which ...
1
vote
3answers
53 views

Rational numbers and periodic decimal representation

I'm trying to prove that a number is rational if and only if it has an eventually periodic decimal expansion. One part is simple; without loss of generality we consider $q=0.\overline{d_1\dots d_k},$ ...
1
vote
2answers
90 views

Probability of assigning balls into buckets, where each bucket has a certain capacity.

I'll start with a specific example of what I am trying to solve: I have eight balls to be randomly placed into four buckets. Buckets #1-3 have the capacity of 2, 2, 3 respectively, while bucket #4 ...
0
votes
1answer
38 views

is the probability of selecting a completely even family $\frac1{2^ n}$?

let $A$ be a set with $N$ elements, and for $0 \le M_{\mathfrak{B}} \le 2^n$ let $\mathfrak{B} =\{B_j\}_{j=0 \cdots M_{\mathfrak{B}}}$ be a a random variable whose value is a family of subsets of $A$, ...
1
vote
2answers
53 views

Counting words with specific requirements

How many words of length exactly 6 can be created from letters A,B,C,D,E,F, so that each word has not more than one A, not more than one B, not less than one C and not less than one D? I've tried ...
0
votes
0answers
44 views

What can we say about shape of intersection area of $N$ disks on a plane?

Intersection area of two disks can be bounded by at most two arcs. Intersection area of three disks can be bounded by at most four arcs. It looks like (I'm not sure) that four disks can have common ...
2
votes
0answers
39 views

$24$ people in groups of $3$ where everyone meets exactly once at the end of some number of rounds

I was presented with this problem at work. Say you have $24$ people and $8$ tables in a room. You want to set people at these tables in groups of three such that during each new round (where people ...
3
votes
0answers
80 views

Clash of Clans Permutations

I'm not an expert mathematician (I'm 16) and I'm Italian, so please try to understand my question and forgive my poor language. Thank you. When I play Clash of Clans, I ask me "How many buildings ...
5
votes
3answers
153 views

How many ways can 5 dice produce a total of 20?

How many ways can $5$ dice produce a total of $20$? I set up the equation $x_1+x_2+x_3+x_4+x_5 = 20$. The total possible number of combinations is $\binom{19}4$. From there I subtracted the ...
0
votes
1answer
19 views

Backsolving Counting Problem

Lauren mixes and matches all of her jeans, skirts, and vests to make different outfits. If she can make a total of 24 different outfits, each consisting of one pair of jeans, one shirt, and one vest, ...
1
vote
1answer
82 views

proving that: $(\frac{13}{4})^n\leq a(n)\leq (\frac{10}{3})^n$

Given $a(n)$ number of sequences of length $n$ that are formed by the digits: $0,1,2,3$ such that after the digit $0$ the digit $1$ must immediately follow. Need to prove that $(\frac{13}{4})^n\leq ...
1
vote
0answers
59 views

Integer partitions without rotated solutions?

I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of ...
6
votes
1answer
32 views

Equivalent of a sequence in regard to a certain length of a cycle for $\mathfrak{S}_{n}$

Let $n \in \Bbb{N}$ ( for me $0\notin \Bbb{N})$. Find the limit as $n$ tends to $+ \infty$ of the following sequence $$\frac{\alpha_{n}}{n}$$ where $\alpha_{n}$ is the number of permutations of ...
4
votes
1answer
37 views

Simplicial complices on unlabelled vertices

My question is about (abstract) simplicial complices. In particular, how many are they if I consider $n$ unlabelled vertices? For example, if $n=4$, the two complices $$ \{\varnothing, \{1\}, \{2\}, ...
0
votes
3answers
49 views

Recursion Problem [closed]

a) Ten people are sitting in a row of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ...
0
votes
1answer
23 views

Cardinality of finite sets: if $B=\{a-b \mid a,b \in A\}$ and $C=\{a+b \mid a,b \in A\}$, then $|C|^2\ge |A||B|$

Let A be a finite set of real numbers. Suppose $B=\{a-b \mid a,b \in A\}$ and $C=\{a+b \mid a,b \in A\}$. Prove that $|C|^2\ge |A||B|$. I tried to solve this in this way: We claim that the function ...
0
votes
2answers
31 views

How many ways can we get 2 a's and 2 b's from aabb?

We have the following group: $aabb$ It is commutative, so abab is the same as aabb. I have figured out this is a combinatorics question. Because abab is the same as aabb. I was how to solve these ...
0
votes
0answers
74 views

A new combinatorics identity— similar to Catalan number

I find a combinatorics identity during my study, but fail to prove it.$$\sum_{i=0}^{[M/2]}(-1)^i\frac{(3M-1-2i)!}{(M-2i)!i!(2M-i)!} = \frac{1}{2M}\big(_{M}^{2M}\big)$$ where $M=1,2,3\cdots$. Note than ...
1
vote
2answers
82 views

Names of 3 input logic gates

I've tried to look this up online, I may have used the wrong terminology. This question is about the names of logic gates with three boolean inputs, and one boolean output. This is a truth table for ...
1
vote
3answers
45 views

Number of license plates formed by four digits and one letter, qualified.

I need some help with this question: If a license plate for a vehicle consist of five characters: $4$ digits (the first of which cannot be $0$), followed by one letter of the alphabet (which ...
8
votes
0answers
139 views
+100

How to estimate $Pr[vr_i=ur_i]$ in the presence of rotations

Suppose we want to compute the probability that for two different random vectors (with elements that are $0$ or $1$), denoted by $v$ and $u$, multiplying them with the rotations of a random vector $r$ ...
-1
votes
1answer
30 views

In how many of the possible arrangements will both end balls be of the same colour? [closed]

6 blue balls, 4 red balls, and 2 white balls are placed in a straight line. In how many of the possible arrangements will both end balls be of the same colour?
1
vote
2answers
58 views

How to understand the combination formula?

I'm reading an algorithm book. In which it mentioned: Imagine (once again) you have n people lined up to see a movie, but there are only k places left in the theater. How many possible ...
0
votes
2answers
42 views

Arrangements of n pairs of socks on a clothesline

n pairs of socks are hung side by side on a clothesline. The socks in each pair are identical and the pairs are different colours. How many different colour patterns can be made if no sock is next to ...
0
votes
2answers
33 views

Probability of getting sum on 3 dice rolls

The integers $1$ through $6$ appear on the six faces of a cube, one on each face. If three such cubes are rolled, what is the possibility that the sum of these numbers on the top faces is $17$ or ...
0
votes
3answers
36 views

Decide to use Factorials or nCr

Five different bands have been selected to march in a parade. One band has been chosen to lead the parade. In how many different orders can the remaining 4 bands be placed in the parade? I don't ...
0
votes
0answers
16 views

Embed one Coxeter System into another

What is a good reference that explains all the braid relations and diagrams for Coxeter systems concisely? In particular, how do I embed $H_3$ inside $D_6$, or $H_4$ inside $E_8$? Any hints?
0
votes
1answer
72 views

Discrete Math Clause Count Question

Ok, I'm completely lost if anyone could hint me through some of the first steps that would be hugely appreciative!! In a CNF formula, a clause contains one or more terms. Each term is either a ...
3
votes
3answers
33 views

factorials vs nCr: Does order matter in this probability problem?

The figure above shows 5 walkways, R,S,T,U, and V, leading to and from a momument. Carlos will take one walkway to the mounment and will leave by a different walkway. From how many different pairs ...
0
votes
1answer
43 views

Arrangement on a regular polygon

If $N$ people are to be arranged around a $K$ sided regular polygon such that each side of that polygon will have equal number of people, then what would be the number of arrangements?
1
vote
1answer
19 views

Proving partial greedy property for minimal knight's path between two squares on unbounded chess board

I was thinking about how to write a computer program to find the path with minimal number of moves that takes a knight from one square $(x_1,y_1)$ to another square $(x_2,y_2)$ on an unbounded chess ...
9
votes
3answers
123 views

Number of elements of order $2$ in $S_n$

How many elements of order $2$ are there in $S_n$? Using combinatorics I arrived at this: For $n$ even ($n=2k$) there are ${n\choose2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2} ...
2
votes
2answers
95 views

Prove that two elements of $A$ should differ by 3.

Let $A$ consist of $16$ elements of the set $\{1,2,3,...,106\}$ so that no two element differ by $6,9,12,15,18$ or $21$. Prove that two elements of $A$ should differ by 3.
1
vote
1answer
26 views

Growth rate of ordered bounded partitions

Let $P_n(k,i)=|\{(d_1,\cdots,d_i): \ \sum_{j=1}^id_j=n, \ \forall j\ 1\leq d_j\leq k\}|$, the number of ordered partitions of $n$ into $i$ parts with individual parts bounded by $k$, with no piece ...
4
votes
2answers
97 views

Can 12 teams in 6 disciplines play 6 rounds without repetition?

Consider the following tournament: There are 12 teams, 6 disciplines and 6 rounds, each round and each event happens simultaneously. Is it possible to create a tournament such that no team does the ...
0
votes
1answer
31 views

Probability for incomplete information

Let's say there are 10 teams: A-J. Only 1 team wins, others lose. Probability of any team to win is unknown (different for each team) and to be calculated. Not all teams participate in each game. ...
0
votes
1answer
35 views

How to calculate probability that a team will win

Let's say there are 10 teams: A-J. Each team always participate in each of the game. Only 1 team wins, others lose. Probability of any team to win is unknown (different for each team) and to be ...