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)

7
votes
2answers
306 views

Combinatorial argument for the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$

I am looking for the combinatorial argument for the identity: \begin{equation} k\binom{n}{k} = n\binom{n-1}{k-1} \end{equation} This is easy to show algebraically as: \begin{equation} \binom{n}{k} ...
0
votes
1answer
38 views

How many ways are there to express 24 as the sum of 4 2's and 16 1's where the order counts and there are never successive 2's?

I'm having trouble making sure order counts and that there are never successive 2's.
2
votes
2answers
793 views

Finding Binomial expansion of a radical

I am having trouble finding the correct binomial expansion for $\dfrac{1}{\sqrt{1-4x}}$: Simplifying the radical I get: $(1-4x)^{-\frac{1}{2}}$ Now I want to find ${n\choose k} = ...
0
votes
2answers
6k views

In how many ways can the students answer a 10-question true false examination?

(a) In how many ways can the students answer a 10-question true false examination? (b) In how many ways can the student answer the test in part (a) if it is possible to leave a question unanswered ...
2
votes
2answers
88 views

Combinatorical meaning of an identity involving factorials [duplicate]

While solving (successfully!) problem 24 in projectEuler I was doodling around and discoverd the foloowing identity: $$1+2\times2!+3\times3!+\dots N\times N!=\sum_{k=1}^{k=N} k\times k!=(N+1)!-1$$ ...
2
votes
1answer
2k views

Sum of combinations of n taken k where k is from n to (n/2)+1

I wonder if there's a formula for obtaining the sum of $n\choose k$'s where $k$ is from $n$ to $\frac{n}{2}+1$. I found out that in odd numbers, it is $2^{n-1}$ (powerset divided by $2$). 1 = 1 3 = ...
0
votes
1answer
109 views

In how many ways can four squares, not all in the same row or column, be selected from an $8 \times 8$ chessboard to form a rectangle?

I know this involves creating a combinatorial argument but this problem is really complex.
2
votes
1answer
91 views

Is this a Permutation or a Combination?

To win a lottery, you must pick the winning 3 numbers from the integers 1-9 (no repeat numbers). What is the probability of winning the lottery by choosing the correct 3 numbers? I think its a ...
2
votes
1answer
623 views

How can I find the number of the shortest paths between two points on a 3D lattice grid?

A similar question has been asked here , but what if we want to find the shortest path between two points in a 3d-space? Of course we are jut allowed to move along the lattice.
2
votes
0answers
62 views

Combinatorics (splitting integral)

I am trying to split an integral in a way that the integrating region becomes "symmetric" i.e. for a fixed $p=1,\dots,m$, $$\int_{s<u_1<\cdots u_m<t}\int_{r<v_1<\cdots< v_n<u_p} ...
5
votes
0answers
224 views

Closed form expression for constants

We have the constants $c_{k,n}$ defined by : $$c_{k,n}=\frac{d^{k}}{ds^{k}}\left(\frac{e^{\frac{1}{n(ns-1)}}e^{\psi\left(\frac{s-1}{s} \right )}}{s} \right )$$ Where $\psi(s)\;$ is the Digamma ...
8
votes
1answer
165 views

the number of positive-integer solutions that satisfy $x_1\cdot x_2\cdot x_3\cdot x_4=1,000,000$?

I can't solve the following: Find the number of positive-integer solutions that satisfy $x_1\cdot x_2\cdot x_3\cdot x_4=1,000,000$. Thanks.
0
votes
1answer
533 views

Determine the number of six-digit integers (no leading zeros) in which no digit may be repeated and divisible by 4?

Determine the number of six-digit integers (no leading zeros) in which no digit may be repeated and divisible by $4$? I've tried solving this problem, but the result is different with the solution ...
0
votes
2answers
499 views

A probability problem - probability of one card being red and the other one being black.

Consider a deck of 50 playing cards (2 cards missing). What is the probability that one of them is red and the other one is black? I've got two solutions which one is correct ? Let $R$ represent red ...
3
votes
1answer
380 views

Triangle from a given rectangle

We are given a set of (marked) points in a 2D coordinate system and function $f(x,y)$ which counts number of points marked in the rectangle $(0 , 0), (x , y)$ - where $(0 , 0)$ if down-left corner, ...
0
votes
1answer
675 views

2 Problems on Palindrome of Five Letters: A Letter appears more than twice and no letter does so.

