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)

2
votes
2answers
32 views

Selecting 180 days from 366: the probability of even distribution across months, or not having September among the first 30

In a draft lottery containing the 366 days of the year (including February 29). Select 180 days (draw 180 without replacement). a) What is the probability that the 180 days drawn are evenly ...
0
votes
0answers
12 views

Is this composition of $K_{4,4}$ graphs minor-closed?

Following graph is a composition of $K_{4,4}$ bipartite graphs with all the edges are of same length. How do I know whether it is minor-closed or not? The definition in the Wikipedia is as follows. ...
2
votes
1answer
35 views

Count amount of pairs $(a,b)$ from two sets $A$ and $B$ such that $a\neq b$

I have two sets $A=\{1,2,3\}$ and $B=\{2,3,4\}$ How do I count the amount of pairs $(a,b)$ where $a\in A$ and $b\in B$, such that $a\ne b$ This problem can easily be done on paper, but how can I ...
2
votes
3answers
71 views

Probability that a word contains at least 3 same consecutive letters?

Assume we have a word of length $n$ and an alphabet of length $26$ (the small letters a through z, if you want so. How likely is it that this word contains at least $k := 3$ consecutive letters of ...
2
votes
1answer
40 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
0
votes
0answers
30 views

Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j ...
0
votes
1answer
18 views

Chong inequalites about permutations

I read about two inequalities called Chong's inequalities. They state: $$\sum_{k=1}^N\dfrac{a_k}{a_{\pi(k)}}\ge N$$ and $$\displaystyle\prod_{k=1}^Na_k^{a_k}\ge\prod_{k=1}^N a_k^{a_{\pi(k)}}$$ I ...
0
votes
0answers
70 views

Cleaning minimum tables

Moderator Note: This question is part of the Ongoing August Challenge 2014 CodeChef (problem page). This contest ends on 11 August 2014, and this question will remain locked (with current answers ...
0
votes
0answers
112 views

Count arrangment such that each person wear different tshirt

Moderator Note: This question is part of the Ongoing August Challenge 2014 CodeChef (problem page). This contest ends on 11 August 2014, and this question will remain locked (with current answers ...
1
vote
1answer
33 views

Infinite series for recurrence

Question 1 If I define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \tag 1$ (where $a_n$ are $3\times 3$ constant matrices indexed with n), then can we re-write $\sum_{n \ge 1} a_{n-1} \frac{z^n}{n!} ...
2
votes
1answer
12 views

How many ways are there to group a sequence into maximal number of contiguous subsequences of given length?

Say we have a sequence $S_q$ of length $q$ and we want to group it into $m$ contiguous subsequences of length $n$. Apparently $$m=\left\lfloor\frac{|S_q|}{n}\right\rfloor.$$ My question is how many ...
1
vote
0answers
47 views

Number of ways to answer three questions, with four choices each, and not get all of them right

I have this question, I could not get answer to it. In an examination there are three multiple choice questions and each question has $4$ choices. Number of sequences in which a student can fail ...
0
votes
3answers
41 views

Find the number of increasing words of length $n$ formed by an alphabet of $m$ letters

Prove that the number of increasing words of length $n$ formed by an alphabet of $m$ letters is $$\binom{m+n-1}{n}$$ (A word is increasing if its letters(except repetitions) appear in ...
-6
votes
0answers
33 views

Both a council and a vice-president selected? [on hold]

The student Engineers Council at a certain college has one student representative from each of the five engineering majors (civil, electrical, industrial, materials, and mechanical). In how many ways ...
1
vote
0answers
32 views

Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is: "Given an infinite length random binary string, what is ...
0
votes
3answers
77 views

Birthday paradox, huge numbers

Pick x random "birthdays", say $10^9$. What are the chance of a collision, given $2^{160}$ possible "days"? I'm trying to estimate the collision rate of sha1 hashes, but the calculation is too big ...
3
votes
3answers
37 views

Probability of having 4 aces after taking turns to pick cards

I've started to learn probability and I get stuck with the following problem: My friend and I are playing a card game with 36 unique cards. There are four suits (diamonds, heart, clubs and spades), ...
6
votes
1answer
55 views

A generalization of Bell numbers to arbitrary complex arguments

For $n\in\mathbb N$, the Bell number $B_n$ is a number of ways to partition the integer range $[1,\,n]$ into pairwise disjoint non-empty subsets. E.g. $B_3=5$ because ...
2
votes
1answer
56 views

A double sum with combinatorial factors

Let $n$, $p$ and $j$ be integers. As a byproduct of some other calculations I have discovered the following identity: \begin{equation} \sum\limits_{p=0}^{j} \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} ...
0
votes
0answers
23 views

Number of unique ways to edge-label a complete graph with $k$ distinct labels.

Given $k$ distinct labels, how many unique ways to label the edges of a complete graph with $n$ nodes (nodes are not labeled). For example, to label a complete graph with 3 nodes using 4 distinct ...
1
vote
1answer
27 views

Diameter of a 2-Lift of complete bipartite graph

Give an undirected simple graph $G$ with $n$ vertices and $m$ edges, its 2-Lift is constructed as follows: Define $G_1$ to be the original graph $G$. Make a duplicate copy of $G$ and call it $G_2$. ...
0
votes
1answer
81 views

The number of functions $f: {\cal P}_n \to \{1, 2, \dots, m\}$ such that $f(A \cap B) = \min\{f(A), f(B)\}$ (Putnam 1993)

Let ${\cal P}_n$ be the set of subsets of $\{1, 2, \dots, n\}$. Let $c(n, m)$ be the number of functions $f: {\cal P}_n \to \{1, 2, \dots, m\}$ such that $f(A \cap B) = \min\{f(A), f(B)\}$. Prove that ...
0
votes
3answers
41 views

What is the minimum number of colours needed for coding 12 objects, if each may be marked with either one or two colours?

I have a word problem here which is a kind of high level to me A company that ships boxes to a total of (12) distribution centres uses colour coding to identify each centre. If either a single ...
0
votes
0answers
30 views

Number of possible ways to give change for 2 pounds

I was solving the following question on Project Euler In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, ...
0
votes
0answers
31 views

Counting the Number of Combinations Conditionally

A bank issues 10 loans ranging from 1000 to 10000 dollars each and charges 5% interest on each loan. On average, the bank finds that 1 in 10 loan recipients defaults. If the loan that defaulted is ...
4
votes
2answers
526 views

Outcome of rolling a fair die 6 times

I'm failing to understand how to come to the answer to this question. If you roll a fair die six times, what is the probability that the numbers recorded are $1$, $2$, $3$, $4$, $5$, and $6$ in any ...
0
votes
0answers
25 views

Average deviation of group sizes

This question is related to Counting of the elements in a set. The method returns $nG$ groups from $n$ points. Each group has a size $s_{j}$ for $j=1...nG$. I then compute the average deviation of ...
0
votes
2answers
21 views

Probability of a certain outcome

A bag of 14 marbles, 8 red and 6 blue and four marbles are to be chosen at random. a) What is the probability that exactly 2 red marbles and 2 blue marbles are selected? b) What is the probability ...
0
votes
1answer
21 views

Finding out co-linear points

How many triangles with positive area can be drawn on the coordinate plane such that the vertices have integer coordinates $(x,y)$ satisfying $1≤x≤3$ and $1≤y≤3$? It is easy that we have ...
-1
votes
0answers
47 views

proof of a theorem in a paper

I was reading a paper named decomposition of kronecker product of cycles and path into long cycles and paths. In one theorem I have a doubt. I am not getting how the proof of Lemma 1.3 is done. I am ...
3
votes
1answer
32 views

How to simplify a sum with binomial coefficients multiplied by $k^3/2^k$?

The sum is $$\sum_{k=5}^{\infty}\binom{k-1}{k-5}\frac{k^3}{2^{k}} $$ The first thing I thought of was the binomial coefficient. So I re-indexed it ...
1
vote
1answer
44 views

Count the number of ways n different-sided dice can add up to a given number

I am trying to find a way to count the number of ways n different-sided dice can add up to a given number. For example, 2 dice, 4- and 6-sided, can add up to 8 in 3 different ways: ...
0
votes
0answers
48 views

The probability of random permutation leaving the sequence almost unchanged

So let's say I have $52$ completely different kinds of arenas that get shuffled. What are the chances of getting the exact same sequence if only one arena can be out of order? For example, you could ...
1
vote
3answers
85 views

Simplifying $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}$

