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)

-2
votes
1answer
62 views

How many unique Binary Search Trees can be created with N keys? [closed]

I have been given a set of keys $\{1,2,3,...,N\}$. How many unique binary search trees can I make with N keys?
0
votes
2answers
20 views

Set of ten distinct two-digit natural numbers

I am confused why there are $2^{10}$ (1024 subsets of distinct 10 digit natural numbers) Can someone please explain? Reference : pigeonhole principle problem : Prove that from a set of ten distinct ...
1
vote
1answer
44 views

Anagrams and related problems

I have a word like CONSTITUTIONALIST that is very fun for Anagram problems. So, in order to count the anagrams I have to: \begin{align*} s=\left\{C(2),O(2),N(2),S(2),T(3),I(3),A(1)\right\}\\ ...
4
votes
2answers
72 views

what is the meaning behind this combinatorial identity

In the following comment: Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$ $$ \binom{2n-1}{n} + \binom{2n-1}{n} = \binom{2n}{n} $$ I'm wondering about the meaning of this ...
7
votes
1answer
129 views

The Day Camp Stacking Game

My friend works at a day camp as a counselor and he told me about an interesting game he plays with his group of kids. You have a perfectly shuffled, regular $52$-card deck and a group of $2 \leq n ...
0
votes
0answers
31 views

Sperner family intersection with chains.

Consider a maximal sperner family $F$ of subsets of $X = \{ 1,2,3 \ldots n \}$. I need to prove that this family intersects with each chain of subsets exactly once. Each chain is defined as : ...
4
votes
2answers
181 views

Chess rook problem

Determine the number of ways for a rook to get from left bottom corner to top right corner of table $3\times 7$, if the rook can only move top and right. (Two ways are different if rook stops at least ...
1
vote
0answers
88 views

How many possibilities would you have in an android lock pattern, always using all 9 moves?

We are doing some research and wanted to know how many possibilities you would have if you would use all 9 dots/options in an (android) swipe lock pattern. What would the formula be to get to this ...
0
votes
0answers
32 views

K- Regular families. Proof of existence.

A family F of subsets is regular if every point lies in a constant number r of the elements of F. Theorem : Let $b,k,n,r$ be positive integer satisfying $bk = nr, k<n, b\leq $ $n\choose{k} $. Then ...
3
votes
0answers
75 views

What's so special about binomial coefficients that someone decided to organize them in a triangle?

I know that binomial coefficients are related to figurate numbers (which were studied by Greeks a loooong time ago, because of its connections to geometry). I also understand how the Pascal's triangle ...
4
votes
1answer
54 views

Order of group $GL_{2}\left( \mathbb{F}_{p}\right) $

I'm having a hard time counting. I need to count the number of elements for the multiplicative group of invertible $2\times 2$ matrices $GL_{2}\left( \mathbb{F}_{p}\right) $ with elements from the ...
0
votes
2answers
31 views

How many ways to withdraw $k$ balls from an urn with $n$ red and $m$ blue ones?

An urn contains $n$ red balls and $m$ blue balls. Of how many ways can we withdrawn a total of k balls, so that $k\le m+n$? My friend told me that there are $\binom {m+n}{k}$ ways to do that but ...
1
vote
2answers
44 views

How to show the identity relating to Matrix

Suppose that $$ A=\begin{bmatrix}a_{11}&a_{21}\\a_{21}&a_{22}\end{bmatrix}, \ \ B=\begin{bmatrix}d&-1\\1&0\end{bmatrix}. $$ and $$A=B^N$$ Show that $$a_{11}=\sum_{i=0}^{[N/2]}(-1)^i ...
-1
votes
1answer
47 views

Simplify factorials into a combinatorial formula

Is there any way to simplify this into a combinatorial formula? $$\frac{t!(n-t)!}{n!}$$
1
vote
1answer
34 views

What is the probability that each of the vehicles will be made to carry at least one local tourist?

Three vehicles (one blue, one green and one grey) with a carrying capacity of 8 passengers each are to be used to ferry 18 international tourists and 5 local tourists (who are a family) from OR Tambo ...
2
votes
0answers
48 views

What is combinatorial probability a special case of?

Once I complained to one of my undergrad math professors that I was hopelessly lost when it came to combinatorics and combinatorial probability problems. He remarked, half-jokingly, that combinatorics ...
1
vote
2answers
43 views

Combinations of $5$ cards out of $52$ that don't include $4$ aces

How would I calculate the number of different ways (order doesn't matter) I can take out $5$ cards from a deck of $52$ cards, without ending up with $4$ aces? A way would be to say that the number ...
0
votes
0answers
27 views

What's the name of $\sum_{k = 0}^{n} (-1)^k {n \choose k} (n-k)^w$?

I worked out the following expression as the number of all possible "words" consisting of exactly $w$ letters from an alphabet $L$ of size $\left|L\right| = n \leq w$, and containing each of these $n$ ...
0
votes
1answer
28 views

Count ways to sit men women in row of size K

Suppose we are given N men and M women.They are to sit in a row of size K such that no two women sit next to each other.What are the number of ways. Like if suppose their are 3 men and 2 women and ...
1
vote
1answer
23 views

What is the probability that the maximum number of shots fired successively from a type A gun is $2$?

A gun salute always takes place at the funeral of a military leader who has died in a certain country. (The $21$ gun salute where $21$ rounds are fired - is the most common for the most senior ...
3
votes
3answers
92 views

Number of attempts needed to open lock

There are $3$ knobs for a lock $A,B,C$. Each can take $8$ positions, and for each knob there is one correct position. When $2$ of the knobs are at their correct positions, the knob opens (irrespective ...
0
votes
2answers
30 views

Probability that the first $2$ balls are white, given that the sample contains exactly $6$ white balls

An urn contains $30$ white and $15$ black balls. If $10$ balls are drawn without replacement, find the probability that the first $2$ balls are white, given that the sample contains exactly $6$ ...
2
votes
2answers
80 views

Combinatorial proof of $a^n - b^n = (a - b)(a^{n – 1} + a^{n – 2}b + \dots + ab^{n – 2} + b^{n – 1})$

Is it possible to come up with a combinatorial argument which proves the following identity? $$a^n - b^n = (a - b)(a^{n – 1} + a^{n – 2}b + \dots + ab^{n – 2} + b^{n – 1})$$ My idea was this: ...
1
vote
3answers
82 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) [closed]

What are binomial coefficients? Can someone explain. For example: (2,1). or what (2n,n) means
0
votes
1answer
36 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
84 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
58 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
39 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
44 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
60 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 ...
2
votes
2answers
33 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
55 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
73 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
74 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
33 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
50 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
109 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
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
118 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
56 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 ...