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)

1
vote
3answers
78 views

Number of groups containing at least 1 and at most k elements

In Counting of the elements in a set, I've been answered that the number of ways of grouping $n$ elements in $n_{G}$ groups such that each group contains at least 1 element is $$ {n-1 \choose ...
-1
votes
1answer
31 views

Binomial Coefficients (2,1) [on hold]

What are binomial coefficients? Can someone explain. For example: (2,1). or what (2n,n) means
0
votes
1answer
34 views

Proof of De Bruijn-Erdos theorem

I am reading Cameron's Combinatorics and came across following part of the proof of De Bruijn-Erdos theorem which I am unable to follow. $F$ is the family of set such that any two sets in $F$ ...
-1
votes
1answer
33 views

4096 vs 12! Binary Combinatorics in 12 bits

Given a $3\times4$ matrix keypad, each key encoded onto a unique index on a 12 bit string (0000-0000-0000), the maximum combinations are $2^{12}=4096$. However, $12$ available keys have a maximum ...
7
votes
1answer
81 views

Integer solutions of the factorial equation $(x!+1)(y!+1)=(x+y)!$

The problem is: are there solutions for the next equation? $$(x!+1)(y!+1)=(x+y)!$$ with $x,y\in\mathbb{N}$. My solution: $\left(x!+1\right)\cdot \left(y!+1\right) = \left(x+y\right)!$ ...
1
vote
3answers
57 views

Relaxed magic squares

I found the definition that a relaxed magic square of type $n\times n$ has row and column sums constant, and all numbers from $1$ to $n^2$ appears exactly once. How can one enumerate those, like how ...
1
vote
1answer
36 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
0
votes
1answer
42 views

Number of ways to divide students into groups of 4 with additional conditions

Ok, I have this question: I have the answers available but I'm struggling to get my around a few parts of the answer. So far I believe: Q1a) $(4n)!$ dictates the number possible ways of ...
0
votes
2answers
47 views

6 Professors and 8 floors - expected value

I have this problem I need help with. There are 6 professors on an elevator that has 8 floors/stops. Each professors exits the elevator randomly(1/8 chance). What is the expected value E(X) of stops ...
0
votes
1answer
59 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
-3
votes
0answers
45 views

Odd Number Query [closed]

Using the odd numbers less than 10, what smallest 4-digit odd number can be formed?
2
votes
2answers
32 views

Distinct balls into distinct boxes with a minimal number of balls in each box

Find the number of ways to distribute $8$ distinct balls into $3$ distinct boxes if each box must hold at least $2$ balls. The stars and bars approach would not work because the balls are ...
2
votes
2answers
52 views

Question of Permutation and combination

I have found a question from somewhere in the internet as follows: English language has 26 alphabets, out of 4 distinct vowels and 7 distinct consonants, how many letter patterns can be made ...
2
votes
2answers
72 views

Product rule for simplex numbers

The $n$th triangular number is defined as $T_2(n) = n(n+1)/2$, and there is an interesting product rule for triangular numbers: $$T_2(mn) = T_2(m)\,T_2(n) + T_2(m-1)\,T_2(n-1).$$ The tetrahedral ...
1
vote
4answers
72 views

Probability of drawing at least 1 red, 1 blue, 1 green, 1 white, 1 black, and 1 grey when drawing 8 balls from a pool of 30?

Given a pool of 30 balls (5 of each color). When drawing 8 balls without replacement, what is the probability of getting at least one of each color? Related: Probability of drawing at least one red ...
1
vote
1answer
31 views

proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
1
vote
1answer
49 views

Find if arrangement is possible or not

The company has k buses and has a contract with a school which has n students. The school planned to take the students to d different places for d days (each day in one place). Each day the company ...
1
vote
2answers
101 views

What algorithm do i need to solve my problem?

unfortunately I even don't know what kind of problem I deal with. But I'll try to explain as good as I can and maybe you can tell what kind of problem this is and how to solve it. I want to find ...
0
votes
1answer
32 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
33 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. ...
0
votes
0answers
18 views

Combinatorial proof of Rothe-Hagen

Wikipediate states the Rothe-Hagen identity below generalizes Vandermonde convolution: ...
3
votes
3answers
108 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
55 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
79 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
53 views

Proof by Induction Problem [closed]

There are n islands with n bridges connecting pairs of islands (where n $\ge$ 2). Prove that some sequence of distinct bridges forms a loop. Hint: Argue by contradiction: suppose there is no loop. ...
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: ...
-3
votes
0answers
32 views

graph problem homework helps [closed]

1) Prove that if all edge-costs are different, then there is only one cheapest tree. (Hint: Do a proof by contradiction, following the proof of Kruskal’s theorem. Make sure to keep track of the costs ...
-1
votes
1answer
43 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
17 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
67 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
62 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
52 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
86 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
43 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
76 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
152 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
36 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 ...