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 (5)

0
votes
0answers
17 views

Combinatorial proof of an identity of Striling number of first kind

I can prove this identity using induction but i was looking for a combinatorial proof for this identity regarding stirling numbers of first kind. How should i proceed? Where, Thanks in advance.
5
votes
0answers
90 views

Number of restricted ways to two-color a necklace [duplicate]

There are $n$ beads placed on a circle, $n\ge 3$. They are numbered in random order as viewed clockwise. Beads for which the number of the previous bead is less than the number of a next bead are ...
0
votes
0answers
51 views

A problem related to combinatorics

If we choose $r$ objects from $n$ objects, where every combination of objects always contains a particular object, the number of ways for such a choice equals $C(n-1,r-1)$. Can someone explain why? ...
4
votes
1answer
66 views

No. of integral solutions of $x_1+x_2+x_3+x_4=20.$

I've to solve a no. of questions of this type but don't get how to do it: Determine the no. of integral solutions of $x_1+x_2+x_3+x_4=20.$ given the constraint that $$1\leq x_1\leq ...
1
vote
2answers
43 views

Number of ways to group digits in {1,2,3,4,5,6,7,8,9} into numbers, while maintaining order

I have a set of integers from 1 to 9, call it A: $$A=[1,2,3,4,5,6,7,8,9]$$ How could I find the total number of possible combination of numbers within that set, while maintaining order? For example, ...
2
votes
2answers
43 views

How many 7-digit telephone numbers have an odd number of even numbers?

((7 choose 1)*5^7) + (7 choose 3)*5^7) + (7 choose 3)*5^7) + (7 choose 1)*5^7) This is how I attempted to solve the problem, but I'm not sure if its correct.
7
votes
1answer
61 views

Sets of size at least $k$ with intersection of size at most $1$ cool problem.

At the OMM School every student goes to at least $k$ classes and two classes have at most $1$ student in common. Prove there is a set of $k$ classes where all of those classes have the same amount of ...
3
votes
2answers
62 views

$P(AB=BA)$ , $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$

Let $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$ ($p$ a prime number). Find the probability $P$ that $AB=BA$ that is $P(AB=BA)$ $$A=\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} ...
0
votes
3answers
39 views

Number of ways to park $10$ cars

