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
0answers
33 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 ...
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 ...
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 ...
8
votes
1answer
245 views

Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices. We focus on closed walks of length $2L$. Such walks can be described by the sequence of ...
1
vote
1answer
267 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
0
votes
2answers
32 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
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!}$$
2
votes
4answers
132 views

Log concavity of binomial coefficients: $ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $

How do we prove that Binomial coefficients are log-concave? A sequence $a_0, \dots, a_n$ is log-concave if $a_k^2 \geq a_{k-1}a_{k+1}$. $$ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $$ If $ n ...
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 ...
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 ...
5
votes
6answers
2k views

Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $

[Corrected question] I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, ...
3
votes
3answers
124 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
1answer
283 views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
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 ...
0
votes
4answers
30 views

In how many ways can we arrange $n$ A's and $n-1$ B's into $2n-1$ slots?

There are $2n-1$ slots/boxes in all and two objects say A and B; total number of A's are $n$ and total number of B's are $n-1$. (All A's are identical and all B's are identical.) In how many ways ...
3
votes
3answers
93 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 ...
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 ...
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 ...
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$ ...
3
votes
2answers
28 views

Size of the collection of permutations of a set in which all elements appear

Say I have a set $A$ consisting of a finite number $N$ of elements, e.g. $A = \{1, 2, 3, 4\}$ for $N = 4$. What is the size of the collection of all possible permutations of the set $A$ into subsets ...
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 ...
2
votes
2answers
81 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: ...
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$ ...
-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
2
votes
2answers
77 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
3
votes
1answer
500 views

What is the maximum number of combinations with repetitions, that the sum could be the same?

Suppose I have $n$ integers (both negative and positive) and I get all combinations of $k$ elements with repetition $((n, k)) = (n + k-1, k)$ My question is: what is the maximum number of ...
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$ ...
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
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 ...
5
votes
3answers
86 views

Ordered partitions of an integer (with a twist)

I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has ...
1
vote
1answer
40 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
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 ...
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 ...
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
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 ...
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
1answer
85 views

How many combinations does Android pattern have?

Rules- 1) At-least 4 and at-max 9 dots must be connected. 2) There can be no jumps 3) Once a dot is crossed, you can jump over it.
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},$ ...
2
votes
2answers
56 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 ...
1
vote
4answers
75 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 ...
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
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 ...
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
2answers
454 views

How many 90 ball bingo cards are there?

In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three ...
2
votes
0answers
31 views

Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
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 ...
1
vote
1answer
133 views

How to form a simplicial complex?

Reference: Combinatorial Commutative Algebra by Miller and Sturmfels. I have difficulty getting started with Miller and Sturmfels, when I read the first few pages, as I do not know where simplicial ...
1
vote
0answers
22 views

Combinatorial proof of Rothe-Hagen

Wikipediate states the Rothe-Hagen identity below generalizes Vandermonde convolution: ...
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
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 ...