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)

1
vote
1answer
26 views

permutations with a given condition!

What will be the number of permutations of n different things, taken r at a time,when p particular things is to be always included in each arrangement? I know the answer to this question but could not ...
0
votes
0answers
31 views

In how many ways can you make change for a dollar? [duplicate]

I know there are questions related to this on the site but they are not in the context I am looking for (basic statistics). This problem is at the end of the section introducing combinations and ...
0
votes
1answer
33 views

How to deduce number of unordered distinct pairs using set operations and bijections

In (b) of the example, we are ask to calculate the number of ordered pairs of distinct positive integers. I like the first method's answer (using bijections, set operations) because it clearly shows ...
1
vote
1answer
34 views

Longest path in a grid

I recently saw a computer programming question that asked for the longest path that one can build in a $3\times3$ unit grid connecting the vertexes, with the following rules(the same rules of a ...
1
vote
1answer
60 views

total number of combinations?

Patient Age ---> Avg Visits / Year <1 year ---> 7.5 1-4 years ---> 3.0 5-14 years ---> 1.8 15-24 years ---> 1.7 25-44 years ...
3
votes
1answer
48 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
3
votes
2answers
45 views

How is this exactly equal to $N_1+N_2+\dots+N_r$?

There are $N$ boxes, each containing at most $r$ balls. If the number of boxes containing at least $i$ balls is $N_i$ for $i=1,2,\dots,r,$ then the total number of balls contained in these $N$ ...
3
votes
3answers
49 views

Counting the factors of $2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$

Let $n = 2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$. How many natural-number factors does $n$ have? I'm not quite sure how to go about solving this problem; there seems to be a lot of overcounting involved.
3
votes
1answer
173 views

How many natural numbers less than $10^8$ are there, whose sum of digits equals $7$?

How many natural numbers less than $10^8$ are there, whose sum of digits equals $7$? I got it here.But is there any more effecient and easier way to solve than the link shows?
0
votes
3answers
80 views

How to show that $A_k=(-1)^k\binom nk$?

In the identity $$\frac{n!}{x(x+1)(x+2)\cdots(x+n)}=\sum_{k=0}^n\frac{A_k}{x+k},$$prove that $$A_k=(-1)^k\binom nk.$$ My try: The given identity implies $$\frac{1\cdot2\cdots ...
2
votes
2answers
45 views

Estimate the number of ants in a colony

A friend of mine gave me this weird problem I cannot solve. To estimate the number of ants in a colony an entomologist draws 5500 ants randomly from the colony, labels them with a radioactive isotope ...
0
votes
1answer
31 views

The number of ways of going up 7 steps …

The number of ways of going up 7 steps if we take one or two steps at a time is ? So its essentially asking in how many ways can we make use of numbers of (1,2) to get a sum of 7. Am I wrong up till ...
-1
votes
3answers
64 views

In how many ways can you choose three distinct numbers … [closed]

In how many ways can you choose three distinct numbers from the set of {1,2,3,...,19,20} such that their product is divisible by 4 ?
2
votes
3answers
45 views

Combinatorics question: Boys and Girls around table

In how many ways can 4 boys and 4 girls sit around a circle table if each boy sits between two girls? (Rotations of the same arrangement are still considered the same. Each boy and girl is unique, ...
1
vote
1answer
41 views

How to calculate the number of lattice points in the interior and on the boundary of these figures with vertices as lattice points?

We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers. Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and ...
-2
votes
3answers
50 views

How many digits… [closed]

How many $3$ digit numbers of distinct digits can be formed by using the digits $1,2,3,4,5,9$ such that the sum of the digits is at least $12$ ?
0
votes
2answers
41 views

Find how many of these $4$-digit numbers are even. [closed]

(a) (i) Find how many different $4$-digit numbers can be formed from the digits $1, 3, 5, 6, 8$ and $9$ if each digit may be used only once. I did this; the answer is $360$; I used ...
1
vote
1answer
36 views

Maps preserving roots of a polynomial function over finite fields

Let $P(x_{1},\ldots,x_{n}):\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}$ be a polynomial function with degree $d$ and with variables $x_{1},\ldots,x_{n} \in \mathbb{F}_{2}$. Let $S(P)=\{ ...
1
vote
1answer
14 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
1
vote
1answer
21 views

Number of arrangement

Problem: What is the formula of number of arrangements? More specifically I need to avoid repeated elements and the order of the sequence does not matter. For lucidity I show an example: For 3 ...
-2
votes
1answer
21 views

How many binary strings are there of length n with k ones? [closed]

For some fixed $n$, how many binary strings are there with $k$ $1$s and $n-k$ $0$s (where $n>k$)?
0
votes
1answer
49 views

Sort of Binomial Expansion

I was trying to find a general formula for expanding the product: $$\prod_{i=1}^k (a+ib)$$ where $a, b \in \mathbb{R}$. The first few expansions are as follows: $$\prod_{i=1}^1 (a+ib) = a + b$$ ...
-2
votes
1answer
37 views

Expected Value Question Intermediate [closed]

Mila has four ropes. She chooses two of the eight loose ends at random (possibly from the same rope) and ties them together, leaving six loose ends. She again chooses two of these six ends at random ...
7
votes
2answers
186 views

Rearrangement of dinner guests

A dinner host wants his guests to move, between main course and dessert, so that everyone gets a complete set of new neighbours. Guests are seated either side of a long table. Most guests have five ...
0
votes
1answer
55 views

Find the number of sets $X$ which can be formed by the number $n$

Find the number of sets $X$ which can be formed by the number $n$ where $X=\{a,b,c\}$ and $a+b+c=n$. $a,b,c$ are natural numbers and so obviously $n$ is also a natural number. $n>2$
1
vote
1answer
81 views

Looking for a bijection between this set and natural numbers

I am a computer programmer, and I am struggling with this mathematical problem without finding a consistent and efficient solution. Let $A_{k, M}$ be the set of all the possible assignments for $n_1, ...
-1
votes
0answers
44 views

Count suggestions to be send

A site currently has N registered users. As in any social network two users can be friends. We wants the world to be as connected as possible, so we want to suggest friendship to some pairs of users. ...
2
votes
2answers
112 views

seventeen tiles on a torus

The torus $\mathbb{R}^2 \mod((4,1),(1,-4))$ has area 17. Can it be covered by seventeen labelled tiles in two different ways so that any pair of tiles is neighbours of each other (at an edge or a ...
1
vote
1answer
133 views

What is the count of the strict partitions of n in k parts not exceeding m?

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...
4
votes
1answer
263 views

The fewest questions should be prepared for a exam

$N$ students will do a test paper with $M$ question and for a consideration of cheat, every paper will be different, but not totally. There are at most $K$ questions same in any two papers. Given the ...
-2
votes
1answer
36 views

Counting overlapping figures

How many four-sided figures appear in the diagram below? I tired counting all the rectangles I could see, but that didn't work. How do I approach this?
2
votes
3answers
161 views

General Leibniz rule for triple products

I have a question regarding the General Leibniz rule which is the rule for the $n^{th}$ derivative of a product and reads: $$ (f g)^{(n)}=\sum_{k=0}^{n} {n \choose k} \,f^{(k)} g^{(n-k)}. $$ ...
1
vote
5answers
129 views

$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}=?$

I was asked to find a closed formula for the sum $$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}$$ could anyone give me an advice on how to get started?
7
votes
4answers
379 views

Show that $\sum_{k=0}^n\binom{3n}{3k}=\frac{8^n+2(-1)^n}{3}$

The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one ...
1
vote
0answers
57 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
1
vote
3answers
173 views

Hint proving this $\sum_{k=0}^{n}\binom{2n}{k}k=n2^{2n-1}$

I need hint proving this $$\sum_{k=0}^{n}\binom{2n}{k}k=n2^{2n-1}$$
1
vote
1answer
57 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
2
votes
2answers
139 views

maximum size of a $k$-intersecting family of $[n]$

What is the maximum size of a family of subsets of $[n]:=\{1,2,3,\dots,n\}$ say $\mathcal{A}$ such that $\mid A\cap B\mid \ge k$ where $A,B\in \mathcal{A}$ and $1\le k\le n-1$? This not ...
3
votes
1answer
167 views

What is this myth/legend and origin of related ideas?

There is a story I recently heard but the story teller (who read about it someone on the Internet) have forgotten the majority of the story, so there is little I can work on: my search attempts went ...
0
votes
0answers
50 views

Sums with k dice

I have n dice, each with k sides, numbered from 1 to k inclusive. I want to find in how many ways I can get a sum of x using those dice. Doing some research, I found that what I am looking for is ...
6
votes
1answer
187 views

find the sum $\sum_{k=0}^{n} k\binom{n}{k}^2p^k$

I need to find the sum $$\sum_{k=0}^{n} \binom{n}{k}^2kp^k,$$ for an integer $n$ and $0<p<1$. Mathematica would only return $$\sum_{k=0}^{n} k p^k \binom{n}{k}^2 = n^2 p \ _2F_1(1-n, 1-n, 2, ...
3
votes
1answer
228 views

Finding intersecting subsets for given binomial coefficient

My apologies if this question is more appropriate for mathisfun.com, but I can only get so far reading about combinatrics and set theory before the interlocking logic becomes totally blurred. If this ...
1
vote
1answer
238 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$: ...
1
vote
1answer
28 views

How many closed binary operations on A have x as the identity?

There is this one example in my book that explains how to do this, but it's very obsecure and I just can't follow it. It says if: A = {x,a,b,c,d} then there are 5^16 closed binary operations on A ...
0
votes
1answer
60 views

How many ways can we form an integer-sided scalene triangles with largest side <= N?

Since triangle is scalene, we can pick 3 numbers [a, b, c] from 1 to N, such that a + b > c, a + c > b and b + c > a. The result is A173196 but I can't get a way to obtain the result except by ...
2
votes
3answers
103 views

How many different choice of sets?

If $S_1$, $S_2$, $\dots$, $S_r$ are r sets, $S_i\subseteq \{1,2,\dots,n\}$. $|S_i|\geq 1$ for all $i$ and $S_i\cap S_{i+1}$=$\emptyset$ for all $1\leq i\leq r-1$. How many different chioce of ...
0
votes
3answers
2k views

Minimum moves to reach destination [closed]

Given that a person is standing at $(0,0)$ and initially look in direction of $X$-axis. Now he can walk only at right angle to previous move. Like if he has to go to $(3,3)$ then $6$ moves are ...
6
votes
4answers
68 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...
0
votes
1answer
229 views

Probability matching problem

Arriving at party n guests throw their hats into pile. When they leave they each take a hat that is chosen randomly from the pile. We want to compute the probability of the event $A$ that at least one ...
2
votes
1answer
47 views

Count no. of ways with exactly K turns

Given two distinct points A(P,Q) and B(R,S) with P,Q,R,S>=0. What is the number of ways to count paths with exactly K turns given that we can move in only two directions i.e. right and down? My ...