A sequence of letters of the form $abcba$, where the expression is unchanged upon reversing order, is an example of a palindrome (of five letters). (a) if a letter may appear more than twice, how ...
6
votes
3answers
310 views

Combinatorial proof involving factorials

Show that $$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$$ I tried thinking of what the LHS summand could possibly be (permutation, combination), but I can't come up with ...
1
vote
0answers
53 views

Proving by Pigeonhole Principle [duplicate]

Considering the case where the numbers 1 through 10 are in some order around a circle. Prove that some set of three consecutive numbers sums to at least 18.
0
votes
0answers
60 views

A tough counting question: Specified order

Assume that there are $3n$ people in the population. These people are ranked randomly and uniformly. ( that is, each permutation is equally probable) There is a competition and $m+1+k$ people among ...
0
votes
1answer
72 views

Combinatorics - Colouring

I have a colouring of the edges of $K_{11}$. I need to prove that there is a vertex $v$ such that at least $6$ of the edges incident to $v$ are the same colour. I think a proof by contradiction is the ...
3
votes
2answers
198 views

My answer to a combination problem is different from the textbook answer.

The question in full goes as follows: How many $5$-digit numbers can be formed from the integers $1,2,\dots,9$ if no digit can appear more than twice? (For instance, $41434$ is not allowed.) I ...
1
vote
1answer
100 views

Combinatorics/Permuation question - Am I overcounting? (Verify my answer)

There is a problem on a recent test of mine and i am wanting to know now rather than later how i did on the question. The question was: How many variations can a 11 digit number have, consisting of ...
5
votes
1answer
175 views

Formula for evaluation of character on a transposition

Let $\lambda\vdash n$ be a partition of $n\in\mathbb N$ and $\chi=\chi_\lambda$ the corresponding irreducible character of the symmetric group $S_n$. Denote by $\lambda^t$ be the transpose of ...
2
votes
1answer
151 views

The number of ways to put numbers in squares

If one put the numbers from $1$ to $7$ in the squares in stead of letters in which the sum of cells is in descending order like shown in the figure .Every number should be used once or twice or ...
2
votes
1answer
41 views

least number of planes intersecting a finite number of points in space, but not intersecting origin.

