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
59 views

Simplify this equation.

Can I simplify or approximate this equation without sigma and combination? \begin{align} \sum_{i = 0}^n (-1)^i {n \choose i} \frac{{d+1}}{d(di + 1)} \end{align}
1
vote
2answers
74 views

Is there a closed form for this binomial sum?

I am looking for a closed form of this sum:$\sum\limits_{j=k}^n\binom{j}{k}(-1)^j$ I know that this sum has a closed form: $\sum\limits_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}$ I can get this closed ...
1
vote
2answers
47 views

in urn A white balls and B black balls. what would be the probability of taking the 5th ball being white

the problem goes like that "in urn $A$ white balls, $B$ black balls. we take out without returning 5 balls. (we assume $A,B\gt4$) what would be the probability that at the 5th ball removal, there was ...
1
vote
2answers
63 views

How many 6-digit numbers contain exactly 4 different digits? [duplicate]

my solution is----> NUMBER can be 777210 this i denote by aaabcd ------ this can be done in ---> 10*1*1*9*8*7*[6!/3!] {1 for a thrice} NUMBER can be 772210 this i ...
0
votes
0answers
30 views

Transforming generating functions into algorithms that generate combinatorial objects

I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities). However, I'm not interested ...
3
votes
2answers
45 views

Help me understanding what actually i counted with inclusion-exclusion

I tried to solve following task: Count number of $8$-permutations from $2$ letters $A$, $2$ letters $B$, $2$ letters $C$ and $2$ letters $D$ where exactly one pair of same letters are adjacent in ...
0
votes
6answers
33 views

Arrangement of 12 boys and 2 girls in a row.

12 boys and 2 girls in a row are to be seated in such a way that at least 3 boys are present between the 2 girls. My result: Total number of arrangements = 14! P1 = number of ways girls can sit ...
4
votes
1answer
34 views

When is a recurrence the sum of the powers of the roots of a polynomial?

Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots ...
1
vote
1answer
68 views

Parity of $\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor$

Let, $L=\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor $. Problem: Find $n$ for which $L$ is odd. In other words, find a closed form expression (function) $f(n)$of variable $n$ such that $L$ is odd/even if ...
0
votes
1answer
56 views

Isi B.Math Fibonacci problem.

Let $\dbinom{n}{k}$ denote the binomial coefficient $\frac{n!}{k!(n-k)!}$ , and $F_m$ be the $m^{th}$ Fibonacci number given by $F_1=F_2=1$ and $F_{m+2}=F_m+F_{m+1}$ for all $m\geq 1$. Show that $\...
3
votes
1answer
51 views

Each $2\times 5$ rectangle contains $1\times 3$ rectangle

A $60\times 60$ board is partitioned into rectangles of size $2\times 5$ (or $5\times 2$). Is it true that there always exist another partition into rectangles of size $1\times 3$ (or $3\times 1$) ...
1
vote
1answer
62 views

Need to prove that there is a continuous sequence which contains 100 cup of coffee , i.e. a man drinks one cup of coffee at the day.

A man can drink at least one cup of coffee at the day. After one year he drinks 500 cup of coffee. Need to prove that there is a continuous sequence which contains 100 cup of coffee, i.e. a man drinks ...
2
votes
0answers
28 views

Number of zigzag permutations of first $n$ natural numbers given start and end value

Given $n$ and $1\le s,e\le n$, how to compute the number of zigzag permutations of first $n$ positive integers starting with $s$ and ending with $e$? I tried formulating a recurrence relation but can'...
3
votes
2answers
72 views

Rewriting product to a binomial

I'm currently researching Wigner matrices. I wanted to calculate the moments of its spectral density. The probability density is $$\frac{1}{2\pi} \sqrt{4-x^2} \text{ for } x \in [-2,2] $$ I have ...
1
vote
0answers
96 views

Joint probability with constraint [on hold]

Let's say that one is conducting an experiment with 8 units and 4 units have to be assigned to treatment. Assuming all units' respective treatment assignment probabilities are greater than 0 and less ...
0
votes
1answer
49 views

Closed formula for ${r \choose 1}+{r \choose 2}\cdots{r \choose w}$ where $w < r$ [on hold]

Let $r,w \in \mathbb{N}$. Are there some formula for the next sum? $${r \choose 1}+{r \choose 2}\cdots{r \choose w}$$ where $w<r$?
0
votes
2answers
42 views

