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)

4
votes
2answers
233 views

How many strings are there that use each character in the set $\{a, b, c, d, e\}$?

How many strings are there that use each character in the set $\{a, b, c, d, e\}$ exactly once and that contain the sequence $ab$ somewhere in the string? My intuition is to do the following: $a \; ...
2
votes
1answer
93 views

How many unique rotating sequences?

This is a small puzzle I've been playing with for the past couple of days: For some length N, how many unique sequences of digits can be created when any 'rotation' of the digits is considered as the ...
0
votes
2answers
38 views

Relation between binomials

how can I prove that the following relation is true: $$\binom{x-2}y+2\binom{x-2}{y-1}+\binom{x-2}{y-2}=\binom{x}y$$ Thank you for hints or references! Marted
0
votes
2answers
55 views

Count indices in summation

Consider a summation of the form \begin{equation}\sum_{i_1,\cdots, i_L=1}^K f_{i_1,\cdots, i_L}.\end{equation} How many sums of, say, $\ell$ distinct indices are present? The problem can be ...
4
votes
1answer
281 views

Number of Permutations Fixed by the Fundamental Transformation is Fibonacci

Writing a permutation in $S_n$ as a product of disjoint cycles, we define a standard representation by writing each cycle with its largest element first, and ordering the cycles by the increasing ...
4
votes
1answer
206 views

Finding the number of 5-node labeled connected graphs via generating functions

Problem: Find the number of ways to connect a graph having 5 labeled nodes so that each node is reachable from every other node. I have solved this problem using principle of inclusion and exclusion ...
5
votes
1answer
328 views

Counting Balanced Brackets with a twist

