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)

8
votes
1answer
389 views

Sum of Squares of Harmonic Numbers

Let $H_n$ be the $n^{th}$ harmonic number, $$ H_n = \sum_{i=1}^{n} \frac{1}{i} $$ Question: Calculate the following $$\sum_{j=1}^{n} H_j^2.$$ I have attempted a generating function approach but ...
0
votes
3answers
50 views

Inclusion exclusion to solve $x_1+x_2+x_3=15$ with conditions

How to do this using inclusion/exclusion? Number of integers solutions to the equation $x_1+x_2+x_3=15$ with $x_1,x_2\leq 5$ and $x_3\leq 7$ for non negative integers $x_1,x_2,x_3$ I can do this ...
1
vote
3answers
33 views

How to find the total number of drinks possible

If I sold coffee in 4 sizes (small, medium, large, and extra large) and 4 varieties (Kenyan, Sumatran, Kona, and Columbian). Customers can choose to add one or more syrups that come in 5 flavors ...
0
votes
0answers
285 views

Cleaning minimum tables

John has been newly hired to clean tables at his restaurant. So whenever a customer wants a table, he must clean it. But John happens to be a lazy boy. So in the morning, when the restaurant is ...
7
votes
1answer
484 views

Count expressions with 1s and 2s

Given at most X number of 1s and at most Y number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * ...
1
vote
0answers
19 views

Number of distinguishable arrangements of the word INDOOROOPILLY with three different conditions

I have the following three questions on a past final exam, I wanted to ask if I have done everything correctly. Thank you! How many distinguishable arrangements are there for the letters of the ...
8
votes
5answers
424 views

Calculating the median in the St. Petersburg paradox

I am studying a recreational probability problem (which from the comments here I discovered it has a name and long history). One way to address the paradox created by the problem is to study the ...
0
votes
1answer
41 views

Counting in two ways

I've been having trouble proving the following equivalence. I suspect a two-way counting method is sufficient. Could anyone shed some light? $$\sum_{i=0}^{m}{ \binom{n-i}{m-i} \binom{k+i}{i}} ...
1
vote
1answer
20 views

Simpler formula for number of ways to pair up (or not ) $2n$ objects?

We can see that the number of ways to pair up $2n$ people is $(2n-1)!!$. But I want to calculate the number of ways to pair up those people where not necessarily all the people are paired. By summing ...
0
votes
0answers
36 views

Generating function to calculate number of ways of distributing $10$ or less items to $3$ people.

There is a container of 10 identical chocolate frogs and three students, Adam, Bob, and Charles, are to be given some of these chocolate frogs, but not necessarily all of the chocolate frogs. ...
-1
votes
0answers
111 views

Express a given integer in terms of given, smaller, integers.