Given $10$ cars (5 Fords, 3 Dodges, and 2 Hondas), how many ways can the cars be parked if there are (a) $10$ spots available? (b) $15$ spots available? My solution: (a) ${10 \choose 5} + {5 \choose ...
1
vote
2answers
12 views

Sum of Cells in Corner and in Center of Magic Square

For the magic square of order 4, the sum of 4 cells in each corner and sum of 4 cells in the center is the same which is equal to 34. But I don't have idea how to prove it. Any hint?
2
votes
1answer
35 views

On the number of cycles and independent edges in $K_{8}$

I am trying to find the number of cycles and $K_{2}$'s in $K_{8}$. That is, partition $8$ into all the ways such that the lowest part can be a $2$, so we have $8 = 8$, $6+2$, $5+3$, $2+3+3$, $4+4$, ...
0
votes
2answers
123 views

How many Binary numbers?

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$? My questions is, can I choose an $n$ randomly? For example, let's say ...
0
votes
1answer
29 views

Combo: Unambiguous expression - String

I am stuck on finding an unambiguous express so that it can produce all the strings in the given set, for the set of binary strings where for each block of zero's which are of length minimum 3 must be ...
4
votes
0answers
61 views

Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These ...
7
votes
1answer
108 views

The meaning of a definition involving multiple sums with Bernoulli numbers

Reading a paper regarding Bernoulli numbers, and I stumbled onto a definition. First let $$\frac{x}{e^x-1}=\sum_{k=0}^{\infty}B_k\frac{x^k}{k!}$$ The author then goes on to define new terms. Let ...
1
vote
3answers
33 views

Total number of possibilities

I have 3 buckets, 1st bucket has 5 red balls, 2nd bucket has 3 green balls and 3rd one has 2 blue balls. so I have total 10 balls in 3 buckets. I need to know, what are the possible combination ...
2
votes
1answer
30 views

$\sum_{i=0}^n (-1)^i \delta_i(\sum_{j=0}^{n+1} (-1)^j \delta_j) = 0$, given that $\delta_i \delta_j = \delta_{j-1}\delta_i$ whenever $i < j$

$\sum_{i=0}^n (-1)^i \delta_i(\sum_{j=0}^{n+1} (-1)^j \delta_j) = 0$, given that $\delta_i \delta_j = \delta_{j-1}\delta_i$ whenever $i < j$ This problem shows up in the middle of dealing with ...
0
votes
2answers
75 views

Biased coin flip from an unbiased coin flip

Von Neumman's method allows us to generate a fair coin flip from any unbiased coin flip using only two bits (two tosses) of information (http://en.wikipedia.org/wiki/Fair_coin). Is the reverse ...
0
votes
1answer
28 views

Predicting the outcomes of a subset of chess games correctly

Suppose $n$ games of chess are played. In how many ways can I predict the outcomes of $m$ of the games ($A$ wins, $B$ wins, there is a draw) correctly? Here's my solution. I can choose the $m$ ...
1
vote
1answer
33 views

The no. of ways dividing a polygon with $n+1$ sides into triangular regions…

Please if any one can help me explaining this concept,as I have my exam tomorrow and I can't proceed further due to this.... Let $h(n)$ denote the no. of ways dividing a convex polygon region ...
0
votes
2answers
42 views

Application of Principle of Inclusion-Excclusion [closed]

Let $$A=\{{1,2,...,300}\}$$ Find the number of subsets $\{a,b\}$ of A such that $a+b$ is the multiple of 3
2
votes
0answers
31 views

Threshold probability subset

Let $S=\{1,...,n\}$ and random subset $A \in S$ and $\forall a \in A$ we choose $a$ from $S$ with probability $p$. How find threshold probability for the property of $A$ to include 4 numbers ...
1
vote
1answer
42 views

Count the number of a kind of matrix

I want to count the number of $M\times N$ matrices with $0s$ and $1s$ which have exactly $k$ $1s$ and of which each column and each row has a least one 1. It is a little difficult for me. Could anyone ...
0
votes
2answers
41 views

How to solve $\frac{15!}{(x-1)!(16-x)!}=\frac{15!}{(2x+1)!(14-2x)!}$ for $x$?

I have to solve this problem. $$\frac{15!}{(x-1)!(16-x)!}=\frac{15!}{(2x+1)!(14-2x)!}$$ I imagine that the answer somehow lies in the recursive definition of $n!$ which is $n(n-1)!$. But I can't ...
1
vote
2answers
51 views

N circles in the plane

You are given a family of n pairwise intersecting circles in the plane. No three intersect(share a common point). Find a simple formula for counting the number of regions determined by these circles. ...
0
votes
2answers
32 views

Need help in proving combinatorial identity involving unions, intersections and complements over sets using induction

The identity is the following: $$\left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C = \bigcup_{i=1}^n (A_i^C\cap B_i^C)$$ I must use induction to prove it. Base. Ok, I think I got how to prove base case: ...
0
votes
1answer
46 views

Each Point in Cirlce

Each point in a circle is colored in one of 3 colors (blue, White, or red). Prove that one can find points that are vertices of an isosceles triangle, and either 3 points are all colored with the same ...
0
votes
1answer
32 views

how many boquets of 10 flowers can you make with 4 types of flowers

How many boquets of 10 flowers can you make with 4 types of flowers? Tough one. I heard using "stars and bars" is the approach, but still don't get it. thanks.
1
vote
2answers
69 views

combinatorial or algebraic proof of combinatorial identity

I would like to find out how to prove the following identity, assuming it is correct: $\displaystyle\sum_{r=0}^n\binom{n}{r}\binom{m+r}{l}=\sum_{r=0}^n\binom{n}{r}\binom{m}{r+l-n}2^r$ for ...
1
vote
2answers
23 views

Combinatorics. Picking items with and without replacement. Am I reasoning in a right way?

We have n keys and we want to choose right one to open the door. a. We choose keys w/o replacement. What is probability to choose right one: one the first try, second try, k-th try? b. What if we do ...
2
votes
3answers
54 views

How many ways can the average of n dice be a?

For example, if n = 2, and a = 3.5 one could have (1,6), (2,5), (3,3), (4,3), (5, 2), (6,1) = 6 if n = 10 and a =3.5, one possible combination could be (1, 6, 1, 6, 1, 6, 1, 6, 1, 6)
0
votes
2answers
32 views

Given numbers from $1$ to $N$, find the number of arrangements in which $a$ comes before $b$

We have $N$ numbers from $1$ to $N$. What is the number of arrangements in which number $a$ appears before number $b$? My solution: I keep number $a$ fixed at one location, and find the number of ...
1
vote
3answers
68 views

Draw 4 cards where: 3 cards same suit and remaining card of different suit

Four cards are drawn from a standard 52-card deck without replacement. Find the probability that exactly 3 cards are of the same suit and the remaining card is of a different suit. What I did: ...
0
votes
1answer
79 views

Pascal's Triangle

My question is the following; Q: Prove that if we move straight down in Pascal’s Triangle (visiting every other row), then the numbers we see are increasing. Found an answer but that doesn't count ...
1
vote
2answers
61 views

Solve for the number of students who took an exam.

An exam consisted of $28$ problems. Each student solved $7$ problems correctly. For every pair of problems solved, there are exactly $2$ students who solved them correctly. How many students took the ...
3
votes
1answer
47 views

Proving a Binomial Identity

Can you please help me with problem 25. I need to prove that $f(n+1)=2 f(n)$, where $f(n)$ is the LHS of the expression, from there on I can do it my self. I have tried using the binominal theorem ...
0
votes
2answers
51 views

Number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is

The number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is $\bf{My\; Try}::$ Given $x_{1}\cdot x_{2}\cdot x_{3}\cdot x_{4}\cdot x_{5} = 2 ...
1
vote
3answers
51 views

Letters of the word $\bf{“ALASKA”}$ can be arranged in a circle (Diff. b/w clockwise & Anticlockwise.)

(1): Numbers of ways in which all the letters of the word $\bf{"ALASKA"}$ can be arranged in a circle distinguishing between the clockwise and anticlockwise arrangements, is (2): Numbers of ways in ...
0
votes
2answers
20 views

Choosing a committee with a constraint - where is my reasoning wrong?

Okay, this is an example from Challenge and Trill of Pre-college Mathematics by Krishnamurthy et al. In how many ways can we form a committee of three from a group of 10 men and 8 women, so that ...
5
votes
1answer
64 views

Application of Davenport theorem

The Davenport theorem (or Cauchy-Davenport theorem for some authors ) states that for any two nonempty subsets $A$ and $B$ of the prime field $\mathbb Z/p\mathbb Z$ we have $$|A+B| ≥ \min(p, ...
3
votes
3answers
52 views

$5$ digit no. in which at least $3$ digits are identical.

The number of $5$-digit numbers that can be made with digits $\left\{1,2,3,4,5,6\right\}$ in which at least $3$ digits are identical is. $\bf{My\; Try::}$ No.,s in which at least $3$ digits are ...
22
votes
6answers
2k views

A beautiful game of gold and silver coins

A stack of silver coins is on the table. For each step we can either remove a silver coin and write the number of gold coins on a piece of paper, or we can add a gold coin and write the number of ...
0
votes
1answer
33 views

Combination with Repetitions and a bound on set

Emily really loves chocolate, but lately she has been indecisive on what kinds of chocolate to eat. She currently has a collection of various chocolate squares of 1 square inch, 2 square inches, and 3 ...
0
votes
3answers
54 views

Problem about sets of integers

Given 15 pairwisely different integers. Pat wrote all sums of 7 integers and Vova wrote all sums of 8 integers from this set. Can the set of sums of Pat be equivalent to the set of sums of Vova? I'm ...
0
votes
1answer
59 views

How many combinations can I make?

let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two ...
1
vote
1answer
60 views

Combinatorics: fewest weighting possible.

I have trouble for this weighting problem: You are given 4 balls, all equal in weight except for one that is either heavier or lighter. You are also given a two-pan balance to use. In each use of ...
1
vote
2answers
35 views

Number of ways to paint a strip of $n$ slots using $k$ colors?

Suppose I have $k$ colors, all of which must be used at least once. How many distinct ways are there to paint a strip of $n$ slots with these $k$ colors? Stars and bars and multinomial coefficients ...
0
votes
2answers
33 views

Equality in Local LYM

The Local LYM inequality says the following : for all $A \subseteq [n]^{(r)}$, $$ \frac{|\partial A|}{\binom{n}{r-1}} \geq \frac{|A|}{\binom{n}{r}},$$ where $\partial A$ is the lower shadow of $A$ and ...
1
vote
1answer
37 views

solving a simple problem of combination , with different approach

I found a question and I have different approach to solve it , but unable to get the answer. Question :How many 3-digit numbers can be formed from the digits 2, 3, 5, 6, 7 and 9, which are divisible ...