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)

0
votes
0answers
60 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 ...
2
votes
1answer
98 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 ...
4
votes
0answers
47 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
34 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 ...
2
votes
1answer
58 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 ...
1
vote
1answer
41 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, ...
2
votes
0answers
72 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
3answers
56 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
2answers
73 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 ...
1
vote
0answers
56 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 ...
11
votes
1answer
591 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 ...
1
vote
1answer
65 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. ...
1
vote
1answer
38 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 ...
0
votes
0answers
16 views

Specific property of complete weighted graphs with 6 vertices with distinct weights

Given a complete graph with 6 vertices such that all edge weights are distinct. Prove that there exist edge which is lightest in one triangle, and heaviest in another. My first approach was to find ...
2
votes
1answer
70 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
4answers
58 views

dealing cards probability

If a standard deck of cards is deal to 4 players, 13 cards each, how many possibilities are there assuming that it matters which player gets but card order does not matter. Why is the answer not (52 ...
3
votes
2answers
74 views

Binomial Theorem Application Exercise

In my theoretical mathematics class notes, the following problem is left open as an exercise. The professor thinks the solution should be easily seen, but after many hours, I cannot gain the proper ...
0
votes
1answer
78 views

Rolling a three sided die six times?

Consider the problem of a rolling a three-sided die six times (independently). The probability of seeing 1 is 0.5, 2 is 0.25, and 3 is 0.25. With this model, I have been given the claim that: We ...
0
votes
2answers
27 views

combinatorics question sampling without replacement

Suppose a bag has $x$ blue marbles and $y$ red marbles, and the marbles are picked one at a time without replacement. Would the probability that all blue marbles are picked before red marbles be ...
0
votes
2answers
40 views

Probability counting question combinatorics

You must choose 9 courses from a list of 20 classes. At least one course has to be a math class, and 5 out of the 20 classes are math classes. How many possible combinations of 9 classes can the ...
1
vote
2answers
79 views

How many different DNA sequences of length 4 consist of exactly two different letters?

Note: $P(A)=p_A, P(C)=p_C, P(G)=p_G, P(T)=p_T$ My attempt: I tried to make a list of every single possible sequence. How can I solve this question more efficiently?
1
vote
0answers
47 views

Bijection between $n$-partitions and “flattened” canonical $n+1$-partitions

The set of $n$-partitions (partitions of the set $\{1, 2, \ldots, n\}$) and the set of "flattened" canonical $(n+1)$-partitions (those permutations obtained by removing the bars from an $(n+1)$ ...
0
votes
4answers
368 views

Random walk on a finite square grid: probability of given position after 15 or 3600 moves

An ant is walking on the squares of a 5x5 grid - it starts in the center square. Each second, it will choose (with equal probability) to do one of the following: Move north one square Move south ...
0
votes
2answers
72 views

How many of the n! permutations π from set N to N satisfy min(π(A)) = min(π(B))

Given a set of elements $N = \{1, 2,\ldots, n\}$ and two arbitrary subsets $A\subseteq N$ and $B\subseteq N$, how many of the $n!$ permutations π from $N$ to $N$ satisfy min(π$(A)$) = min(π$(B)$), ...
3
votes
0answers
59 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
0
votes
1answer
26 views

Methods of enumeration(counting techniques)

"Ten children are to be grouped into two clubs, says the lions and the tigers, five in each club. Each club is then to elect a president and secretary. In how many ways can this be done?" The answer ...
3
votes
2answers
340 views

Expected number of output letters to get desired word

I am using a letter set of four letters, say {A,B,C,D}, which is used to output a random string of letters. I want to calculate the expected output length until the word ABCD is obtained; that is, the ...
0
votes
2answers
57 views

Combinatorics. Could somebody explain how binomial theorem is applied here?

I do not understand this solution and this formula and why we are using (1+1)^n... I need some help to get an idea of what is going on here Thanks
1
vote
1answer
70 views

Possible Pool Table Layouts

There is a pool game called Nine-ball. It involves 9 numbered balls 1-9 and a cue ball, so 10 balls overall. A player starts the game with a "break" shot by hitting the cue ball into the "rack of 9 ...
5
votes
1answer
108 views

Proving that $\sum_{i = 0}^{m}{\binom{k+i}{i} \binom{n-i}{m-i}} = \binom{n+k+1}{m}$

Goal: prove that $\displaystyle\sum_{i = 0}^{m}{\binom{k+i}{i} \binom{n-i}{m-i}} = \binom{n+k+1}{m}$ How to give a combinatorial argument, i.e. counting in two ways, for this problem? I tried by ...
1
vote
0answers
16 views

Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
0
votes
0answers
45 views

City grid problem: how to interpret such that we use Vandermonde's convolution

A person wants to return to their house that is two blocks north and three blocks east. The problem resolves to taking five moves such that two are northward; there are thus $C(5,2) = 10$ total paths. ...
2
votes
2answers
305 views

Hat Matching Problem Expectation

I have an interesting problem in the context of the hat matching problem: There are n people with hats at a party. Each person randomly grabs a hat. A match occurs if a person gets his own hat. I'd ...
0
votes
0answers
31 views

Counting Enumeration Problem

Assume a set $N=\{1,\dots,n\}$. Let $A_n$ be the set of ordered pairs $(a,b)$ so that $b$ is a subset of $N$ and $a$ is a subset of $b$. Show that $|A_n|=k^n$ for a suitable $k$. So far, I am ...
1
vote
1answer
35 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
1
vote
0answers
27 views

Ehrhart Polynomials Modulo Prime Integers

Are there any results known about computing Ehrhart Polynomials modulo prime integers?
0
votes
1answer
26 views

Recurrence for integer triangles with perimeter $n$

Let $a_n$ be the number of sets $\{x,y,z\}\subset\mathbb{N}$ such that $x,y,z$ are the lengths of the sides of a triangle with perimeter $n$. Obtain a recurrence relation for $a_n$. I don't ...
1
vote
1answer
49 views

How many terms are in $\sum \alpha_1^{a_1}\alpha_2^{a_2}\cdots \alpha_r^{a_r}\alpha_{r+1}\alpha_{r+2}\cdots \alpha_s$

Suppose that $\alpha_1, \cdots, \alpha_n$ be $n$ roots of the polynomial equation $p(x)=0$ of degree $n$. I was studying on symmetric polynomial and have come accross of several problems on like $\sum ...
2
votes
2answers
71 views

Stuck on Generating Functions

1) Determine how many ways Brian, Katie, and Charlie can split a 50 dollar dinner bill such that Brian and Katie each pay an odd number of dollars and Charlie pays at least 5 dollars . 2) Determine ...
1
vote
2answers
115 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 ...
0
votes
1answer
43 views

