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)

1
vote
1answer
55 views

Stirling number of Second kind generating function

I would like to prove that: $$f_m(x) = \dfrac{x^m}{(1-x)(1-2x)...(1-mx)}$$ Where $$f_m(x) = \sum_{n=0}^{\infty} S(n,m)x^n$$ and $S(n,m)$ is stirling number of 2nd kind Multiplying the recurrence ...
0
votes
1answer
210 views

Probability that the tallest and shortest person are sitting next to each other if they cannot sit at either end?

Eight people of different heights are to be seated in a row. The shortest and tallest in this group are not seated at either end. What is the probability that: (a) The tallest and shortest ...
2
votes
2answers
208 views

number of ways to stack n distinct objects into k distinct boxes

I know that number of ways to distribute $n$ distinct objects into $k$ distinct boxes is $k^n$, but there order of objects in a box doesn't matter. If we want to stack objects in a box, then order ...
1
vote
1answer
46 views

Probability that either one, but not both is chosen

A basketball team of 5 is to be selected from 12 players. Find the probability that either one, but not both of the captain or vice-captain are selected. So I thought the answer is: $$2\frac{{10}\...
0
votes
2answers
66 views

Given a number N how many pairs of numbers have square sum less than or equal to N?

Let's define $F(N)$ as the number of pairs of distinct positive integers $(A, B)$ such that $A^2 + B^2 \leq N$ If $N=5$ the only possible such pair is $(1, 2)$, for $N=10$ the pairs are two: $(1,2)$ ...
1
vote
3answers
65 views

Share $m$ candy bars for $n$ people

Assume that we have $m$ candy bars and $n$ people. Each candy bar can be divided into at most two pieces (not necessarily equal). Find the necessary and sufficient condition of $(m,n)$ such that $m$ ...
7
votes
6answers
528 views

What's wrong with my permutation logic?

The given question: In how many ways the letters of the word RAINBOW be arranged, such that A is always before I and I is always before O. I gave it a try and thought below: Letters A, I and ...
1
vote
1answer
43 views

Finding recurrence relation 2 - Ternary sequences. [duplicate]

for $n \ge 1$ , Let $f(n)$ be the number of ternary sequences {$0,1,2$} of length n, that the sum of their characters are even, and they have at least one show of $0$. How do i find the recurrence ...
1
vote
1answer
165 views

Number of distinct cycle in complete undirected graph of length $4$?

Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$ My attempt : ...
1
vote
1answer
35 views

Combinatorial Probabilities

I've been trying out some of the early problems in the probabilistic method, since I hear it can prove many problems in discrete mathematics. Let $A_1,..., A_n$ be events such that the independent of ...
8
votes
5answers
364 views

An interesting Sum involving Binomial Coefficients

How would you evaluate $$\sum _{ k=1 }^{ n } k\left( \begin{matrix} 2n \\ n+k \end{matrix} \right) $$ I tried using Vandermonde identity but I can't seem to nail it down.
5
votes
1answer
34 views

Manipulation with strings riddle.

Starting with the "string" $PI$, can I or not transform it into the "string" $PK$ by applying the following rules (each rule can be used any number of times, in any order, and $x$ and $y$ represents a ...
6
votes
5answers
263 views

All the ternary n-words with an even sum of digits and a zero.

I'm trying to find a recursive formula for all the ternary (using ${0,1,2}$) sequences of length $n$ which contain at least one zero, and have an even sum of digits. My attempt so far is added below. ...
8
votes
1answer
78 views

How many rectangles are there on an $8 \times 8$ checkerboard?

How many rectangles are there on an $8 \times 8$ checkerboard? \begin{array}{|r|r|r|r|r|r|r|r|} \hline & & & & & & & \\ \hline & & & & &...
5
votes
3answers
145 views

Combinatorial argument for an identity

Consider the following equation: $x_1 + x_2 + \cdots + x_r = n,~~$ where $~~0\leq x_{i}\leq n, \forall i$ The number of integral solutions to the above equation = ${n+r-1 \choose r-1}$. Consider ...
0
votes
1answer
92 views

How do i solve the recurrence: $f(n)=F(n-1)+f(n-2)+1$

How do i solve the recurrence: $f(n)=F(n-1)+f(n-2)+1$? My first attempt was to "guess" a private solution to the nonhomogenous which got me : $ f(n)= -1 $ and the corresponding is $F_n$ (fibonacci), ...
0
votes
2answers
47 views

Number of ternary sequences ${0,1,2}$ of length n without two consecutive even numbers.

(I edited the question and erased my last try, cause my understanding of it, was poor) any help would be appreciated.
0
votes
0answers
34 views

Number of ways to choose colored points equality

Let $n$ be a positive integer and $S$ the set of points $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers such that $x +y<n$. The points of $S$ are colored in red and blue so that ...
2
votes
1answer
59 views

Number of ways to obtain n as sum of 1,…,m

Let $m \leq n $. I want to find the number of ways $N$ in which $n$ can be written as a sum of elements in $\{1,\ldots, m\} $, with repetitions. For example, if $n=5$ and $m=3$, then $N=13$, because $...
3
votes
1answer
72 views

Permutations of the natural numbers that leave a finite set fixed

I´m going through the forcing proof of the relative consistency of `every set can be linearly ordered' to ZF. I'm stuck on some technical details regarding permutations of the natural numbers that ...
3
votes
0answers
42 views

value if $\binom{n}{c}$ when $n$ is a positive integer and $r$ is a negative integer

The formula we use for ncr is $\frac{n!}{(n-r)!r!}$ for example, $\binom{5}{2}= \frac{5!}{2!3!} = 10$ Special case is also there $\binom{n}{0}=1$. As per the formula, $\binom{n}{0} = \frac{n!}{0!n!}...
1
vote
0answers
30 views

Number of distinct connected undirected graphs possible with n nodes and k edges [duplicate]

Given $n$ labelled nodes and $k$ edges, how many number of distinct connected undirected graphs are possible? There can be only one edge between a pair of nodes and cycles are allowed. I came up with ...
3
votes
3answers
55 views

Compute the minimum number of seconds necessary for Kevin to evaluate the expression together by performing eight such multiplications

For the NEMO, Kevin needs to compute the product $$9 \times 99 \times 999 \times ··· \times 999999999.$$ Kevin takes exactly $ab$ seconds to multiply an $a$-digit integer by a $b$-digit integer. ...
1
vote
1answer
77 views

For give permutation $\sigma\in S_{13}$ solve equation $x^3=\sigma$

We have this permutation $$\sigma =\left({\begin{array}{*{20}c}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ 3 & 2 & 1 & 11 & ...
1
vote
2answers
83 views

Number of ways in which 6 rings can be worn on the 4 fingers of one hand

The way I solved this is - The 1st finger can have any of the 6 rings, $\therefore 6$ ways The 2nd finger can have any of the 5 remaining rings, $\therefore 5$ ways The 3rd finger can have any of ...
1
vote
4answers
77 views

Combinatorial problem : How many ways can you choose 3 balls from nine such that no two of them are consecutive?

I tried approaching this problem by first assuming that all the balls are chosen from the odd places(10) only and then the even places only(6). And then adding them together. However, my approach ...
4
votes
1answer
72 views

Double Summation Over all subset of $\{1,2,…n\}$

In Benson's Book "Polynomial In variants of Finite Groups" It is claimed that(Without any proof): $$ j! u_1u_2...u_j =\sum_{I \subseteq \{1,2,...,j\} } (-1)^I (\sum_{i \in I}u_i)^j$$ Where $I$ runs ...
0
votes
1answer
34 views

Arrangement of people in 2 taxis.

Find the number of ways in which 6 people can be seated in 2 taxis of 4 seats each if internal arrangement matters. My answer is $\frac{6!6!}{4!2!}$ But the answer key says different. Please help
0
votes
1answer
504 views

Number of integral solutions to an equation subject to both upper and lower bounds

Find the number of positive integer solutions to $a+b+c+d+e+f= 20$ subject to $1\leq a,b,c,d,e,f\leq 4$. When there is only the lower bound, i.e $1\leq a,b,c,d,e,f$, we can substitute $g= a-1$, $h= b-...
1
vote
1answer
81 views

What is the probability of matching exactly 4 numbers?

In Canada's national 6-49 lottery, a ticket has 6 numbers each from 1 to 49, with no repeats. Find the probability of matching exactly 4 of the 6 winning numbers if the winning numbers are all ...
3
votes
3answers
147 views

How many ways to arrange 15 people around 3 circular tables seating 5 people each

I've seen questions where it will have you arrange $N$ people at $2$ tables with $N\over 2$ people sitting at them. The answer is usually $$\binom{N} {\frac{N}{2}} \cdot \left(\frac{N}{2} - 1\right)! ...
0
votes
0answers
38 views

Lego arrangement function limit comparison

Let L(x) be the equation that gives us the number of possible arrangements of x Legos—L(2)=24, L(3)=1560, L(6)=915,103,765, etc.. I think that this might be true: $$\lim_{x\to \infty} \frac{L\left(x+...
6
votes
2answers
139 views

Derangements with extra chairs

This was a question on my combinatorics final. Suppose $m$ people are sitting in a room with $n$ chairs. If everyone leaves and comes back, how many ways can they sit down such that no one gets ...
3
votes
3answers
123 views

How many binary words of length n , that consist an even number of zeros?

How many binary words (chars '0' and or '1') of length n that consist an even number of zeros are there? I know that there are $2^n$ options overall, and that for every $n$, there are $\lceil{\frac{n}{...
0
votes
2answers
80 views

The Basic Principle

In any n+1 integers there will be a pair which differs by a multiple of n. I have tried to create a pigeon hole with numbers a0,a1,a2,...,an but i could not get a solution.
3
votes
0answers
69 views

Combinatorical question related to the number of groups of order $n$

Suppose $n$ is a squarefree number, such that for every prime divisor $p|n$ , there exists at most one prime divisor $q|n$, such that $p|q-1$. If this is the case, then the number of groups of order $...
2
votes
3answers
65 views

Password combinations

A password consists of $13$ characters each character being one of the ten digits $0,1,2,3,4,5,6,7,8,9.$ A password must contain at least one odd digit. How many passwords are there$?$ I think the ...
10
votes
1answer
188 views

Sum of matrix vector products

Consider a sequence of fixed non-singular $n$ by $n$ matrices $A_i$ whose entries are chosen from $\{0,1\}$ and a sequence of independent random $n$ dimensional vectors $x_i$ whose entries are also ...
-2
votes
3answers
166 views

Two questions about eulerian and hamiltonian graphs.

I have 2 questions in graph theory. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 1$ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 2$ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ ...
4
votes
2answers
2k views

Conceptual proof that $p\choose k$ ($1 < k < p$) is divisible by $p$ when $p$ is prime? (I.e., no equations).

If $n,k\in \mathbf{N}$, then one defines $n\choose k$ to be the number of ways to choose $k$ elements from a set of size $n$. One can then show (by a combinatorial argument) that $${n\choose k} = \...
4
votes
2answers
350 views

Combinatorial Proof for a $ p\mid\binom{p}{k} \ \ \ \ \ 0<k<p$ .

I'm looking for a combinatorial proof to the following statement: $$ p\mid\binom{p}{k} \ \ \ , \ \ 0<k<p \ \ \ \ \ \ \text{and} \ \ p \ \text{is prime}.$$ Thank you.
2
votes
0answers
37 views

Canonical colorings over $ \omega $

Given a natural number n, let $ c:[X]^n \to \omega $ be a coloring by arbitrary many colors, where $X$ is an infinite countable set. Then there exists an infinite subset $ H $ of $ X $ for which the ...
0
votes
1answer
59 views

How many different pairs of dominoes with a unique combination of four numbers could be combined to yield $20$?

A student has an unlimited supply of dominoes, which are each labeled with two numbers. Each numbers is a member of the set $\{0,1,2,3,4,5,6\}.$ The student picks two dominoes, multiplies the numbers ...
0
votes
2answers
60 views

How many total digits are written?

In Triangleland, numbers must be written as sums of consecutive integers, starting with $1$, with at most one integer used twice. For example, $12$ must be written as $1 + 2 + 2 + 3 + 4$, which uses ...
0
votes
1answer
38 views

Path of all possible lengths $1, \ldots n - 2$ on $(n - 1)$-cycle

There is cycle with $n - 1$ vertices. $\ge \frac{n}{2}$ vertices are selected. Prove that paths of all the possible lengths from $1, 2, \ldots, n - 2$ can be drawn between selected vertices. It is ...
1
vote
1answer
52 views

Sum of kth binomial coefficient but starting at index 1.

I want to know what is the sum $\binom{n}{1} + \binom{n}{1+k} + \binom{n}{1+2k} +...$. The answer for when it starts at 0 can be derived with roots of unity and simply adding, and I suspect the same ...
0
votes
2answers
1k views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
2
votes
1answer
43 views

An additive combinatorics problem

Given $n,m\in\Bbb N$. We want to find two disjoint sets $A$ and $B$ such that $$|A|=|B|=n$$ $$\min\{a\in A,b\in B\}>m$$ $$|A+B|=2n$$ where $A+B=\{a+b:a\in A, b\in B\}$. What is the minimum ...
3
votes
5answers
134 views

The number of positive integral solutions of the equation $x_1x_2x_3x_4x_5=1050$? [duplicate]

The number of positive integral solutions of the equation $x_1x_2x_3x_4x_5=1050$ ? I prime factorized 1050.Then what to do?
1
vote
1answer
29 views

The probability that the subset will have at least one neighbor present is

In a game of tickets,the tickets are marked $1,2,3,...,50$.If 6 unordered combination of tickets is selected,then the probability that the subset will have at least one neighbor present is [if at ...