How to correctly count the probability for a computer game situation? [on hold]

Imagine we have the following situation in a computer game: One player has two minions with 30 and 6 hitpoints correspondingly. Another player casts a spell which does 12 times 1 damage (for each of ...
0
votes
0answers
25 views

Distribution for playing n scratcher lottery tickets

If I know the prize distribution for a scratcher lottery ticket (i.e. the various prize amounts and the probability associated with each prize) is there a way to form a distribution for playing, say, ...
1
vote
0answers
42 views

Given N blocks, find the number of unique shapes in a NxN block

Constraints: The blocks must be adjacent to each other. i.e. A pair of blocks must have a common edge or vertex. Any shapes that are formed by flipping or rotating or mirroring should be considered to ...
2
votes
1answer
23 views

double summation of conditional variable depending on sum of integer

I am having trouble with taking a certain summation and finding an explicit value for the summation. The summation is: $$ S = \sum_{w=3}^a \lambda_w \sum_{m=w}^a \lambda_m $$ The only information ...
8
votes
0answers
94 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$...
1
vote
3answers
154 views

Find general solution for the equation $1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) $

A positive integer $n$ is called a balancing number if $$1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) \tag{1}$$ for some positive integer $r$. Problem: Find the general ...
2
votes
1answer
33 views

Binomial identity for bijection $\mathbb N\times\mathbb N\to\mathbb N$

In a book I'm currently reading it is said (without proof) that, for an enumeration $d$ of $\mathbb N\times\mathbb N$ defined by $$d(0)=(0,0),\ d(1)=(0,1),\ d(2)=(1,0),\ d(3)=(0,2),\ d(4)=(1,1),\ d(5)=...
4
votes
0answers
57 views

How many subsets of $n$ linearly independent binary strings of length $n$?