Find the possible number of assignments

There are $S$ students, $I$ interviewers, each student has to undergo $R$ interviews, and each interviewer can interview at most $X$ students. No student interviews with an interviewer more than once, ...
-1
votes
2answers
103 views

Combinatorics (Yahtzee)

Well I am trying to solve some math problems and I am stuck, I really need some help. Here are the problems, please feel free to help me out. How many of the outcomes on a single "Yahtzee Throw" ...
1
vote
2answers
41 views

Partitions tending to a constant

$P_{k}(n)$ = the number of partitions of n into k parts. Now, if we fix some $t\ge 0$ , then $\lim_{n\to\infty}P_{n-t}(n)\to$ c, c being some constant. Please help me with this! I believe ...
2
votes
3answers
64 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$.
2
votes
1answer
53 views

Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
-1
votes
1answer
273 views

Finding winner of flipping game

Alice and Bob play a game with N non-negative integers. Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list. That is, they ...
0
votes
1answer
57 views

Find number of solutions to the equation?

Find the number of distinct ways to make a sum N using numbers given numbers $a_1,a_2,a_3...a_k$ where $1\le k\le n$ .Here $a_1,a_2,...a_k$ can be used more than once. Example: If N=19 and the ...
2
votes
2answers
131 views

A Question on distribution numbers

This is a question from the book Combinatorics -a problem oriented approach which states: Q.1 Find the no. of distributions of a set of distinct balls into a set of distinct boxes, if no boxes can ...
0
votes
2answers
476 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
4
votes
2answers
137 views

Can anybody help me solve this combinatorial identity?

While trying to derive some physical equation, I noticed that the following identity was needed: $\sum^{4a \leq 2k}_{a=0}{2k \choose 4a} + \sum^{4a+1 \leq 2k}_{a=0} {2k \choose 4a+1} = \left\{ ...