I have $n$ "1"s written as a sum: $1+1+1+\dots+1$, and proceed to add some brackets to the sum. Call the modified sum "good" if the brackets are balanced and not redundant*. [Since in fact placing any ...
0
votes
1answer
1k views

Dice question: Probability of rolling at least 2 of 3 dice with score 3 or less

my first post here. I've recently gotten back to boardgaming (Labyrinth: The War on Terror in this case) and would like to get clear on the probability of various actions. I've learnt about 'basic' ...
0
votes
0answers
260 views

Number of distinct unordered ways distribute $N$ identical objects in $R$ identical boxes?

One of the possible solution is taking $X_1,X_2,X_3,\ldots,X_r$ as boxes and no. of objects in these boxes as $0\leq X_1\leq X_2\leq X_3\leq \cdots\leq X_r$ where $[X_1+X_2+X_3+\cdots+X_r=N]$. But ...
1
vote
2answers
186 views

Combinatorics Problem On Choosing K objects from different types of objects

There are $n$ types of different articles. The names of the types are - $A_1,A_2,A_3,...,A_n$ Number of article $A_1$ is $B_1$ , $A_2$ is $B_2$... same goes upto $A_n$. We have to choose k ...
2
votes
1answer
444 views

$m\times n$ matrix with an even number of 1s in each row and column

So I want to find the number of ways to fill an $m\times n$ matrix with only 0s and 1s such that each row and column has an even number of 1s. I'm pretty stumped here. I've set up m+n equations ...
3
votes
1answer
181 views

discrete probability question

Suppose we randomly choose a byte (8 bits). What is the probability that the byte has at least two 1's? Can someone explain why is the answer 247/256 and ...
2
votes
1answer
48 views

A survey of 1,000 employees in a company

A survey of 1,000 employees in a company revealed that 201 like rock music, 392 like pop music, 121 like jazz, 140 like pop and rock music, 56 like jazz and rock, 37 like pop and jazz, and 18 ...
1
vote
2answers
195 views

A standard Missouri state license plate consists of a sequence of two letters, one digit, one letter, and one digit.

A standard Missouri state license plate consists of a sequence of two letters, one digit, one letter, and one digit. How many such license plates can be made?
14
votes
4answers
494 views

Gambling puzzle

A math friend of mine showed me this strange gambling puzzle. There is a button in a casino and every time you press it you can win either $1$ or $0$ dollars. The probability of winning $1$ dollar ...
2
votes
3answers
116 views

proof of combinatoric/using pascals theorem

prove that, for even values of $n$, $$\sum_{i=0}^{n/2}\binom{n}{2i}= 2^{n-1}\;.$$ I tried using pascals theorem to help prove this with no success
0
votes
1answer
1k views

A fair 6-sided die is rolled 10 times and the resulting sequence of 10 numbers is recorded, how many sequences are possible?

A fair 6-sided die is rolled 10 times and the resulting sequence of 10 numbers is recorded, How many sequences are possible? How many different sequences consist entirely of even numbers? How many ...
10
votes
1answer
149 views

Can this product be written so that symmetry is manifest?

Let $i,$ $j,$ $k$ be nonnegative integers such that $i+j+k$ is even. The expression $$(-1)^{j+k}\binom{i+j+k}{i,j,k}\prod_{\ell=0}^{k-1} \frac{i-j+k-2\ell-1}{i+j+k-2\ell-1}$$ apparently computes the ...
6
votes
1answer
449 views

How to compute the sum of every $k$-th binomial coefficient?

My teacher was discussing binomial expansions of $(1 + x)^n$ and he gave as an interesting example with $x = i$ whereby you could obtain the sum of all the odd coefficients ($C_n^1+ C_n^3+ C_n^5 ...$) ...
2
votes
1answer
74 views

Recursions of Sequences of Length $n$

I am trying to determine a recursion $a(n)$ that describes the number of $n$ digit ternary sequences without any blocks $012$ occurring and another recursion $b(n)$ that counts the number of sequences ...
2
votes
0answers
56 views

Number of solutions for $\displaystyle\sum\limits_{i = 1}^k a_i = n$ [duplicate]

I am aware that number of solutions for $a_1,a_2,...,a_k$ for $$a_1+a_2+...+a_k = n$$ is $\binom{n+k-1}{n}$ For $n = 3$ or $n = 2$, it is easy to make cases and follow the result. But How to derive ...
1
vote
2answers
484 views

how to count permutations that sum up to $10$

I want to count the number of permutations of $4$ numbers, each in $\{1, 2, \ldots, 10\}$, that sum up to $10$. Can someone please show how to approach this problem? I want to know what is the best ...
5
votes
3answers
2k views

Minimum number of points to beat the drop in the English Premier League?

There are 20 teams in the English Premier League (EPL) and each team plays 2 games against any other team (one at home and one as a guest). A win is rewarded with 3 points, a draw is 1 point and loss ...
2
votes
2answers
75 views

Calculating an “at least” probability without summation?

I know One can calculate the probability of getting at least $k$ successes in $n$ tries by summation: $$\sum_{i=k}^{n} {n \choose i}p^i(1-p)^{n-i}$$ However, is there a known way to calculate such ...
1
vote
1answer
76 views

Counting number of subsets drawn from a set

Suppose I have a set $S=\{1..n\}$. The number of ways of selecting half of the elements from $S$ is ${n \choose n/2}$. My question is how to count the number of ways of selecting a different set on ...
1
vote
1answer
83 views

How many equivalence relations $S$ on $A$ are there for which $R⊆S$ ($R$ is an equivalence relation on a set $A$, with $4$ equivalence classes)

Suppose $R$ is an equivalence relation on a set $A$, with four equivalence classes. How many different equivalence relations $S$ on $A$ are there for which $R⊆S$? Thanks in advance
3
votes
3answers
1k views

Probability of having exactly 1 pair from drawing 5 cards

I have an exercise as follows: There is a collection of cards consisting of 52 cards (13 types and 4 colours each type). We draw 5 cards from the collection. Then what is the probability of having ...
3
votes
0answers
150 views

Number of collinear subsets in a set

Call a set of points $(x,y)$ good if all the points in the set are collinear (i.e. they all lie on a line).Let S be the set of points $(x,y)$ such that $0\leq x,y \leq n$ ( $ x,y $ are restricted to ...
3
votes
1answer
83 views

What is the name of graph problem that ask to select some vertices to see every edges.

I want to place light bulbs on some vertices (each bulb will lit up every edges it connected) where all edges lit up. e.g. suppose I have this simple planar graph, Sufficient vertices to place ...
7
votes
1answer
144 views

Approximating a sequence with funny recurrence

Consider the sequence $a_n$ defined as $a_1=a_2=1, a_{n+1}(1+a_{n})=n+1$. This sequence describes the average number of fixed points of an involution on an $n$-set, and one can approach the problem ...
1
vote
2answers
280 views

Probability of red ball i before any black ball

Assume we have $r$ red balls and $b$ black balls in a box and we remove one ball at a time without replacement. Red balls are labeled from $1$ to $r$. We want to calculate the probability a particular ...
0
votes
0answers
178 views

Distribution of Levenshtein distances for partially sorted lists

I have a partially sorted list of distinct items and want to know the probability of this occurring by happenstance rather than intent. The Levenshtein distance is a good metric for the problem ...
4
votes
2answers
283 views

Birthday paradox: Comparing the original version with the same-birthday-as-you version

The birthday paradox itself is well known. I am only interested in a small aspect here: The number of pairings in the original problem is $${23 \choose 2} = \frac{23 \cdot 22}{2}=253$$ Another ...
3
votes
1answer
265 views

A proof of Stirling's Formula

I need to gain understanding of a proof of Stirling's formula. I have read through Tim Gowers' and Terence Tao's but I'm struggling to follow them. How rigorous is this proof, if at all? Thank you. ...
0
votes
4answers
114 views

Number of certain (0,1)-matrices, Stanley's Enumerative Combinatorics

Stanley's Enumerative Combinatorics (http://www-math.mit.edu/~rstan/ec/ec1.pdf) contains next fact: 1.1.3 Example. Let f(n) be the number of n × n matrices M of $0$’s and $1$’s such that every row and ...
1
vote
4answers
428 views

Combinations of consecutive digits

Find the number of passwords that use 3, 4, 5, 6, 7, 8, 9 exactly once. I think I solved this part: it's 7! Next question is: in how many of those 7! are the three even digits consecutive? I been ...
2
votes
2answers
126 views

Probability question, not sure if I'm doing this right… at least vs exactly.

So I'm trying to figure a few things out with probability/counting. These a probability questions, but my understanding of the counting behind them is a little fuzzy still. For example, The ...
5
votes
3answers
162 views

Problem involving combinations.

In how many ways can $42$ candies (all the same) be distributed among 6 different infants such that each infant gets an odd number of candies? I seem to think that we have 42 different objects, and 6 ...
3
votes
1answer
77 views

A question about elementary combinatorics [duplicate]

Without computing directly, how to show that $\dfrac{\binom{100}{50}}{2^{100}}<0.1$ easily?
1
vote
2answers
97 views

Probability to win between 7 and 10 games of the next 15 games

The probability that the Mets win is .8. What is the probability they win between 7 and 10 games of the next 15 games? Please help. Thank you.
2
votes
1answer
178 views

Checking Sudoku - sufficient sums

Are the following condition sufficient for checking if solution of Sudoku with (extended output) is valide : sum of values in each row, column and subsquare is equal to 45 and sum of squares of ...
5
votes
2answers
147 views

Probability of finding adjacent colored squares in a line of white squares

So this question has a small science background, but the problem itself is purely mathematical. Consider a one-dimensional row of squares, some are white, some are blue. The blue squares represent ...
2
votes
1answer
180 views

Intersection of Hamming balls of boolean vectors

I noticed that a similar question was asked with a little difference, an answer to this wasn't given certainly. Here is the problem: Given two Hamming balls of boolean vectors of size $n$ with centres ...
3
votes
2answers
204 views

Generating Function Example from class

Example: Consider the sequence $(h_n)$ where $h_n$ is the number of nonnegative integer solutions to $$a_1+a_2+a_3+a_4+a_5=n.,$$ where $a_1$ is even, $a_2$ is odd, $a_3$ is a multiple of $5$, $a_4$ is ...
1
vote
1answer
86 views

Discrete mathematics Hamming balls reference

Could you name a discrete mathematics book which discusses Hamming balls and spheres alongside boolean functions and in a deep manner? I'm particularly interested in their combinatorial ...
4
votes
1answer
109 views

creating a more complex sudoku (69x6)

I would like to know if its possible to create a "sodoku" with this rule: in a table $69\times 6$ i want to put in the numbers from $1$ to $46$ repeated $9$ times, each numbers HAS to stay in the same ...
2
votes
1answer
96 views

A combinatorial Identity considering Arithmetic Geometric Mean

I met the following combinatorial identities following the footsteps of Gauss in Borwein and Borwein's Pi and AGM (p.6); i.e. trying to prove the eq. (1.2.5) on this page. Prove that ...
3
votes
0answers
72 views

Define composition of small cyles and making a big graph

I am having following sub graphs and wish to compose all and make a one bigger graph (say G). After that, I want to select the closed path where it is passing along the outer vertices of that ...
2
votes
1answer
66 views

Determining if a Relation is a Partial Order

Consider the following relation on all pairs of real numbers $(x, y): (x, y) \preccurlyeq (x′, y′)$ if $x ≤ 0$ and $y ≤ y′$. Is it a partial order?
1
vote
0answers
96 views

Number of adjoint cells path in a bounded cubic grid

Can you help me please with the following question: There's a cubic symmetric m-dimensional grid. How many paths of N cells can be constructed inside this grid? The paths are without intersections, ...