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
1answer
157 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
493 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
446 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
340 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
625 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
295 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
52 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
179 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
94 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
167 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
149 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
364 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
830 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
132 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
139 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
108 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
152 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
287 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
55 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
300 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
166 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
143 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
39 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
174 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
107 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
101 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
74 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
313 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
72 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
77 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
173 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
175 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
294 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 ...
3
votes
5answers
99 views

Counting strings containing specified appearances of words

Is there a nice formula (or generating function) for the number of binary strings of length $n$ that contain exactly $k$ appearances of a specified word $w$? For instance, among the binary strings of ...
2
votes
1answer
103 views

Construct a generating function for the components of a sum

Let $j \in Z_+$. Set $$ a_j^{(1)}=a_j:=\sum_{i=0}^j\frac{(-1)^{j-i}}{i!6^i(2(j-i)+1)!} $$ and $a_j^{(l+1)}=\sum_{i=0}^ja_ia_{j-i}^{(l)}$. Find generating function $\sum_{j}a_jx^j$ so that allows to ...
1
vote
3answers
68 views

Sam has to go to work from home. Sam moves either SOUTH or EAST when going to work. How many distinct routes are there for sam to go to work?

The following figure depicts the paths from home to work. SAM never travels through the park when going to work.
1
vote
2answers
175 views

Permutations and Combinations

How many ways are there to find the number of permutations of the elements in $\;\{1,2, 3, 4, 5\}\;$ such that it has one cycle of length $2$ and one cycle of length $3$? Please be as descriptive as ...
4
votes
0answers
176 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
1
vote
1answer
153 views

Finding the residue of function with Laurent series $\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\frac{y^n(A+By+Cy^{-1})^k}{\beta (\beta i)^n \ k!}$

I have been trying to find the residue of $f(\omega) = \frac{e^{i \omega a} e^{\frac{-b \omega}{\omega + ib}}}{i \omega}$ at the essential singularity $\omega = -ib$ for a while, but it is giving me ...
0
votes
1answer
660 views

Combinatorics: How many subsets of size k are there in a group of N elements?

Updating the question after some comments. If I have a multiset consisting of elements {1, 1, 2, 2, 3}. How can I mathematically find the number of distinct sub-multisets with size 2? The answer for ...
0
votes
1answer
32 views

Placing reservations on boxes when using the Pigeonhole Principle

I am choosing $m+1$ integers from the set $\lbrace 1,2,\ldots 2m\rbrace$, and I want to use the Pigeonhole Principle to show that two of the numbers chosen differ by $1$. I want to know if my strategy ...
2
votes
2answers
146 views

Number of Permutations of a Cycle with no cycle greater than 11.

I'm looking for the number of permutations of a $20$ element set, with no cycle greater than length $11$. All of the attempts that I have tried are not working out. I'm not sure how to get started on ...
1
vote
4answers
165 views

Binomial Theorem

By finding appropriate values for $x$ and $y$, evaluate $$\sum_{k=0}^{n} k(k-1)\binom{n}{k}$$ I thought to take the derivative of $(1 + x)^n$ twice, but I noticed the index on $k$ remained at $0$.
40
votes
7answers
918 views

Problems regarding $\{x_n \}$ defined by $x_1=1$; $x_n$ is the smallest distinct natural number such that $x_1+…+x_n$ is divisible by $n$.

Let me denote a sequence of distinct natural numbers by $x_n$ whose terms are determined as follows: $x_1$ is $1$ and $x_2$ is the smallest distinct natural number $n$ such that $x_1+x_2$ is divisible ...