[Please see part beginning with EDIT] I have a number(any number for example 10). We can have another small number(it can be any number for ex 3,2 (any digit). So I need add this number which ...
4
votes
0answers
51 views

Geometric Generating Functions

Let $p(t) = t^3 + Ft^2 + Et + V$, where $F,E,V$ are the number of faces, edges, and vertices of a cube, respectively. Factor $p(t)$ and explain your results in terms of generating functions. A hint ...
1
vote
1answer
42 views

Finding maximum no of $1$'s

We are given a matrix $A \in M_n (F)$ such that all its entires are either $1$ or $0$. I need to find the maximum number of $1$'s that can be in matrix $A$ so that it is still invertible. My try : ...
0
votes
2answers
44 views

Probability of each outcome from dice notation

In the "dice notation", XdY means you rolls X number of Y-sided dices, and adds the results together to get the final outcome. For example, on 3d3 distribution, you can get number from 3 to 9, and ...
0
votes
1answer
19 views

Paths in rectangular grid. Need some help with the logic behind it.

Suppose I have a an ixj grid (i rows, j columns) From the bottom left, to the top right, you may only move UP or RIGHT, how many paths are there from A to Z. In this case, you must go up twice, ...
0
votes
1answer
35 views

How many elements does $\mathcal{P}(A)$ have?

Let $A$ be a set of size fifteen. Let $\mathcal{P}(A)$ denote the power set of $A$, that is the set of all the subsets of $A$. How many elements does $\mathcal{P}(A)$ contain? This is the same as ...
0
votes
1answer
27 views

Sum of products of binomial coefficients is equal to another binomial coefficient [duplicate]

Need help in proving (by induction or by combinatorics) the following statement Is it possible to do it by induction? there are 3 veriables and I think I cannot easily do it by induction. Correct? ...
0
votes
1answer
39 views

Intuition behind $t(t+1)(t+2)\cdots(t+n-1)$

We have the following formula: Let $t$ be indeterminate and fix $n\geq 0$. Then \begin{equation} \sum_{k=0}^n c(n,k)t^k = t(t+1)(t+2)\cdots(t+n-1) \end{equation} where $c(n,k) = \#$ of permutations ...
3
votes
1answer
63 views

Combinatorial Analysis: Fermat's Combinatorial Identity

I was looking through practice questions and need some guidance/assistance in Fermat's combinatorial identity. I read through this on the stack exchange, but the question was modified in the latest ...
-3
votes
1answer
38 views

Alphabets Problem [closed]

in the English alphabets of capital letters there are 15 stick letters which contain no curved lines, and 11 round letters which contain at least some curved segment. How many different 3 letters ...
1
vote
3answers
55 views

Number of derangements $f(1)=2 , f(2)=3$

What is the number of derangements of the set $\{1,2,…,n\}$ such that $f(1)=2, f(2)=3$.
1
vote
1answer
30 views

Intuition behind combinatorics problems?

I have a hard time understanding when a problem is a combination or permutation. Especially when using the multinomial theorem. For example: three boxes numbered 1,2 and 3 for k = 1 2 and 3, box k ...
6
votes
1answer
63 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
2
votes
0answers
40 views

Cubic 3-edge connected graph has edge cover that can omit 2/3 of all edges over 5 graphs (so 2/15 per graph) and be 2-edge connected

Let's assume that I have a cubic 3-edge connected simple graph $G$. After taking a perfect matching (and we can specify which one we want), I want to split the remaining edges in 5 sets $U_1, ..., ...
0
votes
0answers
10 views

Proof: Generalized Version Of The Basic Counting Principle

The Generalized Basic Principle Of Counting If $r$ experiments that are to be performed are such that the first one may result in any of $n_1$ possible outcomes; and if, for each of these ...
3
votes
1answer
288 views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
1
vote
1answer
40 views

How can I calculate $ \sum_{j=0}^{49}\binom{100}{2j+1}p^{100-(2j+1)} q^{(2j+1)} $?

I got the following formula when I tried an exercise in probability: $$ \sum_{j=0}^{49}\binom{100}{2j+1}p^{100-(2j+1)} q^{(2j+1)} $$ where $p+q=1$. These are the "odd" terms in the expansion of ...
0
votes
0answers
4 views

Graphing ratios; non-common denominators for different data series in the same category?

I'm developing custom graphing software for a client and they have a need that doesn't make sense to me mathematically and I was hoping someone could help. They will be graphing the ratio of scrapped ...
2
votes
1answer
50 views

More Generating Functions problems

(a) For this problem, define a nonstandard die as a 6-sided die that is equally likely to come up on each side, but has a different set of numbers than the usual 1,2,3,4,5,6 on its sides. A standard ...
0
votes
3answers
53 views

Need help with flaws in statistical reasoning

The problem is as follows - there are three couples and six chairs in a row. The six individuals are seated at random. What is the chance that at least one couple will be seated together? Here's my ...
0
votes
0answers
34 views

Distributing balls in boxes.

In how many ways can $n$ identical balls be distributed amongst $m$ different boxes given that a box can have any number of balls(from $0$ to $n$)? What I've tried is using multinomial theorem to ...
0
votes
0answers
26 views

Permutation Inversion Question [closed]

Show that the number of permutations of {1,...,n} with k inversions is equal to the number of permutations of {1,...,n} with (n choose 2)-k inversions.
2
votes
2answers
3k views

Count the number of positive solutions for a linear diophantine equation

Given a linear Diophantine equation, how can I count the number of positive solutions? More specifically, I am interested in the number of positive solutions for the following linear Diophantine ...
3
votes
0answers
29 views

placing chess knights in a numbered chessboard.

Suppose you have a square board where the number on the square in column $i$ and row $j$ is $(j-1)8+i$ you have to place knights on the board so no two knights threaten each other and the sum of the ...
1
vote
1answer
58 views

Closed form expression for $\sum_{k=0}^m{ n+2k \choose 1+2k}$

Can we get a closed form expression for $f(m,n) = \sum_{k=0}^m{ n+2k \choose 1+2k}$, for $m\ge 0, n>1$? I am interested in this expression, as it appeared in one of the problems I was solving. ...
2
votes
1answer
46 views

How can I simplify $ \sum_{r=0}^{m-1}r^3\frac{\binom{m}{r}(m-r)!\begin{Bmatrix} n\\ m-r \end{Bmatrix}}{m^n}$?

Let $N$ and $M$ be sets with $n$ and $m$ elements respectively with $n>m$. Randomly assign a function $f:N\to M$. Suppose that the probability of each element in $N$ being assigned to any ...
-4
votes
0answers
25 views

Points on the sides of an equilateral triangle are colored in two colors. [closed]

Do there exist on the perimeter of the triangle three monochromatic vertices of a right-angled triangle?
1
vote
1answer
26 views

raBinomial distribution with dependent trials?

I need your help with following problem: String with n characters is given. For each character in string there is probability p that it is wrong. Now you take a sliding window of length k, k<= n, ...
0
votes
0answers
27 views

Given a positive integer $k$, find the integer part of $n^2 /k$ for $n\ge 1$, and a related question.

For a given positive integer $k,$ I am looking for possible answers / literature about the sequence $(a_n)=([\frac{n^2}{k}])_{n=1}^\infty$, where $[x]=$the integer part of $x.$ This question is ...
0
votes
0answers
20 views

Investment Strategies(Integer Solutions Of Equations)

You have \$$20$k that must be invested among $4$ possible opportunities. Each investment must be in multiples of \$$1$k, and there are minimal investments that need to be made if one is to invest in ...
0
votes
0answers
17 views

The number of lattice points in d-dimensional ball

The following paper states that the number of lattice points in a $d$-dimensional ball of radius $R$ is $V_d R^d + O(R^\alpha)$ where $\alpha = d - 2$ and $V_d$ is the volume of the unit ...
4
votes
3answers
2k views

How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?

I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice. I've spent quite ...
3
votes
1answer
524 views

What is the maximum number of combinations with repetitions, that the sum could be the same?

Suppose I have $n$ integers (both negative and positive) and I get all combinations of $k$ elements with repetition $((n, k)) = (n + k-1, k)$ My question is: what is the maximum number of ...
1
vote
2answers
182 views

On the Homology of Posets

Is there a homology theory of posets which computes topological invariants (e.g., number of $k$-faces, etc.) of the associated Hasse diagrams (viewed as simplicial/cellular/singular complexes) as ...
1
vote
2answers
34 views

Formula for counting ways to divide a number of people into separate groups

Assume six people at a party. Is there a formula to calculate the total possible combinations? Ie: Six alone. Four together, two alone. Four together, two together. 3 together, 3 others ...
3
votes
3answers
509 views

How many functions are transitive?

Let the set of all functions defined as: $\left\{a,b,c,d\right\} \rightarrow \{a,b,c,d\}$ How many functions are transitive? I've been told to use the fact that a function is transitive iff "it's ...
-2
votes
0answers
26 views

31 Knights round table problem formula. [closed]

A legendary King decided who was the fittest to marry his daughter. The way he chooses is to have 31 knights all sit down at the round table and he'll say to the first knight, "You live." He'll say to ...
1
vote
1answer
42 views

Combinatorial identity on partitions

In Stanley's Enumerative Combinatorics, there is the following identity $$\sum_{n \geq k}S(n,k) x^n = \frac{x^k}{(1-x)(1-2x) \dots (1-kx)}$$ where $S(n,k)$ denotes the number of partitions of an ...
1
vote
1answer
34 views

Simple Countability Problem

Count the number of strings of length 8 over A = {a, b, c, d} that begins with either a or c and have at least one b. My attempt: 4^8 total possibilities. a or c will occupy the first part, so ...
2
votes
2answers
493 views

How many 90 ball bingo cards are there?

In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three ...