Let $$\mathbb{R}^*=\mathbb{R}-\{0\}$$ and $$N=\{0,...,n\}$$ and $$\mathcal{M}=\{ A\subseteq \mathbb{R}^3\times\mathbb{R}^* \mid (\forall\mathbb{x}\in N^3:\mathbb{x}\ne 0)(\exists(\mathbb{a},d)\in ...
10
votes
4answers
368 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
1
vote
1answer
62 views

Probability of winning of teacher

Teacher is playing a game with his students. He is having $k$ red balls. Each of his student is either having a red or black ball. $M$ students have red balls and $N$ students have black balls. Now ...
8
votes
7answers
927 views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
1
vote
1answer
138 views

Moore neighborhood on a two-dimensional Cartesian lattice

How many distinct cellular automata rules are there that use the Moore neighborhood on a two-dimensional Cartesian lattice if we allow three bits (eight states) per site?
1
vote
1answer
143 views

How many words can be obtained using 2n letters?

Given n letters 'A' and n letters 'B', how many unique words can be obtained using all 2n letters? Or how many unique arrangements exist for those letters? Why is the answer $C_{2n} ^n = ...
2
votes
2answers
119 views

Feature of the Pascal's triangle (OEIS A007318)?

If rows of Pascal's triangle (OEIS's A007318) after their content concatenation {1-1, 1-2-1, 1-3-3-1, 1-4-6-4-1, 1-5-10-10-5-1, 1-6-15-20-15-6-1, 1-7-21-35-35-21-7-1 and so on } be considered as ...
0
votes
1answer
157 views

Bins in balls where bin size grows exponentially

I have $k$ bins. The first bin can fit $1$ ball. Each subsequent bin can fit two times more balls than the previous one. In other words, the $i$th bin can fit $2^i$ balls. We randomly assign $U = ...
2
votes
0answers
288 views

Prove that sum is finite with the help of generating function

Please help me to prove that the following sum is finite $$ \sum_{j=2l-2}^{\infty}j!\, a_j^{(l)}, $$ here the generating function of $\displaystyle{a_j^{(l)}}$ is ...
3
votes
2answers
56 views

Obtaining certain pairs of numbers using three “machines”

Each of three machines can read a card on which is written a pair of whole numbers $(m,n)$ and print a new card. Machine $\text{A}$ reads $(m,n)$ and prints $(m-n,n)$. Machine $\text{B}$ ...
1
vote
1answer
342 views

tHow many ways we can partition a set S into two subsets under the following restrictions?

How many ways we can partition a set S into two subsets such that: The set $S$ can have $n$ elements in the range $1$ to $1000$ (inclusive). Let the two subsets be $A$ and $B$. For all $x$ in range ...
1
vote
2answers
171 views

$n$-digits numbers made of 1, 2, 3, such that none of two consecutive digits differ by more than one

We call a number to be good if none of two consecutive digits differ by more than one. How many good $n$-digits numbers made from digits $1$, $2$ and $3$ are there? For example, $12232$ is good, ...
0
votes
0answers
144 views

Tricky Combinations Problem with Repeats

Let's say I have $18$ elements, $\{A_0, A_1, B_0, B_1, ... I_0, I_1\}$ Now I want to form a sequence of sets, where each element of the sequence is a set of size $3$, where the sets form a ...
2
votes
1answer
42 views

Numbers of solutions of $ \sum_{i=1}^{k}x_i=n $ in $\mathbb{N}_0$

In a certain problem, the solution states that number of solutions of $a+b+c+d=13$ is $\binom{16}{3}$, so I'm guessing that my following statement is true: The number of solutions of $$ ...
8
votes
2answers
182 views

Connect $n$ white and $n$ black points

$n$ black and $n$ white points are drawn on plane, so that no three of them lay on one line. How to prove that we can connect each white point to some black point by straight segment so that no two ...
2
votes
1answer
111 views

How to simpify the following equation involving binomial coefficients?

How can one simplify this equation: $$ \sum_{k=0}^{n-1}\binom{n}{k}\binom{n}{k+1} $$
6
votes
1answer
121 views

Arithmetic; count + divisibility

Let there be $101$ numbers arbitrarily chosen from the first $200$ whole numbers $1,2, \ldots ,200$. Prove that among the chosen numbers there is a pair of numbers such that one them is divisible by ...
1
vote
0answers
102 views

Probability proof and combinatorics

I was asked to use the factorial definition of ${m \choose r}$ to verify that the equalities hold: $${n \choose k}k = {n \choose k-1}(n-k+1) = n {n-1 \choose k-1}$$ The answer is \begin{align*} {n ...
2
votes
1answer
83 views

What is the degree of the fourier expansion

Let $ f:\{-1,1\}^3 \rightarrow \{-1,1\} $ , $f(x)= \operatorname{sgn}(x_1+x_2+x_3)$; (Majority function), then Fourier expansion of $f$ is $f(x)= \frac{1}{2} ...
7
votes
1answer
320 views

On Magnitudes of Sums of Roots of Unity and a Simple Trigonometric Inequality

The Problem Let $r,q,m$ be positive integers such that $4 \leq r$ and $1<m,q\leq r/2$. Is it the case that $$\left | \sum_{k=0}^{q-1} \zeta^{km}\right | < \left |\sum_{k=0}^{q-1} ...
1
vote
1answer
77 views

How to find the number of combinations in which a class of elements always has to be included?

Say I have a set $\{A, B, C, D, E, F\}$ and I have to find how many sets of four elements I can make from these that must include at least any two elements from the set $\{D, E, F\}$? On a similar ...
3
votes
1answer
81 views

Prove by using Pigeon Hole Principle

Let $k \in \mathbb Z^+ $. Prove that there exists a positive integer $n $ such that $k|n$ and the only digits in $n$ are 0's and 3's
1
vote
1answer
180 views

Prove using Pigeon Hole

Prove that if select $101$ integers from the set $S = \{1,2,3,...,200\}$, there exist $m,n$ in the selection where $\gcd(m,n) = 1$! Any hint how to prove this?
2
votes
1answer
184 views

Solving for the closed form of a recurrence relation

Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and ...
3
votes
5answers
323 views

Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)

Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
1
vote
3answers
135 views

Induction proof of $\sum_{k=1}^{n} \binom n k = 2^n -1 $

Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$. Today I wrote calculus exam, I had this problem given. I have the feeling that I will get $0$ points for my ...