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)

2
votes
1answer
64 views

unbalancing lights

I'm reading the following notes on unbalancing lights, http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf. The question i have is regarding the first page. Where it says Consider a square $n ...
1
vote
1answer
19 views

Number of ways of selecting all k-indexed identical items before all k+1 indexed identical items for all k from 1 to n

Suppose we have n indices and we have a specific number of items allotted to this index. Say for 2 balls of colors Blue(B)[1], 4 of color Green(G)[2] and 2 of color Red[3] (I could've just assigned ...
1
vote
1answer
51 views

Count the paths in a graph

For a given graph $G(V,E)$ $V = \{ (x,y) | x = \{0,1, ... , m\}, y = \{0,1, ... , n\} \}$ $E = \{ \{(x,y), (u,v)\} | (x=u \text{ and } |y-v|) = 1 \text{ or } (|x-u| = 1 \text{ and } y=v) \}$ How to ...
7
votes
1answer
99 views

How many ways to add to 32?

I have been presented with a rather complex combination problem. Using only the numbers 2, 4, 6 and 8, how many possible ways can you add up to 32 if the number 4 may only be used no more than once ...
3
votes
2answers
55 views

In how many ways can you group $3$ different numbers from $1$ to $12$ wherein their sum is divisible by $3$?

In how many ways can you group $3$ different numbers from $1$ to $12$ wherein their sum is divisible by $3$? This question is one of the questions asked in a Math contest for intermediate level, ...
1
vote
2answers
29 views

Marbles Combinations problem

Martin’s bag of marbles contains two red, three blue and five green marbles. If he reaches in to pick some without looking, how many different selections might he make? I do not know how to ...
0
votes
1answer
30 views

Distributing $n$ distinguishable objects into $n$ distinguishable boxes [closed]

I'm taking an introductory statistics course and one of the previous exam questions goes like this: $n$ numbered balls are placed into $n$ distinguishable cells. Find the probability that exactly ...
1
vote
1answer
79 views

Simplify a Combinatorial Sum $\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$

Is there a way to simplify $$\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$$ where $a,b,c,d,e$ are natural numbers? In particular, I would like to see the case for $a=45, ...
1
vote
1answer
38 views

Linear extension of a set

I have to find a linear extension of the poset $(X,P)$ where the set $X = \{2,3,10,21,24,50,210\}$ iff $x$ divides $y$. For the answer, I got ...
2
votes
5answers
99 views

The number of ways to write $10$ as the sum of five natural numbers not equal to $3$

How many answers are there for the equation $$x_1+x_2+x_3+x_4+x_5=10$$ given that $0\leq x_1, x_2,x_3,x_4,x_5$ and none of them equal to $3$? The numbers $x_1, x_2,x_3,x_4,x_5$ are in $\mathbb{N} $. ...
1
vote
2answers
118 views

A Vandermonde's-like identity, new or existing?

From my effort of finding Vandermonde's-like identity, I found out that if $n \le m-2$, then $$\sum_{r=1}^{n+1} \frac{\binom{2r}{r}\binom{m+n-2r}{n+1-r}}{r+1}=\binom{m+n}{n}.$$ I am not sure if ...
0
votes
1answer
54 views

Probability of (A <= B OR A <= C) AND B > C when A, B and C are random integers with different ranges but starting at 0.

I have 3 random integers A, B and C, along with 3 defined integers X, Y and Z: A in [0, X] B in [0, Y] C in [0, Z] All the values that A can take within its defined range are equiprobable. Same goes ...
0
votes
2answers
34 views

How many non-negative integer solutions does $x_1+x_2+\cdots+x_n=A$ have?

If I have the Diophantine equation $\displaystyle{\sum_{i=1}^n x_i =A}$, is there a function $f(n,A)$ that will yield the number of non-negative integer solutions of the equation?
2
votes
1answer
39 views

triangulation of the cube of whose vertices are in the set $\lbrace (\pm 1 , \pm 1 , \dots , \pm 1)\rbrace$

Take the cube centered at the origin whose vertices are $\lbrace (1 ,1 , 1) , (-1 ,1 , 1) , (1 ,-1 , 1) , (1 ,1 , -1) , (1 ,-1 , -1) , (-1 ,1 , -1) , (-1 ,-1 , 1) , (-1 ,-1 , -1) \rbrace$. We can ...
0
votes
1answer
21 views

How can I count the number of $n$ digit positive integers without a specific digit?

Came across the Kempner Series and was doing a little reading. The proof that the Kempner Series is bounded by 80 requires the fact that the number of $n$ digit positive integers without the digit 9 ...
0
votes
2answers
49 views

find the number of ways of selecting 9 balls from 6 red balls 5 white balls and 5 blue balls if each selection contains 3 balls of each colour.

The question in my book has been solved this way $\binom{6}{3}\binom{5}{3}\binom{5}{3}$ but I think that there should only be one way of this combination because no matter how we select 3 balls from ...
-4
votes
1answer
47 views

How many ways are there to divide $5$ books amongst $3$ people? [closed]

How many ways are there to divide $5$ books amongst $3$ people, with each person getting zero or more books , given All books are different. All books are identical.
1
vote
1answer
50 views

Estimation of a probability of marginal values of a random variable

My question is related with this question on combinatorics of 0-1-matrices from MO. Trying to obtain a (asymptotic) lower bound for $\alpha(n)$ by probabilistic approach (see, for instance, “The ...
0
votes
1answer
39 views

Probability of A > B AND A > C when A, B and C are random integers with different ranges but starting at 0.

I have 3 random integers A, B and C, along with 3 defined integers X, Y and Z: A in [0, X] B in [0, Y] C in [0, Z] All the values that A can take within its defined range are equiprobable. Same goes ...
0
votes
3answers
22 views

Calculating the amount of numbers in a range that yields a certain condition

For example: How many numbers in $[40000,70000]$ are there such that the sum of all digits is $12$ and the right most digit is $1$? I cant figure out how to calculate the numbers that the sum of thier ...
-1
votes
0answers
20 views

Number of ways to distribute a list of numbers into 2 groups in such a way that sum of numbers in each group is greater or equal T

Given a list of N positive integers K1, K2, .... KN. Then what is the number of ways to distribute them into 2 groups in such a way that sum of numbers in each group is greater or equal to T. ...
-5
votes
1answer
37 views

I need a logic to generate unique number with combination of other numbers [closed]

I have series of numbers 1,2,3,4 upto 10000. I need a logic to generate unique number which is not there in the same series. And it's should not be duplicated with other combinations. Failure Logic, ...
2
votes
4answers
82 views

show there exists an integer k such that $2013^k$ ends with '0001'

Prove that there exists an integer k so that $2013^k$ ends with '0001'. we couldn't figure this out. i thought we might try to prove that we can find an integer m such that $m*10^4 +1 = 2013^k$, but ...
-1
votes
2answers
43 views

Should I be using combinations or permutations?

I have a set of $26,000$ values. Each value has the option of being $1$ or $0$. How do I calculate the number of potential combinations of $1$'s and $0$'s that exist for $26,000$ values?
-1
votes
0answers
30 views

number of solutions of equation $xy \leq n$ where $x>0$ and $y>0$ and $n>0$ [closed]

How do I approach this problem programatically?? Given a positive integer $n$, how many positive integers $(x,y)$ are there such that $x\cdot y\le n$ ?
10
votes
3answers
528 views

proof that $1 = \sum\limits_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$

I'm looking for a proof of this identity: $$ 1 = \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k} $$ I'll take anything, but a combinatorial proof would be nice - all of the terms in the sum ...
11
votes
1answer
71 views

How many unique numbers can be obtained from multiplying two natural numbers less than $N$?

The question seems simple, but I cannot wrap my head around how to properly count it, or even give a good estimate. I can't find the answer either. We have two integer numbers $1 < a,b < N$, ...
1
vote
1answer
33 views

Arranging $8\times 8$ square so that every $2\times 2$ square satisfy $|ab-cd|=1$.

Is it possible to arrange an $8\times 8$ square with numbers $1,2,\ldots,64$ once each so that for every $2\times 2$ square, if the numbers on one diagonal is $a,b$ and the other diagonal $c,d$, then ...
1
vote
0answers
36 views

Deriving deletion-contraction formula from Subgraph Expansion of Chromatic Polynomial

Given a graph $G=(V,E)$, the chromatic polynomial $P(G,q)$ counts the number of $q$-colorings of a graph $G$. It satisfies the deletion-contraction formula: \begin{equation*} P(G,q) = P(G-e, q) - ...
0
votes
0answers
31 views

How many possible Connect 4 end boards are there?

If you search google you can find that there are over 4.5 trillion board combinations, but if i understand correctly there are two differences between this and what I am asking. First this figure ...
3
votes
3answers
39 views

Trouble Understanding this Combinatorics Problem

Problem: There are 2 girls and 7 boys in a chess club. A team of four persons must be chosen for a tournament, and there must be at least 1 girl on the team. In how many ways can this be done? ...
1
vote
1answer
22 views

combinations of graphs with 2 vertices

I am reading graph theroy. Here author mentions that the number of possible digraphs is truly huge. Each of the $V^2$ possible directed edges (including self-loops) could be present or not, so the ...
1
vote
2answers
54 views

Tough Polynomial Root Problem

Let $S$ be the set of all polynomials of the form $z^3 + az^2 + bz + c$, where $a$, $b$, and $c$ are integers. Find the number of polynomials in $S$ such that each of its roots $z$ satisfies either ...
2
votes
2answers
20 views

In a circle there are $m$ chords and no $3$ are concurrent, $n$ intersections in the interior. Show there are $m+n+1$ regions dividied by the chords.

In a circle there are $m$ chords such that no $3$ are concurrent and there are $n$ intersections of these chords in the interior of the circle. Prove that the number of regions divided by the ...
20
votes
5answers
4k views

Puzzle of gold coins in the bag

At the end of Probability class, our professor gave us the following puzzle: There are 100 bags each with 100 coins, but only one of these bags has gold coins in it. The gold coin has weight of ...
1
vote
0answers
20 views

Invertible matrices, permutations and leading principal minors

Given an invertible $\{-1,0,1\}$-matrix $A$ (its determinant is $\pm 1$), are there two permutation matrices $P$ and $Q$ such that all the leading principal minors (determinants of the top-left ...
3
votes
1answer
39 views

cycle space in graph theory

I read the following definition of the cycle space in a set of notes. Definition (Cycle space): Let $G=(V,E)$ . The cycle space of $G$ is an element of $2^{E}$ denoted $\mathcal{C}$ and is the ...
1
vote
1answer
27 views

proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct. proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ ...
18
votes
4answers
8k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
0
votes
1answer
354 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
31
votes
1answer
2k views

Minesweeper - Chance of one-click win

I'd like to know if it's possible to calculate the odds of winning a game of Minesweeper (on easy difficulty) in a single click. This page documents a bug that occurs if you do so, and they calculate ...
0
votes
0answers
27 views

Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$ [duplicate]

How do we show that this identity holds for any n? Any hints or solutions? Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$
1
vote
1answer
41 views

How to show that a set of random strings has unit probability

I am encountering a problem where I want to show that the generation of a random string terminates in finite time with probability one, where the termination is condition is reaching an element of a ...
4
votes
0answers
63 views

About two combinatorial counting problems.

Here are the problems: Suppose $X$ is a set of $n$ elements, and $S_1,...,S_m$ are $m$ subsets of $X$ of average size at least $n/w$. Show that if $m\geq 2kw^k$, then there are $k$ distinct ...
3
votes
0answers
65 views

Coupon collector variation (with deleterious coupons and tolerance)

Imagine the standard coupon collector's problem, with $n$ coupons to be collected. However, the sample space also contains $T$ bad coupons. Specifically, if during the collection, I collect more than ...
0
votes
3answers
31 views

Showing that a series solves a recurrence relation

Let: $a_n = a_{n-1}+2a_{n-2} +3\cdot 2^n$, $\displaystyle b_n=4\sum_{k=0}^nk\binom n k$ Show that $b_n$ solves $a_n$ There are no starting conditions for the recurrence, that is how the ...
1
vote
1answer
50 views

Given 3 Red, 3 White, and 3 Blue balls and 3 purple and 1 black urns, how many possible arrangements are there? [closed]

I know for 1 ball of each color, with the same types of urns we can have 16 possible arrangements, but when increasing to 3 balls of each color, how should you approach this?
21
votes
0answers
509 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
3
votes
4answers
77 views

Number of ways selecting 4 letter words

The number of ways of selecting 4 letters out of the letters MANIMAL A. 16 B. 17 C. 18 D. 19 I have made three different cases. Including 1 M, 2 M and none of the M. So it is 6C3/2 + ...
2
votes
0answers
27 views

Performing operations on sides and diagonals of convex polygon

Given a convex $n$-gon with $n\geq 4$. We write a positive number on $2n-3$ segments: all sides, and all diagonals from one vertex. If there is a quadrilateral $ABCD$ such that all sides and the ...