Let's consider binary words of length $n$ with elements {-1,1}. There are $2^n$ binary words of length $n$. Now let's consider a subset of $n$ such binary words. All possible subsets are $\binom{2^n}{...
0
votes
0answers
14 views

Noetherian Rings Definition, countability?

In my book (Jantzen, Algebra, 2014), Noetherian rings are defined by three equivalent conditions. I wonder how the first two can be equivalent: Every ascending chain of ideals $(a_1) \subset (a_2) \...
2
votes
3answers
56 views

Doubt in finding number of integral solutions

Problem : writing $5$ as a sum of at least $2$ positive integers. Approach : I am trying to find the coefficient of $x^5$ in the expansion of $(x+x^2+x^3\cdots)^2\cdot(1+x+x^2+x^3+\cdots)^3$ . ...
1
vote
2answers
35 views

Half from any $2n$ but not $2n+2$

Let $n$ be a positive integer. What is the length of the longest possible sequence of $0$'s and $1$'s such that among any $2n$ consecutive numbers, exactly half are $0$'s, but among any $2n+2$ ...
1
vote
3answers
40 views

Expected Value for Heads for Unknown Weighted Coin Given Head First Flip

This is a combinatorics problem, and I think it involves expected values and conditional probability, but I don't know how to use them: "A bag contains an infinite number of coins whose probabilities ...
0
votes
1answer
39 views

distributing numbered balls with duplicates into 4 boxes [closed]

How many ways are there to distribute 52 balls, numbered 1 to 13 with 4 duplicates for each number, into 4 distinguishable boxes.
2
votes
0answers
18 views

Finitely many steps to $n$-stone pile.

I have a combinatoric problem still unsolved: $2n$ ($n$ is a positive integer) stones are divided into $3$ piles. In each step, we pick half of a pile which has even number of stones and move those ...
0
votes
3answers
30 views

code to calculate all combinations [closed]

I have the follwing problem: I have an array u of length d. The sum of every integer of this array u should be k, and integers are from 0 to k. I want now all possible combination that suffice this ...
1
vote
4answers
47 views

Bayesian probability problem?

Problem: In a city there are three types of taxis which drive towards the airport. 30% are blue, 20% green, 50% yellow. They take there customers too late with probabilities 0.1,0.2,0.3 respectively. ...
7
votes
3answers
139 views

Maximum area of triangle inside a convex polygon

Prove that within any convex polygon of area $A$, there exists a triangle with area at least $cA$, where $c=\tfrac{3}{8}$. Are there any better constants $c$? I'm not sure how to approach this ...
0
votes
3answers
35 views

Prove that if a collection of subsets of {1,..,n} that each pair of subsets has at least one element in common, there are at most $2^{n-1}$ subsets

Full question: Prove that if a collection of subsets of {1,2,...,n} has the property that each pair of subsets has at least one element in common, then there are at most $2^{n-1}$ subsets in the ...
0
votes
2answers
57 views

In AB + BC + AC = N, how can I find all possibilities for A, B and C in less than n³ computational time?

The problem is the one on the title. Given a N, find all possibilies for A, B and C that make this true: $AB+BC+AC = N$when $A \ge B \ge C$. This code in C do the job: ...
0
votes
4answers
57 views

In how many ways can a group of $n$ people composed of six types be created with restrictions?

Suppose we need to create a group of $n \geq 20$ people with the following types and requirements: Scientists, at least 2; Pro Athletes, at least 1; Mathematicians, at least 5; Plumbers, at least 0; ...
2
votes
1answer
56 views

Is there a more concise expression of this product?

In a longer computation, I have stumbled upon the following product, where $k,r \in \mathbb{N}_0$ are fixed numbers: $$\prod_{0 < i_0<i_1<\dots<i_r\leq k} (i_r-i_{r-1})(i_{r-1}-i_{r-2})\...
0
votes
1answer
36 views

Least distance between two points in an equilateral triangle [closed]

Five points lie inside an equilateral triangle of side 2 units.Prove that at least 2 points are no more than a unit distance apart.
0
votes
1answer
37 views

Picking balls from boxes, a logical approach?

You have a box with ten purple balls, five red balls, five blue balls, three yellow balls. You pick out four balls at random. What is the probability of all four balls being the same color? I've ...
11
votes
2answers
466 views

Differentiating the binomial coefficient

I took a lecture in combinatorics this semester and the professor did the following step in a proof: He showed that function $f: x \mapsto \binom{x}{r}$ is convex for $x > r - 1$ (in order to use ...
3
votes
1answer
32 views

How to find number of integral solutions, containing large number of cases?

Number of positive unequal integral solutions of the equation $x+y+z=12$ can be found out knowing the cases it involves: $(1, 2, 9) , (1,3,8), (1,4,7), (1,5,6), (2,3,7), (2,4,6) and (3,4,5)$. Thus, ...
1
vote
2answers
48 views

Problem 14, Ch. 1 from Blitzstein and Hwang, Intro to Probability

You are ordering two pizzas. A pizza can be small, medium, large or extra large, with any combination of 8 possible toppings (getting no toppings is also allowed, as is getting all of 8). How many ...
0
votes
0answers
26 views

Problem 13, Ch1 from Blitzstein and Hwan, Intro to Probability

A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. Thus, a superdeck has $52{\cdot}10=520$ cards, with 10 copies of each card. How many ...
5
votes
5answers
120 views

Prove that $\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$

Prove that $$\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$$ I've tried multiple things that didn't work. Maybe this would help $$\sum_{k=0}^n \binom{3n-k}{2n}=\sum_{k=0}^n \binom{3n-(n-k)}{2n}=\...
0
votes
3answers
67 views

Find the number of sums that you will get A, when A=100?

Problem: Take any number $A \in \Bbb{N} = \{1, 2, 3, \dots\}$, and then take $x, y \in \Bbb{N}$, where $x \ne y$ and $x + y = A$. Find the number of possible choices for $x$ and $y$ when $A=100$. ...
-4
votes
2answers
52 views

b) How many onto functions are there from A to C? [duplicate]

Let $A=\{1,2,3,4\}$ Let $B= \{a,b\}$ Let $C= \{ \text{hiking, baseball, hockey} \}$ a) How many onto functions from A to B $(1,a) (1,b) (2,a) (2,b) (3,a) (3,b) (4,a) (4,b)$ Thus 8. b) How many ...
2
votes
2answers
45 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
1
vote
2answers
108 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
0
votes
0answers
22 views

Consider the system S which can take n input parameters and each parameter can take on m values

(a) What is the maximum number of pairs a single test case for this system can cover? "I know that there are m^n different combinations in this example, but i'm unsure how many pairs a single test ...
0
votes
1answer
44 views

Combination Problem : $6$ Countries , $4$ players from each country

$6$ Countries participate a world tournament . Each country has $4$ players. One Cricket player , One Rugby player , one Volleyball player and one Football player. Need to select a team of $8$ ...