In trying to simplify my answer to a problem posted recently, I am trying to show that $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}=8\binom{24}{4}$. I know that ...
0
votes
0answers
12 views

exponential bound on the number of possible clusters at $0$ in $\mathbb{Z}^d$

Let us say that $\mathbb{Z}^d$ is given the usual lattice structure as a graph. I want to know the number of connected induced subgraphs of size $k>0$ that include the vertex $0$. Call this ...
3
votes
0answers
47 views

How to show this expression is always a perfect square?

The number of tilings of an $m \times n$ board with $2 \times 1$ dominoes (each placed either horizontally or vertically on two squares of the board) has been shown to be $$\sqrt{\prod_{j=1}^m ...
2
votes
1answer
41 views

Simplifying a generating function in two variables with two binomial coefficients

I'm trying to to make the below expression simpler, and it would be great if it could be expressed as something like $(x+y)^k$. $$ \sum_{i=0}^k\binom{n+1}i\binom{m+1}{k-i}x^iy^{k-i} $$ The number ...
1
vote
0answers
35 views

Counting apartments in spherical buildings

Is there a formula for the number of apartments in a finite, spherical building? To be specific, is there a formula that depends on the associated Coxeter group and the thickness of the building? ...
0
votes
0answers
18 views

How many Homomorphisms are there from one bounded lattice to another?

for a project that I work on, I need to know how many homomorphisms there are from one finite lattice with 0 and 1 to another. I remember that I already worked it out if one of them is the trivial ...
1
vote
2answers
41 views

Upper bound on $ \binom{a}{m+1}\sum ^m_{j=0} \binom{a-m-1}{j}/\binom{b}{j+m+1}$

Given $a,b,m$ such that $0<2m<a<b$. I would like to find out upper bound of $$S = \binom{a}{m+1}\sum ^m_{j=0} \frac{\binom{a-m-1}{j}}{\binom{b}{j+m+1}}$$ Anyone can help me please? Thank you ...
3
votes
1answer
29 views

Number of possible rectangles from at most N identical squares

I was looking to find the number of distinct rectangles possible from at most $N$ identical squares. (Two rectangles are distinct if one cannot be rotated to obtain another) e.g for $N = 6$ , $8$ ...
0
votes
1answer
22 views

Probability $\sum_{j=n+1}^{2n+1} {M \choose m+1}{M-m-1 \choose j-m-1}/{N \choose j} $

I have a prob. problem: A school has $N$ students in which $M$ students are leader (of each class in school), and $N>M$. There are $2n+1$ balls in the black box including $n+1$ blue balls and $n$ ...
0
votes
2answers
43 views

Combinatorial argument $a(n-a)$ $n \choose a $ = $n(n-1)$ $n-2 \choose a-1$

I can not make sense of this; I am looking for a combinatorial argument that would prove the equivalence of this statement. I can prove it with algebraic manipulation. $a(n-a)$ $n \choose a $ = ...
6
votes
7answers
156 views

How many $10$ digit number exists that sum of their digits is equal to $15$?

How many $10$ digit number exists that sum of their digits is equal to $15$? Additional info: First digit from left is not $0$.we could use any digits from $0$ to $9$. I saw in some ...
-2
votes
1answer
105 views

A Twin Primes Sequence [on hold]

How to prove the relation below and is it enough significant to prove the infinitude of the twin primes? For every twin primes $x,y$ there exists $\alpha,\beta$ positive integers such that ...
-1
votes
0answers
79 views

Find the highest story from which an egg can be dropped without breaking it (lowest average, not worst-case scenario) [on hold]

EDIT: Not looking for worst-case scenario solution, but rather the lowest average. This question has been answered many times for worst-case scenario being 14, I know this already :) PROBLEM: You ...
2
votes
2answers
57 views

Number of ways to put one or more of $5$ books in $5$ bags

In how many ways can we put one or more of 5 books in to 5 bags? Additional info: books are labeled. Bags too. One or more bags can remain empty. Things I have done so far: There are $5$ ...
2
votes
3answers
60 views

Combo Identity: How to prove this using Induction [on hold]

$$ \sum_{n = 0}^{\infty} \binom{n + k}{k}x^n = \dfrac{1}{(1 - x)^{k + 1}} $$ Could someone suggest how I should get started to prove this using induction?
1
vote
3answers
31 views

Choosing $2$ groups of $5$ members and $1$ group of $2$ members from $15$ person

In how many ways can we choose $2$ groups of $5$ members and $1$ group of $2$ members from $15$ person? Additional info: groups are not labeled. Things I have done so far: I know number of ...
1
vote
1answer
24 views

Combinatorics Question about balls in boxes

There are 5 balls numbered 1 to 5, and there are 3 boxes numbered 1 to 3. The question asks in how many distinct ways can the balls be put into the boxes if 2 boxes have 2 balls each and the other box ...